Day 59: Advanced Tree Structures
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: #
1class AVLNode:
2 def __init__(self, key):
3 self.key = key
4 self.left = None
5 self.right = None
6 self.height = 1
7
8class AVLTree:
9 def __init__(self):
10 self.root = None
11
12 def height(self, node):
13 if not node:
14 return 0
15 return node.height
16
17 def balance_factor( …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: #
1class AVLNode:
2 def __init__(self, key):
3 self.key = key
4 self.left = None
5 self.right = None
6 self.height = 1
7
8class AVLTree:
9 def __init__(self):
10 self.root = None
11
12 def height(self, node):
13 if not node:
14 return 0
15 return node.height
16
17 def balance_factor(self, node):
18 if not node:
19 return 0
20 return self.height(node.left) - self.height(node.right)
21
22 def update_height(self, node):
23 if not node:
24 return
25 node.height = 1 + max(self.height(node.left), self.height(node.right))
26
27 def right_rotate(self, y):
28 x = y.left
29 T2 = x.right
30 x.right = y
31 y.left = T2
32 self.update_height(y)
33 self.update_height(x)
34 return x
35
36 def left_rotate(self, x):
37 y = x.right
38 T2 = y.left
39 y.left = x
40 x.right = T2
41 self.update_height(x)
42 self.update_height(y)
43 return y
44
45 def insert(self, root, key):
46 if not root:
47 return AVLNode(key)
48 if key < root.key:
49 root.left = self.insert(root.left, key)
50 else:
51 root.right = self.insert(root.right, key)
52
53 self.update_height(root)
54 balance = self.balance_factor(root)
55
56 # Left Left Case
57 if balance > 1 and key < root.left.key:
58 return self.right_rotate(root)
59 # Right Right Case
60 if balance < -1 and key > root.right.key:
61 return self.left_rotate(root)
62 # Left Right Case
63 if balance > 1 and key > root.left.key:
64 root.left = self.left_rotate(root.left)
65 return self.right_rotate(root)
66 # Right Left Case
67 if balance < -1 and key < root.right.key:
68 root.right = self.right_rotate(root.right)
69 return self.left_rotate(root)
70
71 return root
72
73 def insert_key(self, key):
74 self.root = self.insert(self.root, key)
75
76 def inorder_traversal(self, root):
77 if not root:
78 return
79 self.inorder_traversal(root.left)
80 print(root.key, end=" ")
81 self.inorder_traversal(root.right)
82
83# Example usage
84avl_tree = AVLTree()
85keys = [10, 20, 30, 40, 50, 25]
86for key in keys:
87 avl_tree.insert_key(key)
88
89print("Inorder traversal of the AVL tree:")
90avl_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: #
1class Color:
2 RED = 1
3 BLACK = 2
4
5class RBNode:
6 def __init__(self, key):
7 self.key = key
8 self.left = None
9 self.right = None
10 self.parent = None
11 self.color = Color.RED
12
13class RedBlackTree:
14 def __init__(self):
15 self.NIL = RBNode(0)
16 self.NIL.color = Color.BLACK
17 self.root = self.NIL
18
19 def left_rotate(self, x):
20 y = x.right
21 x.right = y.left
22 if y.left != self.NIL:
23 y.left.parent = x
24 y.parent = x.parent
25 if x.parent == None:
26 self.root = y
27 elif x == x.parent.left:
28 x.parent.left = y
29 else:
30 x.parent.right = y
31 y.left = x
32 x.parent = y
33
34 def right_rotate(self, x):
35 y = x.left
36 x.left = y.right
37 if y.right != self.NIL:
38 y.right.parent = x
39 y.parent = x.parent
40 if x.parent == None:
41 self.root = y
42 elif x == x.parent.right:
43 x.parent.right = y
44 else:
45 x.parent.left = y
46 y.right = x
47 x.parent = y
48
49 def insert(self, key):
50 node = RBNode(key)
51 node.left = self.NIL
52 node.right = self.NIL
53 y = None
54 x = self.root
55
56 while x != self.NIL:
57 y = x
58 if node.key < x.key:
59 x = x.left
60 else:
61 x = x.right
62
63 node.parent = y
64 if y == None:
65 self.root = node
66 elif node.key < y.key:
67 y.left = node
68 else:
69 y.right = node
70
71 self.insert_fixup(node)
72
73 def insert_fixup(self, k):
74 while k.parent and k.parent.color == Color.RED:
75 if k.parent == k.parent.parent.left:
76 u = k.parent.parent.right
77 if u.color == Color.RED:
78 k.parent.color = Color.BLACK
79 u.color = Color.BLACK
80 k.parent.parent.color = Color.RED
81 k = k.parent.parent
82 else:
83 if k == k.parent.right:
84 k = k.parent
85 self.left_rotate(k)
86 k.parent.color = Color.BLACK
87 k.parent.parent.color = Color.RED
88 self.right_rotate(k.parent.parent)
89 else:
90 u = k.parent.parent.left
91 if u.color == Color.RED:
92 k.parent.color = Color.BLACK
93 u.color = Color.BLACK
94 k.parent.parent.color = Color.RED
95 k = k.parent.parent
96 else:
97 if k == k.parent.left:
98 k = k.parent
99 self.right_rotate(k)
100 k.parent.color = Color.BLACK
101 k.parent.parent.color = Color.RED
102 self.left_rotate(k.parent.parent)
103 if k == self.root:
104 break
105 self.root.color = Color.BLACK
106
107 def inorder_traversal(self, node):
108 if node != self.NIL:
109 self.inorder_traversal(node.left)
110 print(node.key, end=" ")
111 self.inorder_traversal(node.right)
112
113# Example usage
114rb_tree = RedBlackTree()
115keys = [7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13]
116for key in keys:
117 rb_tree.insert(key)
118
119print("Inorder traversal of the Red-Black tree:")
120rb_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: #
1class BTreeNode:
2 def __init__(self, leaf=False):
3 self.leaf = leaf
4 self.keys = []
5 self.children = []
6
7class BTree:
8 def __init__(self, t):
9 self.root = BTreeNode(True)
10 self.t = t # Minimum degree
11
12 def insert(self, k):
13 root = self.root
14 if len(root.keys) == (2 * self.t) - 1:
15 new_root = BTreeNode()
16 new_root.children.insert(0, root)
17 self.split_child(new_root, 0)
18 self.root = new_root
19 self.insert_non_full(new_root, k)
20 else:
21 self.insert_non_full(root, k)
22
23 def insert_non_full(self, x, k):
24 i = len(x.keys) - 1
25 if x.leaf:
26 x.keys.append(None)
27 while i >= 0 and k < x.keys[i]:
28 x.keys[i + 1] = x.keys[i]
29 i -= 1
30 x.keys[i + 1] = k
31 else:
32 while i >= 0 and k < x.keys[i]:
33 i -= 1
34 i += 1
35 if len(x.children[i].keys) == (2 * self.t) - 1:
36 self.split_child(x, i)
37 if k > x.keys[i]:
38 i += 1
39 self.insert_non_full(x.children[i], k)
40
41 def split_child(self, x, i):
42 t = self.t
43 y = x.children[i]
44 z = BTreeNode(y.leaf)
45 x.children.insert(i + 1, z)
46 x.keys.insert(i, y.keys[t - 1])
47 z.keys = y.keys[t: (2 * t) - 1]
48 y.keys = y.keys[0: t - 1]
49 if not y.leaf:
50 z.children = y.children[t: 2 * t]
51 y.children = y.children[0: t]
52
53 def traverse(self):
54 self._traverse(self.root)
55 print()
56
57 def _traverse(self, x):
58 i = 0
59 while i < len(x.keys):
60 if not x.leaf:
61 self._traverse(x.children[i])
62 print(x.keys[i], end=" ")
63 i += 1
64 if not x.leaf:
65 self._traverse(x.children[i])
66
67# Example usage
68b_tree = BTree(3) # A B-Tree with minimum degree 3
69keys = [10, 20, 5, 6, 12, 30, 7, 17]
70for key in keys:
71 b_tree.insert(key)
72
73print("B-Tree traversal:")
74b_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. As we near the 60 days, stay tuned for the exciting conclusion of our challenge!
Continue Reading
Sign up or log in to access the full lesson and all 60 days of algorithm content.