Self Balancing Binary Search Tree - Deletion

Deletion in an AVL tree is more complex than insertion because removing a node can unbalance the tree at multiple levels. After deleting a node using standard BST rules, the tree must be rebalanced by updating heights and performing rotations where necessary.

The key difference from a regular BST is that rebalancing may propagate upward toward the root.

Deletion Strategy Overview

AVL deletion follows two major steps:

1. Perform standard BST deletion
2. Rebalance the tree while backtracking

At each node, we:

• Update the node’s height
• Calculate the balance factor
• Apply rotations if the balance factor is outside [-1, 1]

BST Deletion Recap (AVL Context)

Just like BST deletion, AVL deletion has three cases:

Case 1 - Leaf Node

Remove the node directly.

Case 2 - One Child

Replace the node with its child.

Case 3 - Two Children

• Find the in-order successor (minimum in the right subtree)
• Replace the node’s value
• Delete the successor recursively

After this structural change, AVL rebalancing begins.

Rebalancing After Deletion

Once a node is deleted, four imbalance cases can occur:

Unlike insertion, deletion can cause imbalance even if the child’s balance factor is 0.

Rust Implementation

This implementation extends the previous AVL tree by adding a delete operation with full rebalancing logic.

#[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
    }

    fn min_value_node(node: &Box<Node<T>>) -> &Box<Node<T>> {
        let mut current = node;
        while let Some(ref left) = current.left {
            current = left;
        }
        current
    }
    
    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
    }

    pub fn delete(mut node: Box<Node<T>>, value: &T) -> Option<Box<Node<T>>> {
        if value < &node.value {
            node.left = node.left.take().and_then(|n| Self::delete(n, value));
        } else if value > &node.value {
            node.right = node.right.take().and_then(|n| Self::delete(n, value));
        } else {
            match (node.left.take(), node.right.take()) {
                (None, None) => return None,
                (Some(child), None) | (None, Some(child)) => return Some(child),
                (Some(left), Some(right)) => {
                    let successor = Self::min_value_node(&right);
                    node.value = successor.value.clone();
                    node.right = Self::delete(right, &node.value);
                    node.left = Some(left);
                }
            }
        }

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

        // Left Left
        if balance > 1 && node.left.as_ref().unwrap().balance_factor() >= 0 {
            return Some(Self::rotate_right(node));
        }

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

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

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

        Some(node)
    }
}

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

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

        let root = Node::delete(root, &20).unwrap();
        assert!(root.value == 30 || root.value == 10);
    }
}

Example Usage

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

    let root = Node::delete(root, &30);

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

Time and Space Complexity

AVL deletion guarantees balance, so complexity remains logarithmic.

Time Complexity

Space Complexity

Key Differences from BST Deletion

Playground Links

Rust - Self-balancing BST - Deletion