Reducing rotations during deletion from AVL trees

mgcadmin 02-05-2025

AVL trees are the oldest of the self-balancing binary search trees. Like other self-balancing BST's, AVL trees use rotations to enforce balancing. While the tight balancing conditions of AVL tree's result in quick search times, it also has the effect of potentially requiring up to logN rotations in the worst case to rebalance the tree after a deletion. It is for this reason that in applications where many interspersed insertion and deletion operations take place that Red/Black trees with their bounded number of rotations - 2 for insertion, 3 for deletion - are the preferred data structure.

In 2015 Tarjan et. al introduced Weak AVL (WAVL) trees as a new type of rank balanced search tree that possesed the search properties of AVL trees with the relaxed balancing of Red/Black tree's allowing for a more efficient search tree. For todays post I want to talk about a different approach to reducing the number of rotations an AVL tree requires to maintain balance after deletion: choosing an internal nodes replacement preferentially by size of the respective sub trees.

Maintaining balance in AVL trees

AVL trees maintain their balance by performing rotations. The choice of when to rotate and which rotation to apply is determined through a nodes balance factor. The balance factor of a node is computed by finding the difference in height of a given nodes left subtree from its right subtree.

        int balanceFactor(link h) {
            if (h == nullptr)
                return 0;
            return height(h->left) - height(h->right);
        }
        link balanceAVL(link h) {
            if (balanceFactor(h) < -1) {
                if (balanceFactor(h->right) > 0) {
                    h->right = rotR(h->right);
                }
                h = rotL(h);
            } else if (balanceFactor(h) > 1) {
                if (balanceFactor(h->left) < 0) {
                    h->left = rotL(h->left);
                }
                h = rotR(h);
            }
            return h;
        }

Unlike the red/black family of balanced binary search trees, AVL trees use the same balancing logic for deletion as they do for insertion. In addition, the balancing logic is both easy to understand and implement, make it a desirable choice for a symbol table when deletions must be supported. 

Reducing Post-Deletion Rotations in AVL Trees

The "traditional" method for removing a node from an AVL tree is to use the hibbard deletion method of replacing the node with it's in-order successor, and then removing the in-order successor's node which is guranteed to be a leaf, from the tree. Once removed, any balancing required is performed on the way back up the tree as the call stack unwinds. While effective and simple, this method is unfortunately asymmetrical in its approach and asymmetry and balance are opposing forces. As we learned with left leaning red/black trees, asymetry during balancing can lead to an increased number of rotations.

In the case of left leaning red/black tree's the asymmetry caused more rotations because of the fewer number of valid 2-3 tree's when the left leaning configuration is enforced. In the case of an AVL tree, always favoring one subtree without regarding the balance before the removal means that we may be doing rotations when no rotation even need be done, if one tree is higher than the other, simply removing a leaf from the taller sub tree may bring the tree back into balance without doing any rotations. This of course wont happen every time, but it should happen enough that we see a decent reduction in the number of rotations neeed to maintian balance after a deletion.

       link eraseR(link h, K key) {
            if (h == nullptr) 
                return h;
            if (key < h->key) { 
                h->left = eraseR(h->left, key);
            } else if (key > h->key) { 
                h->right = eraseR(h->right, key);
            } else {
                link tmp = h;
                if (h->right == nullptr) {
                    h = h->left;
                } else if (h->left == nullptr) {
                    h = h->right;
                } else {
                    if (size(h->right) > size(h->left)) {
                        h = min(tmp->right);
                        h->right = eraseMin(tmp->right);
                        h->left = tmp->left;
                    } else {
                        h = max(tmp->left);
                        h->left = eraseMax(tmp->left);
                        h->right = tmp->right;
                    }
                }
                delete tmp;
                count--;
            }
            h = updateRankAndHeight(h);
            return balanceAVL(h);
        }

By allowing the replacement node to be plucked from either subtree, we re-introduce symmetry to the algorithm. If the left sub tree is smaller, then we replace the node with it's in-order successor from the nodes right subtree. If the right sub tree is smaller, then we replace the node with it's in-order predecessor, this time taken from the nodes left subtree.

Putting It to the test

To test whether the new algorithm is an improvement with regards to reducing the number of rotations performed, I built two trees from identical inputs using randomly generated keys and trees of varying size. The keys were then erased from the tree's using the two algorithms and their rotation counts compared.

Run 1: 293 entries: 
         Improved Alg: Total rotations performed: 95 of which Left rotations: 39, And Right rotations: 56
         Orginal Alg: Total rotations performed: 120 of which Left rotations: 89, And Right rotations: 31
Run 2: 292 entries:
         Improved Alg: Total rotations performed: 92 of which Left rotations: 30, And Right rotations: 62
         Orginal Alg: Total rotations performed: 117 of which Left rotations: 90, And Right rotations: 27
Run 3: 307 entries:
         Improved Alg: Total rotations performed: 119 of which Left rotations: 67, And Right rotations: 52
         Orginal Alg: Total rotations performed: 141 of which Left rotations: 105, And Right rotations: 36
Run 4: 283 entries:
         Improved Alg: Total rotations performed: 101 of which Left rotations: 46, And Right rotations: 55
         Orginal Alg: Total rotations performed: 119 of which Left rotations: 84, And Right rotations: 35
Run 5: 284 entries: 
         Improved Alg: Total rotations performed: 104 of which Left rotations: 57, And Right rotations: 47
         Orginal Alg: Total rotations performed: 112 of which Left rotations: 83, And Right rotations: 29
Run 6: 315 entries:
         Improved Alg: Total rotations performed: 118 of which Left rotations: 71, And Right rotations: 47
         Orginal Alg: Total rotations performed: 135 of which Left rotations: 99, And Right rotations: 36
Run 7: 294 entries:
         Improved Alg: Total rotations performed: 104 of which Left rotations: 48, And Right rotations: 56
         Orginal Alg: Total rotations performed: 137 of which Left rotations: 95, And Right rotations: 42
Run 8: 283 entries:
         Improved Alg: Total rotations performed: 96 of which Left rotations: 52, And Right rotations: 44
         Orginal Alg: Total rotations performed: 122 of which Left rotations: 90, And Right rotations: 32
Run 9: 296 entries:
         Improved Alg: Total rotations performed: 100 of which Left rotations: 59, And Right rotations: 41
         Orginal Alg: Total rotations performed: 122 of which Left rotations: 88, And Right rotations: 34
Run 10: 294 entries: 
         Improved Alg: Total rotations performed: 109 of which Left rotations: 58, And Right rotations: 51
         Orginal Alg: Total rotations performed: 135 of which Left rotations: 97, And Right rotations: 38

On every single run the new algorithm performed fewer rotations than the original. Indicitive of greater balancing is the difference in ratio of left rotations to right rotations performed. Not only is the overall number of rotations reduced, the type of rotation is more evenly dispersed.

Though certainly more testing needs to be done, the implications of these results are clear: By preferring to take the in order successor or predecessor based on the size of their corresponding tree's reduces the numbers of rotations required to maintain balance after removing a node from the tree.

Until next time, Happy Hacking!

---