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?