How to augment an AVL tree?

Question

I want to augment an avl tree to add extra properties to each node such as number of nodes it contains (i.e. in its subtree).

From this avl java implementation code here http://www.blackbam.at/blackbams-blog/2012/05/04/avl-tree-implementation-in-java/ I want to add certain code to it, so that each node will contain a size element.

In the AvlNode class, I changed it to:

/** Here is the AVL-Node class for Completenesse **/
public class AvlNode {
     public AvlNode left;
     public AvlNode right;
     public AvlNode parent;
     public int key;
     public int balance;
     public int size;

     public AvlNode(int k) {
          left = right = parent = null;
          balance = 0;
          key = k;
          size = 1;
     }
     public String toString() {
         return "" + key;
     }
}

But now for the AvlTree class, where do I actually add the code to update the size value of the node, during the insert and delete operations. I think it's the rotateleft and rotateright methods. Is this right?

templatetypedef templatetypedef · Accepted Answer · 2013-02-07T00:14:06

This completely depends on what you're trying to do with the augmentation. Typically, when augmenting a balanced binary search tree, you would need to insert extra code in the logic to do

Insertions, which change the number / contents of certain subtrees,
Deletions, which remove elements from subtrees, and
Tree rotations, which move nodes across different subtrees.

The "Introduction to Algorithms" textbook by CLRS has a chapter on augmented binary search trees. While they focus on red/black trees, the same general policies should work for any rotation-based tree balancing scheme.

Hope this helps!

How to augment an AVL tree?

1 Answers