Describe how to extend the definition of a node in a binary search tree (what ad
ID: 3681897 • Letter: D
Question
Describe how to extend the definition of a node in a binary search tree (what additional fields to include) so that in addition to search, insert, and delete also the following count operation could be implemented to run in time O(h), where h is the height of the tree on which the operation is executed: count(T, k): return the number of elements in a tree T with the key smaller than k.
a-Explain how to modify the procedures insert and delete so that count works correctly after any sequence of insertions and deletions. sequence of operations??
PLEASE HELP ASAP
thanks
Explanation / Answer
The idea is to maintain rank of each node. We can keep track of elements in a subtree of any node while building the tree. Since we need K-th smallest element, we can maintain number of elements of left subtree in every node.
Assume that the root is having N nodes in its left subtree. If K = N + 1, root is K-th node. If K < N, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > N + 1, we continue our search in the right subtree for the (K – N – 1)-th smallest element. Note that we need the count of elements in left subtree only.
Time complexity: O(h) where h is height of tree.
/* Binary tree node */
struct node_t
{
int data;
int lCount;
node_t* left;
node_t* right;
};