Consider the following order statistic tree with the given keys: [3,7,10,12.14.1
ID: 3668446 • Letter: C
Question
Consider the following order statistic tree with the given keys: [3,7,10,12.14.14,16,17-19.20.21,21.26.28.30,35,38,39:41.47], each node on the tree has another key called size which gives the size of the subtree (number of all children of that node including itself) and the two methods, each node has a pointer to its parent node called. Answer the following questions: Show the recursive calls for OS-select(T. 19) Show the recursive calls for OS-select(T. 7) Show the recursive calls for OS-select(T. 14) Show the nodes visited and the value of r for OS-rank(T, 10) Show the nodes visited and the value of r for OS-rank(T, 28) Show the nodes visited and the value of r for OS-rank(T, 20) Given an element x in an n-node order-statistic tree and a natural number i, how can we determine the i h successor of x in the linear order of the tree in O (lg n) time?Explanation / Answer
a) OS-SELECT(x,i)
We begin with x as the root, whose key is 26, and with i = 19. Since the size of 26’s left subtree is 12, its rank is 13.Thus, we know that the node with rank 19 is the 19 -13 = 6th smallest element
in 26’s right subtree. After the recursive call, x is the node with key 41, and i = 6.
Since the size of 41’s left subtree is 5, its rank within its subtree is 6. Thus, the procedure returns a pointer to
the node with key 41.
So the recursive calls are :
x = 26 , i = 19
x = 41 , i = 6
return 41
b)
Similarly, the recursive calls for OS-SELECT(T,7) are :
x = 26 , i = 7
x = 17, i = 7
x = 14 , i = 7
x = 16, i = 2
return 16
c)
Similarly, the recursive calls for OS-SELECT(T,14) are :
x = 26 , i = 14
x = 41, i = 1
x = 30 , i = 1
x = 28, i = 1
return 28
d)
Iteration node visited r
1 10 3
2 14 3
3 17 3
4 26 3
r = 3
e)
Iteration node visited r
1 28 1
2 30 1
3 41 1
4 26 14
r = 14
f)
Iteration node visited r
1 20 1
2 19 2
3 21 2
4 17 10
5 26 10
r = 10
g)
OS-SUCCESSOR(T,x,i) :
R OS-RANK(T,x)
S r + i
Return OS-SELECT(root[T],s)
Since OS-RANK and OS-SELECT each take O(lg n) time, so does the procedure OS-SUCCESSOR.