silvercoder007

Posted on Nov 5

Mastering Trees in Rust: From Novice to Ninja

#algorithms #beginners #tutorial #rust

Welcome to Mastering Trees in Rust! If you've ever wondered how to organize data hierarchically—like a family tree or a company's org chart—this guide is for you. We'll start from absolute basics, assuming you know nothing about trees, and build up to advanced self-balancing trees like AVL and Red-Black. Along the way, we'll code everything in Rust, with plenty of examples, ASCII diagrams, and tests to ensure our code works flawlessly.

Trees are powerful data structures for storing and retrieving data efficiently. By the end, you'll implement your own tree library and understand when to use each type.

What Are Trees? The Basics

Imagine a tree in nature: it has a root, branches, and leaves. In computer science, a tree is a hierarchical data structure where each element (called a node) has a parent (except the top one) and zero or more children.

Key Terminology

Root: The top node with no parent.
Node: Each element in the tree, containing data and links to children.
Leaf: A node with no children.
Internal Node: A node with at least one child.
Parent/Child: Relationships between nodes.
Subtree: A node and all its descendants.
Depth: Number of ancestors (root is depth 0).
Height: Maximum depth in the tree.
Level: Nodes at the same depth.

Here's a simple ASCII diagram of a tree:

       Root (A)
      /     \
    B         C
   / \       / \
  D   E     F   G

Root: A
Leaves: D, E, F, G
Internal nodes: A, B, C
Height: 2 (from A to D/E/F/G)

Trees are non-linear, unlike arrays or linked lists, making them great for hierarchical data.

Why Use Trees in Rust?

Rust's ownership and borrowing make trees safe and efficient. No null pointer dereferences or memory leaks! We'll use structs, enums, and smart pointers like Rc (Reference Counting) for shared ownership.

Setting Up: Basic Tree Node in Rust

Let's start with a simple binary tree node. A binary tree has at most two children per node.

use std::rc::Rc;
use std::cell::RefCell;

// A basic tree node
#[derive(Debug)]
struct TreeNode<T> {
    value: T,
    left: Option<Rc<RefCell<TreeNode<T>>>>,
    right: Option<Rc<RefCell<TreeNode<T>>>>,
}

impl<T> TreeNode<T> {
    fn new(value: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(TreeNode {
            value,
            left: None,
            right: None,
        }))
    }
}

Rc<RefCell<TreeNode<T>>>: Rc allows shared ownership, RefCell enables mutable borrowing.
Option: Handles absence of children safely.

Example: Create a simple tree.

fn main() {
    let root = TreeNode::new("A");
    let left = TreeNode::new("B");
    let right = TreeNode::new("C");

    root.borrow_mut().left = Some(left);
    root.borrow_mut().right = Some(right);

    println!("{:?}", root); // Prints the tree structure
}

Test it:

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

    #[test]
    fn test_basic_node() {
        let node = TreeNode::new(42);
        assert_eq!(node.borrow().value, 42);
        assert!(node.borrow().left.is_none());
    }
}

Run with cargo test.

Binary Search Trees (BST): Ordered Trees

A BST is a binary tree where left children < parent < right children. This enables fast searches (O(log n) average case).

BST Node and Operations

#[derive(Debug)]
struct BST<T: Ord> {
    root: Option<Rc<RefCell<TreeNode<T>>>>,
}

impl<T: Ord> BST<T> {
    fn new() -> Self {
        BST { root: None }
    }

    fn insert(&mut self, value: T) {
        let new_node = TreeNode::new(value);
        if let Some(root) = &self.root {
            Self::insert_node(root.clone(), new_node);
        } else {
            self.root = Some(new_node);
        }
    }

    fn insert_node(node: Rc<RefCell<TreeNode<T>>>, new_node: Rc<RefCell<TreeNode<T>>>) {
        let mut node_borrow = node.borrow_mut();
        let new_val = new_node.borrow().value.clone();
        if new_val < node_borrow.value {
            if let Some(left) = &node_borrow.left {
                Self::insert_node(left.clone(), new_node);
            } else {
                node_borrow.left = Some(new_node);
            }
        } else {
            if let Some(right) = &node_borrow.right {
                Self::insert_node(right.clone(), new_node);
            } else {
                node_borrow.right = Some(new_node);
            }
        }
    }

    fn search(&self, value: &T) -> bool {
        Self::search_node(&self.root, value)
    }

    fn search_node(node: &Option<Rc<RefCell<TreeNode<T>>>>, value: &T) -> bool {
        if let Some(n) = node {
            let n_borrow = n.borrow();
            if *value == n_borrow.value {
                true
            } else if *value < n_borrow.value {
                Self::search_node(&n_borrow.left, value)
            } else {
                Self::search_node(&n_borrow.right, value)
            }
        } else {
            false
        }
    }
}

Example: Build and search a BST.

fn main() {
    let mut bst = BST::new();
    bst.insert(10);
    bst.insert(5);
    bst.insert(15);
    bst.insert(3);

    println!("Found 5: {}", bst.search(&5)); // true
    println!("Found 20: {}", bst.search(&20)); // false
}

ASCII Diagram of BST:

Tests:

#[test]
fn test_bst_insert_and_search() {
    let mut bst = BST::new();
    bst.insert(10);
    bst.insert(5);
    assert!(bst.search(&10));
    assert!(bst.search(&5));
    assert!(!bst.search(&1));
}

Tree Traversals: Visiting Every Node

Traversals visit all nodes in a specific order.

In-Order Traversal (Left, Root, Right)

impl<T: Ord + Clone> BST<T> {
    fn in_order(&self) -> Vec<T> {
        let mut result = Vec::new();
        Self::in_order_node(&self.root, &mut result);
        result
    }

    fn in_order_node(node: &Option<Rc<RefCell<TreeNode<T>>>>, result: &mut Vec<T>) {
        if let Some(n) = node {
            let n_borrow = n.borrow();
            Self::in_order_node(&n_borrow.left, result);
            result.push(n_borrow.value.clone());
            Self::in_order_node(&n_borrow.right, result);
        }
    }
}

Example: In-order on our BST: [3, 5, 10, 15]

Pre-Order (Root, Left, Right) and Post-Order (Left, Right, Root)

Add similar methods. Pre-order: [10, 5, 3, 15], Post-order: [3, 5, 15, 10]

Advanced: Min, Max, and Removal

impl<T: Ord + Clone> BST<T> {
    fn min(&self) -> Option<T> {
        Self::min_node(&self.root)
    }

    fn min_node(node: &Option<Rc<RefCell<TreeNode<T>>>>) -> Option<T> {
        if let Some(n) = node {
            let n_borrow = n.borrow();
            if n_borrow.left.is_some() {
                Self::min_node(&n_borrow.left)
            } else {
                Some(n_borrow.value.clone())
            }
        } else {
            None
        }
    }

    fn remove(&mut self, value: &T) {
        self.root = Self::remove_node(self.root.take(), value);
    }

    fn remove_node(node: Option<Rc<RefCell<TreeNode<T>>>>, value: &T) -> Option<Rc<RefCell<TreeNode<T>>>> {
        if let Some(n) = node {
            let mut n_borrow = n.borrow_mut();
            if *value < n_borrow.value {
                n_borrow.left = Self::remove_node(n_borrow.left.take(), value);
                Some(n)
            } else if *value > n_borrow.value {
                n_borrow.right = Self::remove_node(n_borrow.right.take(), value);
                Some(n)
            } else {
                // Node to remove
                if n_borrow.left.is_none() {
                    return n_borrow.right.take();
                } else if n_borrow.right.is_none() {
                    return n_borrow.left.take();
                } else {
                    // Two children: replace with min of right subtree
                    let min_val = Self::min_node(&n_borrow.right).unwrap();
                    n_borrow.value = min_val.clone();
                    n_borrow.right = Self::remove_node(n_borrow.right.take(), &min_val);
                    Some(n)
                }
            }
        } else {
            None
        }
    }
}

Tests:

#[test]
fn test_bst_remove() {
    let mut bst = BST::new();
    bst.insert(10);
    bst.insert(5);
    bst.remove(&5);
    assert!(!bst.search(&5));
    assert!(bst.search(&10));
}

Self-Balancing Trees: AVL Trees

BSTs can become skewed (like a linked list), ruining O(log n) performance. AVL trees keep height difference ≤1.

AVL Node with Height

#[derive(Debug)]
struct AVLNode<T> {
    value: T,
    height: i32,
    left: Option<Rc<RefCell<AVLNode<T>>>>,
    right: Option<Rc<RefCell<AVLNode<T>>>>,
}

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

    fn height(node: &Option<Rc<RefCell<AVLNode<T>>>>) -> i32 {
        node.as_ref().map_or(0, |n| n.borrow().height)
    }

    fn update_height(node: &Rc<RefCell<AVLNode<T>>>) {
        let left_h = Self::height(&node.borrow().left);
        let right_h = Self::height(&node.borrow().right);
        node.borrow_mut().height = 1 + left_h.max(right_h);
    }

    fn balance_factor(node: &Rc<RefCell<AVLNode<T>>>) -> i32 {
        Self::height(&node.borrow().right) - Self::height(&node.borrow().left)
    }

    // Rotations: LL, RR, LR, RL (implement similar to original)
    fn rotate_right(y: Rc<RefCell<AVLNode<T>>>) -> Rc<RefCell<AVLNode<T>>> {
        let x = y.borrow_mut().left.take().unwrap();
        let t2 = x.borrow_mut().right.take();
        y.borrow_mut().left = t2;
        x.borrow_mut().right = Some(y.clone());
        Self::update_height(&y);
        Self::update_height(&x);
        x
    }

    // Add insert with balancing...
}

For full AVL, implement insert with rotations. (Space constraints; expand in real code.)

Red-Black Trees: Another Balancer

Red-Black trees use colors to ensure balance. Rules: Root black, no two reds adjacent, equal black nodes per path.

Similar to AVL but with color-based balancing.

Conclusion and Testing

Trees are versatile! Use BST for ordered data, AVL/Red-Black for balance. Always test:

#[test]
fn comprehensive_test() {
    let mut bst = BST::new();
    for i in 0..10 {
        bst.insert(i);
    }
    assert_eq!(bst.in_order(), (0..10).collect::<Vec<_>>());
    bst.remove(&5);
    assert!(!bst.search(&5));
}

Run cargo test to verify. Happy coding!

Top comments (1)

Some comments may only be visible to logged-in visitors. Sign in to view all comments.