# AVL tree to find kth smallest key

I'm working on this problem and having difficulty with it

Search trees such as BST, AVL, 2-3 trees are used to search a set of n keys for a key value. We can augment the tree to allow searching by rank, that is, we can ask for the kth smallest key in the tree. On way to do thus for AVL trees is to store a field L(x) at each node(in addition to the balance information for x) such that L(x) is 1+ the number of nodes in x's left subtree. Design an algorithm that inputs an AVL tree T with rank fields (L(x)) and n nodes and an integer k such that 1<=k<=n and outputs the kth smallest key in T. Analyze worst case complexity of the algorithm Explain how the rank information of T should be updated after the insertion of a new key.

First of all, I'm not sure why L(x) <-rank(x) is 1 + the number of nodes in x's left subtree. And for the time complexity, I think it will remain O(logn) as the insertion will rebalance the tree and it taks O(logn)

Can anyone please clarify this?

## 1 Answer

The #(number) nodes in the left subtree of $x$ is the # of nodes which have value less than that of the $x$ in the tree rooted at $x$.

The rank of an element is # of elements which are less than itself +1.

If you trying to search the rank of some element $y$ less than $x$, then rank of $y$ in tree rooted at $x$ is rank of $y$ in tree rooted at left subtree of $x$.

If you are trying to search the rank of some element $y>x$, then the rank of $y$ in tree rooted at $x$ =(rank of $x$ + rank of $y$ in right subtree of $x$).

Lastly if you are looking for rank of $x$, you just query at the root.

As far as updating the rank information is concerned. Every time a new element is added, check the root. If it is less than the root increment the root's rank field by one, and recurse on left-subtree, else dont increment the root's rank field and recurse on the right subtree.

Time to update the rank information is same as the time to insert an element in the tree.

• Does my answer solve the question now? – Vk1 Jul 12 '18 at 15:21