Iterative AVL Trees - Insertion

mgcadmin 19-02-2023

In the past I've primarily used two sources as reference material while implementing AVL trees: the example in Mastering Algorithms with Perl from O'Reilly, and Robert Sedgewick's description of the implementation from his book Algorithms. Both of these algorithms are implemented using recursion however, and I've always wanted to write a purely iterative implementation.

What follows is a simple implementation of insertion in AVL Tree's using parent pointers and loops instead of recursion. The rotate left and rotate right algorithms are taken practically unchanged from the CLRS chapter on red black trees.

 class AVLTree {
    private:
        struct node {
            T key;
            T2 value;
            int height;
            node* left;
            node* right;
            node* parent;
            node(T k, T2 v) {
                key = k; value = v; height = 0; left = right = parent = nullptr;
            }
        };
        node* root;
        int height(node* h) {
            return (h == nullptr) ? -1:h->height;
        }
        int max(int a, int b) { return (a < b) ? b:a; }
        void left_rotate(node *x) {
            node *y = x->right;
            if (y) {
                x->right = y->left;
                if (y->left) y->left->parent = x;
                y->parent = x->parent;
            }
            if (!x->parent) root = y;
            else if (x == x->parent->left) x->parent->left = y;
            else x->parent->right = y;
            if (y) y->left = x;
            x->parent = y;
            x->height = 1 + max(height(x->left), height(x->right));
            y->height = 1 + max(height(y->left), height(y->right));
        }
  
        void right_rotate(node *x) {
            node *y = x->left;
            if (y) {
                x->left = y->right;
                if (y->right) y->right->parent = x;
                y->parent = x->parent;
            }
            if (!x->parent) root = y;
            else if (x == x->parent->left) x->parent->left = y;
            else x->parent->right = y;
            if (y) y->right = x;
            x->parent = y;
            x->height = 1 + max(height(x->left), height(x->right));
            y->height = 1 + max(height(y->left), height(y->right));
        } 

The actual insertion itself is the normal top down insertion for binary search trees, starting at the root and inserting the new node at the leaf:

       void insert(T key, T2 value) {
            node* x = root;
            node* p = x;
            while (x) {
                p = x;
                x = (key < x->key) ? x->left:x->right;
            }
            x = new node(key, value);
            if (!p) root = x;
            else if (key < p->key) p->left = x;
            else p->right = x;
            x->parent = p;
            balance(x);
        } 

Once we've inserted the node at its position, we follow the parent pointers back up the tree, using rotations to ensure our tree maintains the AVL property:

       int balanceFactor(node* h) {
            return height(h->left) - height(h->right);
        }
        void balance(node* x) {
            while (x && x->parent) {
                node *y = x->parent;
                y->height = 1 + max(height(y->left), height(y->right));
                if (balanceFactor(y) < -1) {
                    if (balanceFactor(y->right) > 0) {
                        right_rotate(y->right);
                    }
                    left_rotate(y);
                } else if (balanceFactor(y) > 1) {
                    if (balanceFactor(y->left) < 0) {
                        left_rotate(y->left);
                    }
                    right_rotate(y);
                }
                x = x->parent;
            }
        } 

The above given scheme for determining which series of rotations to perform is derived from the work of Robert Sedgewick. An alternative algorithm for balancing, as proposed in CLRS is as follows:

      void balance(node* x) {
            while (x && x->parent) {
                node *y = x->parent;
                y->height = 1 + max(height(y->left), height(y->right));
                if (height(y->left) > height(y->right) + 1) 
                    right_rotate(y);
                if (height(y->right) > height(y->left) + 1) 
                    left_rotate(y);
                x = x->parent;
            }
        }

Sewing it all together we have a very straight forward, easy to implement height balanced binary search tree. I had long considered Red Black trees my go to for balanced search trees, however after putting this algorithm together, I think the AVL tree might be edging in on it's turf!

 

---