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

Bottom Up AVL Tree: The OG SelfBalancing Binary Search Tree

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
Leave A Comment