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.
I had initially resisted using parent pointers, as a) I’ve always implemented my search trees sans parent pointers, and b) I held the false belief that their use would complicate and clutter up the code. The truth of the matter is that while performing tree rotations while maintaining parent pointers IS more complicated we don’t need to reinvent the wheel: the rotation algorithms from CLRS in the section on Red Black Tree’s which utilize parent pointers serves as a drop in replacement. This enabling me to implement the re-balancing algorithm in an incredibly straight forward translation of the recursive version by simply walking the parent pointers. When compared to my previous attempts using a stack to store the path from root to leaf during insertion instead of parent pointers this is, in my opinion at least, a far more elegant solution.
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!
