Self Balancing Binary Search Tree (AVL Tree)

An AVL tree is a self-balancing binary search tree. Unlike a regular BST, an AVL tree automatically maintains its height balance after every insertion and deletion. This guarantees logarithmic time complexity for search, insertion, and deletion operations.

The key idea behind AVL trees is rotation - local restructuring of the tree to keep it balanced.

Why AVL Trees Exist

A standard BST can degrade into a linked list if values are inserted in sorted order:

1 → 2 → 3 → 4 → 5

This leads to O(n) operations.

AVL trees prevent this by enforcing a balance rule at every node.

Balance Factor

For each node in an AVL tree:

balance_factor = height(left subtree) - height(right subtree)

An AVL tree maintains:

balance_factor ∈ { -1, 0, +1 }

If the balance factor goes outside this range, the tree must be rebalanced.

Rotations

Rotations are local transformations that restore balance while preserving BST ordering.

There are four cases:

1. Left-Left (LL) Case

Occurs when a node becomes unbalanced after insertion into the left subtree of the left child.

Fix: Right rotation

    z            y
   /            / \
  y     →      x   z
 /
x

2. Right-Right (RR) Case

Occurs when insertion happens in the right subtree of the right child.

Fix: Left rotation

z               y
 \             / \
  y     →      z   x
   \
    x

3. Left-Right (LR) Case

Insertion in the right subtree of the left child.

Fix:

1. Left rotation on left child
2. Right rotation on the node

4. Right-Left (RL) Case

Insertion in the left subtree of the right child.

Fix:

1. Right rotation on right child
2. Left rotation on the node

Rust Implementation

Below is a simplified AVL tree implementation focusing on insertion and rebalancing.

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub height: i32,
    pub left: Option<Box<Node<T>>>,
    pub right: Option<Box<Node<T>>>,
}

impl<T: Ord + Clone> Node<T> {
    pub fn new(value: T) -> Self {
        Node {
            value,
            height: 1,
            left: None,
            right: None,
        }
    }

    fn height(node: &Option<Box<Node<T>>>) -> i32 {
        node.as_ref().map_or(0, |n| n.height)
    }

    fn update_height(&mut self) {
        self.height = 1 + std::cmp::max(
            Self::height(&self.left),
            Self::height(&self.right),
        );
    }

    fn balance_factor(&self) -> i32 {
        Self::height(&self.left) - Self::height(&self.right)
    }

    fn rotate_right(mut y: Box<Node<T>>) -> Box<Node<T>> {
        let mut x = y.left.take().unwrap();
        y.left = x.right.take();
        y.update_height();
        x.right = Some(y);
        x.update_height();
        x
    }

    fn rotate_left(mut x: Box<Node<T>>) -> Box<Node<T>> {
        let mut y = x.right.take().unwrap();
        x.right = y.left.take();
        x.update_height();
        y.left = Some(x);
        y.update_height();
        y
    }

    pub fn insert(mut node: Box<Node<T>>, value: &T) -> Box<Node<T>> {
        if value < &node.value {
            node.left = match node.left.take() {
                Some(left) => Some(Self::insert(left, value)),
                None => Some(Box::new(Node::new(value.clone()))),
            };
        } else if value > &node.value {
            node.right = match node.right.take() {
                Some(right) => Some(Self::insert(right, value)),
                None => Some(Box::new(Node::new(value.clone()))),
            };
        } else {
            return node;
        }

        node.update_height();
        let balance = node.balance_factor();

        // Left Left
        if balance > 1 && value < &node.left.as_ref().unwrap().value {
            return Self::rotate_right(node);
        }

        // Right Right
        if balance < -1 && value > &node.right.as_ref().unwrap().value {
            return Self::rotate_left(node);
        }

        // Left Right
        if balance > 1 && value > &node.left.as_ref().unwrap().value {
            node.left = Some(Self::rotate_left(node.left.take().unwrap()));
            return Self::rotate_right(node);
        }

        // Right Left
        if balance < -1 && value < &node.right.as_ref().unwrap().value {
            node.right = Some(Self::rotate_right(node.right.take().unwrap()));
            return Self::rotate_left(node);
        }

        node
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_balances_tree() {
        let mut root = Box::new(Node::new(10));
        root = Node::insert(root, &20);
        root = Node::insert(root, &30);

        assert_eq!(root.value, 20);
    }
}

Example Usage

fn main() {
    let mut root = Box::new(Node::new(30));
    root = Node::insert(root, &20);
    root = Node::insert(root, &10); // triggers rotation

    println!("{:#?}", root);
}

Time and Space Complexity

AVL trees guarantee balance, so performance is predictable.

Time Complexity

Space Complexity

Key Takeaways

• AVL trees maintain balance using rotations
• Height difference is strictly limited
• More rotations than Red-Black trees, but faster lookups
• Guaranteed logarithmic performance

Playground Links

Rust - Self-balancing BST