AVL Trees with Implementation in C++, Java, and Python

Before going through this, please read the following two articles that discuss about the binary search tree and self-balancing binary search tree.

Introduction

AVL trees are height balanced binary search trees. This means the height of the AVL tree is in the order of $\log (n)$. AVL tree keeps the height balanced using the following property.

The heights of the left and right subtrees differ by at most 1. If $h_l$ be the height of the left subtree and $h_r$ be the height of the right subtree, then,
$$|h_l - h_r| \le 1$$

Every node should follow the above property and the resulting tree is the AVL tree. If any of the node violates this property, the tree should be re-balanced to maintain the property. Now I am going to prove that the AVL property guarantees the height of the tree to be in the order of $\log (n)$.

Consider an AVL tree given in Figure 1. Let $h$ be the height of the tree and let $N_h$ denotes the number of nodes in the tree of height $h$.

Fig 1: An AVL tree of height $h$

The total number of nodes in the tree is the sum of the total number of nodes in the left subtree, the total number of nodes in the right subtree and the root node.
$$N_h = N_{h - 1} + N_{h - 2} + 1$$
This is a homogeneous recurrence relation that resembles the recurrence relation of Fibonacci number. The solution of this recurrence relation is
$$N_h = \frac {\varphi^h}{\sqrt{5}}$$
Where $\varphi$ is the golden ratio. If we take the $\log_{\varphi}$ on both sides, we get
$$h = 1.44 \log_2 (N_h)$$
This proves that the height of the AVL tree is in the order of $\log(n)$.

Balance factor

In a binary tree the balanced factor $(BF)$ of the node $x$ is the height $(h)$ difference between left $(LS)$ and right subtree $(RS)$ of $x$
$$BF(x) = h(RS(x)) - h(LS(x))$$

In an AVL tree, the balance factor must be -1, 0, or 1. If the balance factor of a node is greater than 1 (right heavy) or less than -1 (left heavy), the node needs to be rebalanced. Figure 2 shows a tree with balance factor.

Fig 2: A binary tree with balance factor

Figure 2 is not an AVL tree as some nodes have balance factor greater than 1.

AVL tree rotations

When the balance factor of a node is less than -1 or greater than 1, we perform tree rotations on the node. These rotations change the structure of the tree and make the tree balanced. There are four kind of rotations we do in the AVL tree. These are described below.

Left Rotation (LL)

Figure 3 illustrates the left rotation on AVL tree.

Fig 3: Left Rotation (LL)

The tree at the left side of Figure 3 is right heavy. To fix this, we must perform a left rotation on node $a$. This is done in the following steps.

$b$ becomes the new root
$a$ takes ownership of $b$’s child as its right child, or in this case, null
$b$ takes ownership of $a$ as its left child.

In AVL tree, we perform the left rotation (LL) on node $x$ when

Node $x$ is right heavy
Node $x$’s right subtree is not left heavy

Right Rotation (RR)

Figure 4 illustrates the right rotation.

Fig 4: Right Rotation (RR)

We fix the tree on the left side of Figure 4 using following steps.

$b$ becomes the new root.
$c$ takes ownership of $b$’s right child, as its left child. In this case, that value is null.
$b$ takes ownership of $c$, as its right child.

In AVL tree, we perform the right rotation (RR) on node $x$ when

Node $x$ is left heavy
Node $x$’s left subtree is not right heavy

Left-Right Rotation (LR)

Sometimes a single rotation is not sufficient to balance an unbalanced tree. Consider a tree given in Figure 5.

Fig 5: An unbalanced tree. Node a is right heavy with BF 2

Since node $a$ is right heavy, first thing that comes in mind is to perform the left rotation (LL). Let’s see what happens if we do the left rotation on node $a$.

Fig 6: Performing left rotation on the root node

As we can see in the figure, the tree after the left rotation is still un-balanced. Therefore the single left operation is not effective in this case. To fix this we do the following using two step rotation.

Perform the right rotation on the right subtree. In the above figure, perform the right rotation on node $c$ (NOT $a$).
Perform the left rotation on the root node.

This is illustrated in Figure 7 below.

Fig 7: Illustrating the left-right rotation

We perform the left right rotation (LR) on node $x$ when

Node $x$ is right heavy
Node $x$’s right subtree is left heavy

Right-Left Rotation (RL)

RL rotation is symmetric to LR rotation. In RL rotation, we do the following

Perform the left rotation on the left subtree.
Perform the right rotation on the root node.

This is illustrated in Figure 8.

Fig 8: Illustrating the right-left rotation

We perform the right left rotation (LR) on node $x$ when

Node $x$ is left heavy
Node $x$’s left subtree is right heavy

Operations on AVL tree

AVL tree supports all the dynamic set operations. In this post, I am going to discuss about insertion and deletion operations only. The rest of the operations are similar to the ordinary binary search tree.

Insertion

To insert a node $x$ on an AVL tree, we do the following.

Insert node $x$ using the ordinary binary search tree insertion logic.
Update the balance factors of all the ancestral nodes of $x$.
If the balance factor is other than -1, 0, 1, balance the tree using the tree rotations.

Figure 9 illustrates the insertion operation with the help of an example tree.

Fig 9: Illustrating the insertion operation

Deletion

Deletion operation is same as the insertion operation. To delete a node $x$ from the AVL tree, we first delete it using the ordinary binary search tree deletion logic. After that we update the balance factor of the ancestral node of $x$ and perform the tree rotation if the tree is unbalanced.

Complexity

The running time of all the operations in AVL tree is $O(\log n)$. This is because AVL tree guarantees the height of the tree is always in the order of $\log n$.

Implementation

Node

The AVL tree node has the following properties.

data: It contains the key of the node
parent: It contains the reference to the parent node.
left: It contains the reference to the left subtree.
right: It contains the reference to the right subtree.
bf: It contains the balance factor of the node. This is the additional property in the AVL tree which is not present in ordinary BST.

A C++ implementation of the node is given below.

// data structure that represents a node in the tree
struct Node {
	int data; // holds the key
	Node *parent; // pointer to the parent
	Node *left; // pointer to left child
	Node *right; // pointer to right child
	int bf; // balance factor of the node
};

Left Rotate

When we do the left rotation on a node $x$, the new balance factor for node $x$ and $y$ can be written as.
Fig 10: Illustration the left tree rotation

newBal(x) = oldBal(x) - 1 - max(0, oldBal(y))
newBal(y) = oldBal(y) - 1 + min(0, newBal(x))

This can be derived easily by looking at the figure 10. Let $h_x$ denotes the height of node $x$.

oldBal(x) = $h_y - h_{\alpha}$
newBal(x) = $h_{\beta} - h_{\alpha}$

Combining these two relations, we get

newBal(x) = oldBal(x) - $(h_y - h_{\beta})$
or, newBal(x) = oldBal(x) - $(1 + \max(h_{\beta}, h_{\gamma}) - h_{\beta})$
or, newBal(x) = oldBal(x) - $(1 + \max(0, h_{\gamma} - h_{\beta}))$
or, newBal(x) = oldBal(x) - 1 - max(0, oldBal(y))

Similarly we can derive the value of new balance factor of $y$. The C++ implementation of left rotation is given below.

// rotate left at node x
void leftRotate(NodePtr x) {
	NodePtr y = x->right;
	x->right = y->left;
	if (y->left != nullptr) {
		y->left->parent = x;
	}
	y->parent = x->parent;
	if (x->parent == nullptr) {
		this->root = y;
	} else if (x == x->parent->left) {
		x->parent->left = y;
	} else {
		x->parent->right = y;
	}
	y->left = x;
	x->parent = y;

	// update the balance factor
	x->bf = x->bf - 1 - max(0, y->bf);
	y->bf = y->bf - 1 + min(0, x->bf);
}

Right rotate

The right rotation is symmetric to the left rotation. When we perform the right rotation on node $x$ whose left child is node $y$, the new balance factor for $x$ and $y$ will be.

newBal(x) = oldBal(x) + 1 - max(0, oldBal(y))
newBal(y) = oldBal(y) + 1 + max(0, newBal(x))

The C++ implementation is given below.

// rotate right at node x
void rightRotate(NodePtr x) {
	NodePtr y = x->left;
	x->left = y->right;
	if (y->right != nullptr) {
		y->right->parent = x;
	}
	x->parent = y->parent;
	if (x->parent == nullptr) {
		this->root = y;
	} else if (x == x->parent->right) {
		x->parent->right = y;
	} else {
		x->parent->left = y;
	}
	y->right = x;
	x->parent = y;

	// update the balance factor
	x->bf = x->bf + 1 - min(0, y->bf);
	y->bf = y->bf + 1 + max(0, x->bf);
}

Re-balancing

When the balance factor of a node is greater than 1 or less than -1, we perform the rebalancing using the logic shown below.

// rebalance the tree
void rebalance(NodePtr node) {
	if (node->bf > 0) {
		if (node->right->bf < 0) {
			rightRotate(node->right);
			leftRotate(node);
		} else {
			leftRotate(node);
		}
	} else if (node->bf < 0) {
		if (node->left->bf > 0) {
			leftRotate(node->left);
			rightRotate(node);
		} else {
			rightRotate(node);
		}
	}
}

The full implementation in C++, Python, and Java is available on Github.

C++ Implementation.

Java Implementation.

Python Implementation.