AVL Tree Implementation in Rust

1. Introduction

An AVL tree (Adelson-Velsky and Landis tree) is a self-balancing binary search tree where the difference between the heights of the left and right subtrees (balance factor) for every node is at most one. This ensures that the tree remains approximately balanced, leading to O(log n) search times.

2. Implementation Steps

1. Define a Node struct with attributes value, height, left, and right.

2. Define the AVLTree struct that will have a root node.

3. Implement a new function to initialize an empty tree.

4. Implement an insert function to add a node while maintaining balance.

5. Define helper functions to calculate the height and balance factor of nodes.

6. Define rotations to ensure the tree remains balanced during insertions.

3. Implementation in Rust Programming

type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
    value: T,
    height: isize,
    left: Link<T>,
    right: Link<T>,
}
pub struct AVLTree<T> {
    root: Link<T>,
}
impl<T: Ord> AVLTree<T> {
    pub fn new() -> Self {
        AVLTree { root: None }
    }
    fn height(&self, node: &Link<T>) -> isize {
        match node {
            None => 0,
            Some(ref boxed_node) => boxed_node.height,
        }
    }
    fn balance_factor(&self, node: &Link<T>) -> isize {
        self.height(&node.as_ref().unwrap().left) - self.height(&node.as_ref().unwrap().right)
    }
    fn rotate_right(&self, mut y: Box<Node<T>>) -> Box<Node<T>> {
        let mut x = y.left.take().unwrap();
        y.left = x.right.take();
        x.right = Some(y);
        x.height = 1 + std::cmp::max(self.height(&x.left), self.height(&x.right));
        x.right.as_mut().unwrap().height = 1 + std::cmp::max(self.height(&x.right.as_ref().unwrap().left), self.height(&x.right.as_ref().unwrap().right));
        x
    }
    fn rotate_left(&self, mut x: Box<Node<T>>) -> Box<Node<T>> {
        let mut y = x.right.take().unwrap();
        x.right = y.left.take();
        y.left = Some(x);
        y.height = 1 + std::cmp::max(self.height(&y.left), self.height(&y.right));
        y.left.as_mut().unwrap().height = 1 + std::cmp::max(self.height(&y.left.as_ref().unwrap().left), self.height(&y.left.as_ref().unwrap().right));
        y
    }
    pub fn insert(&mut self, value: T) {
        self.root = self.insert_rec(self.root.take(), value);
    }
    fn insert_rec(&self, node: Link<T>, value: T) -> Link<T> {
        let mut node = match node {
            None => return Some(Box::new(Node {
                value,
                height: 1,
                left: None,
                right: None,
            })),
            Some(mut boxed_node) => {
                if value < boxed_node.value {
                    boxed_node.left = self.insert_rec(boxed_node.left, value);
                } else if value > boxed_node.value {
                    boxed_node.right = self.insert_rec(boxed_node.right, value);
                } else {
                    return Some(boxed_node); // Duplicates not allowed
                }
                boxed_node
            }
        };
        node.height = 1 + std::cmp::max(self.height(&node.left), self.height(&node.right));
        let balance = self.balance_factor(&Some(node.as_ref().clone()));
        // Left Left Case
        if balance > 1 && value < node.left.as_ref().unwrap().value {
            return Some(self.rotate_right(node));
        }
        // Right Right Case
        if balance < -1 && value > node.right.as_ref().unwrap().value {
            return Some(self.rotate_left(node));
        }
        // Left Right Case
        if balance > 1 && value > node.left.as_ref().unwrap().value {
            node.left = Some(self.rotate_left(node.left.take().unwrap()));
            return Some(self.rotate_right(node));
        }
        // Right Left Case
        if balance < -1 && value < node.right.as_ref().unwrap().value {
            node.right = Some(self.rotate_right(node.right.take().unwrap()));
            return Some(self.rotate_left(node));
        }
        Some(node)
    }
}
fn main() {
    let mut avl = AVLTree::new();
    avl.insert(10);
    avl.insert(20);
    avl.insert(30);
    avl.insert(40);
    avl.insert(50);
    avl.insert(25);
    // Note: Printing is omitted for brevity. You can implement an in_order function similar to the BST for visualization.
}

Output:

// The output is omitted in this example since we haven't implemented a print or in-order function. The main function demonstrates how to insert values into the AVL tree.

Explanation:

1. The Node struct represents each element in the AVL tree. It includes attributes for value, height, left child, and right child.

2. The AVLTree struct acts as a container for the tree with a root node.

3. The new function initializes an empty AVL tree.

4. The height function returns the height of a node, used to calculate balance.

5. The balance_factor function computes the difference in height between the left and right children of a node.

6. The rotate_right and rotate_left functions are used to perform rotations on the tree to keep it balanced.

7. The insert function inserts a new value into the tree, and ensures that the tree remains balanced after every insertion using the helper function insert_rec.