Given a binary search tree T and a node x in the tree, describe the procedure of
ID: 3747309 • Letter: G
Question
Given a binary search tree T and a node x in the tree, describe the procedure of finding the predecessor PRECEDESSOR(x) of node x briefly, assuming that the routine of identifying a node with the maximum key in a subtree is given in advance, where a node y is the predecessor of a node x if all nodes in T are sorted in increasing order of their keys, the rank of node y is the rank of node x minus 1 in the sorted node sequence. In other words, y is the node with the largest key that is no greater than the key of node x.
Explanation / Answer
In Binary Search Tree PRECEDESSOR(x) will previous greater element then x.
Example : In 1 2 4 5 7 9
PRECEDESSOR(5) is 4
PRECEDESSOR(9) is 7.
To find PRECEDESSOR(x) is binary search tree we have to search the largest element in the left side of x as left will contain all elements smaller than x.
PRECEDESSOR(x){
y=x->left
y=findmax(y) // findmax is the routine for identifying a node with the maximum key in a subtree
return y;
}
THUMBS UP IF YOU ARE SATISFIED WITH THE ANSWER OTHERWISE REPLY WITH YOUR CONCERN.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.