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: #
- For each node, the heights of its left and right subtrees differ by at most 1.
- Every subtree is an AVL tree.
- 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: #
- Every node is either red or black.
- The root is always black.
- Every leaf (NIL) is black.
- If a node is red, then both its children are black.
- 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: #
- All leaves are at the same depth.
- A non-leaf node with k children contains k-1 keys.
- 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.
- The root has at least 2 children if it is not a leaf node.
- 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 #
AVL Trees:
- Pros: Strictly balanced, guaranteeing O(log n) operations
- Cons: More rotations during insertion and deletion
Red-Black Trees:
- Pros: Fewer rotations than AVL trees, good for frequent insertions/deletions
- Cons: Not as strictly balanced as AVL trees
B-Trees:
- Pros: Optimized for disk access, good for large datasets
- Cons: More complex implementation, higher memory usage for small datasets
Applications #
- AVL Trees: Used in databases for indexing, in-memory sorting
- Red-Black Trees: Implemented in many standard library map/set data structures
- B-Trees: Used in file systems and databases for efficient disk access
Exercise #
- Implement a delete operation for the AVL Tree.
- Add a search function to the Red-Black Tree implementation.
- 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!