Iterative AVL Trees  Deletion
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 rebalancing 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!!

A Different Take on Merge Sort: Binary Search Trees?

Deleting Entries From OpenAddress Hash tables

Transform any Binary Search Tree in to a Sorted Linked List

From Regular Expressions To NFA by way of Abstract Syntax Trees: Thompsons Construction

Extending Sedgewick's explicit Digraph NFA

Iterative Inorder B Tree Traversal

Simple DB Migration with JDBC

Welcome to CodeBlahger, A Blahging Platform for Programmers.

The Façade Pattern

The Interpreter Pattern: Implementing Interpreters the OOP way
Leave A Comment