I am having trouble in understanding order-statistics tree .

Definition :
Every node in tree stores the number of descendants of itself .
Can you please explain the Algorithm or pseudocode how to Insert and Delete a node in the tree when tree is to be balanced .

Basically i want to find the rank of an element in the tree in O(log N) time complexity and nodes can be inserted and deleted in between querries .

P.S. I am able to understand the rank(x) operation .

  • 1
    I think it is better if you worked it out yourself. This is the best way to understand how it works. Try drawing up a tree and manually inserting and deleting elements, updating the tree accordingly. You should then be able to come up with pseudocode for Insert and Delete. – Yuval Filmus Mar 26 '14 at 14:12

The exact implementation of Insert and Delete depends on the underlying binary tree structure which is used, but the idea is that you maintain the size field throughout the operation. Consider for example the following Insert procedure, which always inserts its element as a new leaf:

Insert(Tree, $x$)

  1. If Tree is empty, set Tree to be $x$, and return.

  2. Let $r$ be the root of Tree, and Left, Right its children.

  3. If $x < r$ then call Insert(Left, $x$), otherwise call Insert(Right, $x$).

Here is the updated algorithm, which maintains the size information:

Insert(Tree, $x$)

  1. If Tree is empty, set Tree to be $x$ and size(Tree)=1, and return.

  2. Increase size(Tree) by 1.

  3. Let $r$ be the root of Tree, and Left, Right its children.

  4. If $x < r$ then call Insert(Left, $x$), otherwise call Insert(Right, $x$).

This is the basic idea. You can take it from here.

  • yes , i knew this , but i am interested in balanced insert/delete , sorry i missed it in my question . The step 2. you gave is not correct when rotations occour. – Aseem Goyal Mar 26 '14 at 14:33
  • The same idea works even when rotations occur, you just have to be more careful. I'm sure you can work it out yourself. – Yuval Filmus Mar 26 '14 at 14:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.