AVL Tree

An AVL tree, named after Adelson Velsky and Landis, is a self-balancing binary search tree.

Properties

Height of an AVL tree is:

$$O(\log n)$$

Where n is the number of nodes.

Height balanced

The height difference in between the left subtree and the right subtree must be at most one. This ensures that all operations in the tree are at a log(n) time complexity.

Rotations

Balancing of the tree occurs via rotations.

How would you rotate a stick shaped tree into a perfect Binary Tree?

Implementation

One of the possible implementations for such a node of such a tree could be something like this:

enum balance_type{ LEFT_HEAVY = -1, BALANCED = 0, RIGHT_HEAVY = 1};
 
class AVLNode {
	public: 
		int data;
		AVLNode* left;
		AVLNode* right;
		balance_type balance;
}

Where it effectively just has an extra field that denotes the balance of that node’s subtree.

Operations

Insertion

One of the most effective ways of ensuring AVL balance is to never let it become unbalanced upon insertion in the first place.

Insertion starts with a regular BST insertion.

Rebalancing

If we encounter the case where an insertion would cause an AVL tree to become imabalanaced, we can perform rebalancing based on the type of imbalance. There are four different types of AVL imbalance:

LEFT LEFT

Left left imbalance looks like this: And is solved by a right rotation at C.

This can be implemented with an algorithm like the following:

Node* leftRotate(Node* y) {
    Node* x = y->right;
    Node* T2 = x->left;
 
    // Perform rotation
    x->left = y;
    y->right = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    // New root
    return x;
}

RIGHT RIGHT

Right right imbalance looks like this: And is solved by a left rotation at A.

This can be implemented with an algorithm like the following:

Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    // New root
    return x;
}
 

LEFT RIGHT

RIGHT LEFT