Iterative AVL Trees - Deletion

mgcadmin 17-04-2023

In a previous article I introduced what AVL trees are, their structure and insertion. If you have not read that article, go back and read it first, as code in this article builds off of code from there.

AVL Tree's are the original self balancing binary search tree, and as with all binary search tree's - self balancing trees especially - the deletion algorithm is trickier to implement than for insertion.

Compared to Red/Black trees though, they're a breeze.

Deleting Items From a BST

Deleting a node from an AVL tree is performed in three distinct operations. It begins by searching for the node which we are going to delete, which is accomplished in the usual way, this is followed by a normal hibbard deletion on the node to be removed, after which we perform the same bottom up re-balancing that we use for insertion.

       void erase(T key) {
            node *x = root;
            bool found = false;
            while (x != nullptr) {
                if (x->key == key) {
                    found = true;
                    break;
                }
                x = (key < x->key) ? x->left:x->right;
            }
            if (found) {
                eraseR(x); 
            }
      } 

Notice that we're using a "found" flag to escape the search loop and proceed to an iterative hibbard deletion implementation:

void eraseR(node* h) {
            node* t = h;
            if (h->left == nullptr)
                moveNode(h, h->right);
            else if (h->right == nullptr) {
                moveNode(h, h->left);
            } else {
                node* y = min(h->right);
                if (y->parent != h) {
                    moveNode(y, y->right);
                    y->right = h->right;
                    y->right->parent = y;
                }
                moveNode(h, y);
                y->left = h->left;
                y->left->parent = y;
            }
            delete t;
           balance(y);
 }

The moveNode method moves the node pointed to by v into the position pointed to by u, while neatly handling our parent pointers:

      void moveNode(node *u, node* v) {
            if (u->parent == nullptr) {
                root = v;
            } else if (u == u->parent->left) {
                u->parent->left = v;
            } else {
                u->parent->right = v;
            }
            if (v != nullptr) {
                v->parent = u->parent;
            }
      } 

min() is of course, the standard method for obtaining the min node of a given tree:

node* min(node* h) {
      node* x = h;
      while (x->left != nullptr) x = x->left;
      return x;
}

As mentioned, balance() is the same as used in insertion, and covered in that article:

    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;
            }
        }

And that's it! Now that we have implemented insert, search, and erase for our AVL tree, stay tuned for the next installment in my iterative AVL tree series, where I will explain implementing forward and reverse iterators for our tree so that it can be a drop in replacement for std::map or set!!

 

---