9.4.7 Access By Order in AVL Trees

Given a key value to find, it is easy to search the AVL tree for it. However, consider the records stored at the nodes as ordered by their processing positions in an inorder traversal of the AVL tree. For instance, in the AVL tree of Figure 9.10, the ordering is

1.  17   9.  60

2.  35  10.  70

3.  37  11.  80

4.  40  12.  81

5.  45  13.  83

6.  50  14.  85

7.  53  15.  100

8.  55

By access by order to a node is meant that, given an index (say, 10) produce the tenth record (key value 70 above). The difficulty is that it is not immediately apparent where node 10 is nor what its key value is. One way to access this node is simply to inorder traverse the tree, counting nodes. Arriving at the tenth node, produce it. This will take time O(i) if the index is i. In the worst case this is O(n), if n nodes are stored in the tree. Since AVL trees with n nodes have maximum depth 1.44 lg n, any key search, insertion, or deletion can be done in at most O(1g n) time. There is also a simple way to access by order, or index, in at most O(1g n) time. To accomplish this, add an index field to each node. It will contain an integer that is 1 plus the number of nodes in its left subtree. The index field thus contains the nodes' index. For example, the index field value of 70 would be 10. It is then possible to search the tree for an index value, much as it is searched for a key value. The index search thus takes time at most O(1g n). Of course, the insertion and deletion algorithms must be modified to keep the index fields updated correctly.

Creating an AVL tree is done by growing it as was done for the simple binary search tree: start with a null tree and insert each input record, one at a time. The difference is that a "simple" insertion is used to grow the simple binary search tree, whereas the insertavl procedure is used to grow an AVL tree. The AVL tree may be grown in O(n lg n) time. Also, since it may then be inorder traversed in O(n) time, we have another way to sort in O(n lg n) time.