AVL Trees: How to make access to the index?

Question

I noticed the following comment on the AVL Tree Wikipedia page :

"If each node additionally writes the size of its subtree (including its and its descendants), then the nodes can be restored by an index in O (log n)."

I have google and I found several places that mentioned access by index , but can't seem to find an explanation for the algorithm to write.

Many thanks

[UPDATE] Thanks to the people. If @templatetypedef is found, the answer is in conjunction with one of the @ user448810 links to especially help. Especially this snip:

“The key to both of these functions is that the node index is the size of its left child. While we are dropping the tree through its left child, we just take the node index. But when we need to move down the tree through its right child, we have to adjust the size to include half the tree we excluded. "

Since my implementation is immutable, I did not need to do any additional work when rebalancing, since each node calculates its size during construction (just like the implied scheme)

My final implementation has ended:

class Node<K,V> implements AVLTree<K,V> { ... public V index(int i) { if (left.size() == i) return value; if (i < left.size()) return left.index(i); return right.index(i - left.size() - 1); } } class Empty<K,V> implements AVLTree<K,V> { ... public V index(int i) { throw new IndexOutOfBoundsException();} } 

Which is slightly different from other implementations, let me know if you think I have a bug!

Answer 1

The general idea of ​​this design is to take an existing BST and increase each node, keeping the number of nodes in the left subtree. After that, you can find the nth node in the tree using the following recursive algorithm:

• To find the nth element in BST, the root node has k elements in its left subtree:
  • If k = n, return the root of the node (since this is the zero node in the tree)
  • If n & le; k, a recursive search for the nth element in the left subtree.
  • Otherwise, find the element (n - k - 1) st in the right subtree.

This takes O (h) time, where h is the height of the tree. In the AVL tree, this is O (log n). In CLRS, this construction is studied with respect to red / black trees, and they call such trees "sort statistics trees".

You need to introduce additional logic during the rotation of the tree in order to configure the cached number of elements in the left subtree, but this is not particularly difficult.

Hope this helps!