Day 59: Advanced Tree Structures

Table of Contents

Day 59: Advanced Tree Structures #

Welcome to Day 59 of our 60 Days of Coding Algorithm Challenge! Today, we’ll delve deep into advanced tree structures, building upon the foundational tree concepts we’ve explored in previous lessons. We’ll focus on three powerful tree structures: AVL Trees, Red-Black Trees, and B-Trees.

1. AVL Trees #

AVL trees, named after their inventors Adelson-Velsky and Landis, are self-balancing binary search trees. They maintain their balance by ensuring that the height difference between left and right subtrees (balance factor) for every node is at most 1.

Key Properties: #

  1. For each node, the heights of its left and right subtrees differ by at most 1.
  2. Every subtree is an AVL tree.
  3. The height of an AVL tree with n nodes is O(log n).

Implementation: #

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def __init__(self):
        self.root = None

    def height(self, node):
        if not node:
            return 0
        return node.height

    def balance_factor(self, node):
        if not node:
            return 0
        return self.height(node.left) - self.height(node.right)

    def update_height(self, node):
        if not node:
            return
        node.height = 1 + max(self.height(node.left), self.height(node.right))

    def right_rotate(self, y):
        x = y.left
        T2 = x.right
        x.right = y
        y.left = T2
        self.update_height(y)
        self.update_height(x)
        return x

    def left_rotate(self, x):
        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2
        self.update_height(x)
        self.update_height(y)
        return y

    def insert(self, root, key):
        if not root:
            return AVLNode(key)
        if key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)
        
        self.update_height(root)
        balance = self.balance_factor(root)
        
        # Left Left Case
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)
        # Right Right Case
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)
        # Left Right Case
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        # Right Left Case
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)
        
        return root

    def insert_key(self, key):
        self.root = self.insert(self.root, key)

    def inorder_traversal(self, root):
        if not root:
            return
        self.inorder_traversal(root.left)
        print(root.key, end=" ")
        self.inorder_traversal(root.right)

# Example usage
avl_tree = AVLTree()
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
    avl_tree.insert_key(key)

print("Inorder traversal of the AVL tree:")
avl_tree.inorder_traversal(avl_tree.root)

Time Complexity: #

  • Insertion: O(log n)
  • Deletion: O(log n)
  • Search: O(log n)

Space Complexity: #

O(n) for storing n nodes

2. Red-Black Trees #

Red-Black trees are another type of self-balancing binary search tree. They maintain balance through a set of properties that ensure the tree remains approximately balanced during insertions and deletions.

Key Properties: #

  1. Every node is either red or black.
  2. The root is always black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.

Implementation: #

class Color:
    RED = 1
    BLACK = 2

class RBNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None
        self.color = Color.RED

class RedBlackTree:
    def __init__(self):
        self.NIL = RBNode(0)
        self.NIL.color = Color.BLACK
        self.root = self.NIL

    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.NIL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.NIL:
            y.right.parent = x
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y

    def insert(self, key):
        node = RBNode(key)
        node.left = self.NIL
        node.right = self.NIL
        y = None
        x = self.root

        while x != self.NIL:
            y = x
            if node.key < x.key:
                x = x.left
            else:
                x = x.right

        node.parent = y
        if y == None:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

        self.insert_fixup(node)

    def insert_fixup(self, k):
        while k.parent and k.parent.color == Color.RED:
            if k.parent == k.parent.parent.left:
                u = k.parent.parent.right
                if u.color == Color.RED:
                    k.parent.color = Color.BLACK
                    u.color = Color.BLACK
                    k.parent.parent.color = Color.RED
                    k = k.parent.parent
                else:
                    if k == k.parent.right:
                        k = k.parent
                        self.left_rotate(k)
                    k.parent.color = Color.BLACK
                    k.parent.parent.color = Color.RED
                    self.right_rotate(k.parent.parent)
            else:
                u = k.parent.parent.left
                if u.color == Color.RED:
                    k.parent.color = Color.BLACK
                    u.color = Color.BLACK
                    k.parent.parent.color = Color.RED
                    k = k.parent.parent
                else:
                    if k == k.parent.left:
                        k = k.parent
                        self.right_rotate(k)
                    k.parent.color = Color.BLACK
                    k.parent.parent.color = Color.RED
                    self.left_rotate(k.parent.parent)
            if k == self.root:
                break
        self.root.color = Color.BLACK

    def inorder_traversal(self, node):
        if node != self.NIL:
            self.inorder_traversal(node.left)
            print(node.key, end=" ")
            self.inorder_traversal(node.right)

# Example usage
rb_tree = RedBlackTree()
keys = [7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13]
for key in keys:
    rb_tree.insert(key)

print("Inorder traversal of the Red-Black tree:")
rb_tree.inorder_traversal(rb_tree.root)

Time Complexity: #

  • Insertion: O(log n)
  • Deletion: O(log n)
  • Search: O(log n)

Space Complexity: #

O(n) for storing n nodes

3. B-Trees #

B-Trees are self-balancing tree data structures that maintain sorted data and allow searches, insertions, and deletions in logarithmic time. They are optimized for systems that read and write large blocks of data, such as disk-based storage systems.

Key Properties: #

  1. All leaves are at the same depth.
  2. A non-leaf node with k children contains k-1 keys.
  3. Each node (except root) has at least t-1 keys and at most 2t-1 keys, where t is the minimum degree of the B-tree.
  4. The root has at least 2 children if it is not a leaf node.
  5. A non-leaf node with k keys has k+1 children.

Implementation: #

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.children = []

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t  # Minimum degree

    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            new_root = BTreeNode()
            new_root.children.insert(0, root)
            self.split_child(new_root, 0)
            self.root = new_root
            self.insert_non_full(new_root, k)
        else:
            self.insert_non_full(root, k)

    def insert_non_full(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append(None)
            while i >= 0 and k < x.keys[i]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k < x.keys[i]:
                i -= 1
            i += 1
            if len(x.children[i].keys) == (2 * self.t) - 1:
                self.split_child(x, i)
                if k > x.keys[i]:
                    i += 1
            self.insert_non_full(x.children[i], k)

    def split_child(self, x, i):
        t = self.t
        y = x.children[i]
        z = BTreeNode(y.leaf)
        x.children.insert(i + 1, z)
        x.keys.insert(i, y.keys[t - 1])
        z.keys = y.keys[t: (2 * t) - 1]
        y.keys = y.keys[0: t - 1]
        if not y.leaf:
            z.children = y.children[t: 2 * t]
            y.children = y.children[0: t]

    def traverse(self):
        self._traverse(self.root)
        print()

    def _traverse(self, x):
        i = 0
        while i < len(x.keys):
            if not x.leaf:
                self._traverse(x.children[i])
            print(x.keys[i], end=" ")
            i += 1
        if not x.leaf:
            self._traverse(x.children[i])

# Example usage
b_tree = BTree(3)  # A B-Tree with minimum degree 3
keys = [10, 20, 5, 6, 12, 30, 7, 17]
for key in keys:
    b_tree.insert(key)

print("B-Tree traversal:")
b_tree.traverse()

Time Complexity: #

  • Insertion: O(log n)
  • Deletion: O(log n)
  • Search: O(log n)

Space Complexity: #

O(n) for storing n keys

Comparison of Advanced Tree Structures #

  1. AVL Trees:

    • Pros: Strictly balanced, guaranteeing O(log n) operations
    • Cons: More rotations during insertion and deletion

  2. Red-Black Trees:

    • Pros: Fewer rotations than AVL trees, good for frequent insertions/deletions
    • Cons: Not as strictly balanced as AVL trees

  3. B-Trees:

    • Pros: Optimized for disk access, good for large datasets
    • Cons: More complex implementation, higher memory usage for small datasets

Applications #

  1. AVL Trees: Used in databases for indexing, in-memory sorting
  2. Red-Black Trees: Implemented in many standard library map/set data structures
  3. B-Trees: Used in file systems and databases for efficient disk access

Exercise #

  1. Implement a delete operation for the AVL Tree.
  2. Add a search function to the Red-Black Tree implementation.
  3. Modify the B-Tree to support deletion of keys.

Summary #

Today, we explored three advanced tree structures: AVL Trees, Red-Black Trees, and B-Trees. Each of these structures offers unique benefits and trade-offs, making them suitable for different scenarios. Understanding these advanced tree structures is crucial for designing efficient algorithms and data structures for various applications, especially those dealing with large datasets or requiring balanced search trees.

As we near the end of our 60-day challenge, these advanced concepts demonstrate the depth and complexity of algorithmic thinking. Tomorrow, we’ll tackle our final topic, bringing together many of the concepts we’ve learned throughout this journey. Stay tuned for the exciting conclusion of our challenge!