Binary Trees

Introduction

In this lesson, we'll explore binary trees, their properties, and their usage in Rust. Binary trees are a fundamental data structure used in various applications, from databases to AI algorithms.

Key Points

• Binary Trees: A tree data structure where each node has at most two children, referred to as the left child and the right child.
• Types of Binary Trees: Full, Complete, and Binary Search Trees (BSTs).

Binary Trees

A binary tree is a hierarchical structure where each node has at most two children. It starts with a root node and each node can have a left and/or right child.

Basic Binary Tree Node

Here’s a basic implementation of a binary tree node in Rust:

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

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

    fn insert_left(&mut self, value: T) {
        self.left = Some(Box::new(TreeNode::new(value)));
    }

    fn insert_right(&mut self, value: T) {
        self.right = Some(Box::new(TreeNode::new(value)));
    }
}

fn main() {
    let mut root = TreeNode::new(1);
    root.insert_left(2);
    root.insert_right(3);

    if let Some(left) = &root.left {
        println!("Left child: {:?}", left);
    }
    if let Some(right) = &root.right {
        println!("Right child: {:?}", right);
    }
}

Code Explanation

• new: Creates a new node with a given value.
• insert_left: Adds a left child to the current node.
• insert_right: Adds a right child to the current node.

Binary Search Trees (BSTs)

A Binary Search Tree (BST) is a binary tree where each node follows the property: all nodes in the left subtree are less than the node’s value, and all nodes in the right subtree are greater than the node’s value.

BST Implementation

Here’s how you can implement a basic BST in Rust:

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

impl<T: Ord> BSTNode<T> {
    fn new(value: T) -> Self {
        BSTNode {
            value,
            left: None,
            right: None,
        }
    }

    fn insert(&mut self, value: T) {
        if value < self.value {
            if let Some(left) = &mut self.left {
                left.insert(value);
            } else {
                self.left = Some(Box::new(BSTNode::new(value)));
            }
        } else {
            if let Some(right) = &mut self.right {
                right.insert(value);
            } else {
                self.right = Some(Box::new(BSTNode::new(value)));
            }
        }
    }

    fn search(&self, value: T) -> bool {
        if value == self.value {
            true
        } else if value < self.value {
            self.left.as_ref().map_or(false, |node| node.search(value))
        } else {
            self.right.as_ref().map_or(false, |node| node.search(value))
        }
    }
}

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

    println!("BST Search 7: {}", bst.search(7));
    println!("BST Search 20: {}", bst.search(20));
}

Code Explanation

• insert: Adds a value to the BST while maintaining the BST property.
• search: Checks if a value exists in the BST.

Real World Examples

Binary Trees

Binary trees are used in various applications such as:

• Expression Trees: Used in compilers to represent expressions.
• Decision Trees: Used in machine learning for classification and regression tasks.
• File Systems: Some file systems use binary trees to manage directories and files efficiently.

Binary Search Trees (BSTs)

BSTs are commonly used in scenarios where you need to maintain a dynamic dataset with efficient searching, inserting, and deleting operations. For example:

• Database Indexes: Used to speed up data retrieval operations.
• Autocomplete Systems: BSTs can be used to quickly find possible completions for a prefix in a search query.

Conclusion

Binary trees and binary search trees are powerful data structures that offer efficient data management and retrieval. By implementing these structures in Rust, you can handle a wide range of applications and improve your understanding of data structures.