My prof was talking about how to augment a tree to efficiently find the key with a given rank. On the way to getting the right answer (store the size of the subtree rooted at each node), he proposed augmenting each node with it's rank. That way finding the node with a certain rank is a simple binary search. But he said this wouldn't work because insertion would be $\Theta(n)$. I understand that this is because in the worst case the newly inserted node has rank 0 and so the rank of each node in the tree must be incremented by 1. What I am interested in knowing is an algorithm for computing the rank of a newly inserted node. At first I thought that if a node $n$ is inserted to the left of a leaf $l$ with rank $k$ then the rank of $n$ is $k-1$, or $k+1$ if inserted right of $l$. I found a counter example to that so I know it is not the case. So how would this be done?

  • $\begingroup$ Hint: Insertion costs $O(\log n)$, so you can use $O(\log n)$ time for "free" $\endgroup$ – lox Jun 23 '19 at 8:24
  • $\begingroup$ Hint 2: after insertion of $x$, you have its left subtree (or null), right subtree (or null), and up to $log(n)$ nodes in the path from the root to $x$. $\endgroup$ – lox Jun 23 '19 at 8:25
  • $\begingroup$ On the path down to x from the root I keep track of the largest rank of any node smaller than x. Once x is inserted it's rank is 1 larger than the maximum. On my way back up to the root I update the rank of any node larger than me by adding 1 to it. Is this the correct answer? $\endgroup$ – nakamin Jun 23 '19 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.