forked from kiat/Elements-of-Software-Design
-
Notifications
You must be signed in to change notification settings - Fork 0
/
example_026_BTree.py
150 lines (124 loc) · 4.01 KB
/
example_026_BTree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
class BTreeNode:
def __init__(self, leaf=True):
# Constructor to initialize a B-Tree node
self.leaf = leaf # Indicates if the node is a leaf
self.keys = [] # List to store keys
self.children = [] # List to store child nodes
class BTree:
def __init__(self, t):
"""
B-Tree constructor.
Args:
- t: Order of the B-Tree
"""
self.root = BTreeNode(True) # Initializing the root node
self.t = t # Order of the B-Tree
self.root = BTreeNode(True)
self.t = t
def insert(self, k):
"""
Insert a key into the B-Tree.
Args:
- k: Key to insert
"""
root = self.root
if len(root.keys) == (2 * self.t) - 1:
new_root = BTreeNode()
new_root.children.append(root)
self._split_child(new_root, 0)
self._insert_non_full(new_root, k)
self.root = new_root
else:
self._insert_non_full(root, k)
def _insert_non_full(self, node, k):
"""
Insert into a non-full node.
Args:
- node: Current node in the B-Tree
- k: Key to insert
"""
i = len(node.keys) - 1
if node.leaf:
node.keys.append(0)
while i >= 0 and k < node.keys[i]:
node.keys[i + 1] = node.keys[i]
i -= 1
node.keys[i + 1] = k
else:
while i >= 0 and k < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == (2 * self.t) - 1:
self._split_child(node, i)
if k > node.keys[i]:
i += 1
self._insert_non_full(node.children[i], k)
def _split_child(self, parent, i):
"""
Split child node of a parent node.
Args:
- parent: Parent node
- i: Index of child node to split
"""
t = self.t
child = parent.children[i]
new_child = BTreeNode(child.leaf)
parent.children.insert(i + 1, new_child)
parent.keys.insert(i, child.keys[t - 1])
new_child.keys = child.keys[t: (2 * t) - 1]
child.keys = child.keys[0: t - 1]
if not child.leaf:
new_child.children = child.children[t: 2 * t]
child.children = child.children[0: t - 1]
def search(self, k, node=None):
"""
Search for a key in the B-Tree.
Args:
- k: Key to search
- node: Starting node for the search
"""
if node is None:
node = self.root
i = 0
while i < len(node.keys) and k > node.keys[i]:
i += 1
if i < len(node.keys) and k == node.keys[i]:
return True
elif node.leaf:
return False
else:
return self.search(k, node.children[i])
def display(self, node=None, level=0):
"""
Display the B-Tree structure.
Args:
- node: Node to start the display from (default is the root)
- level: Level of the node in the B-Tree (default is 0)
"""
if node is None:
node = self.root
for i in range(len(node.keys)):
if not node.leaf:
self.display(node.children[i], level + 1)
print("Level", level, "Key", node.keys[i])
if not node.leaf:
self.display(node.children[len(node.keys)], level + 1)
def main():
# Create a B-Tree of order 3
b_tree = BTree(3)
# Keys to insert into the B-Tree
keys_to_insert = [10, 20, 5, 6, 12, 30, 7, 17]
# Insert keys into the B-Tree
for key in keys_to_insert:
b_tree.insert(key)
# Display the B-Tree structure
print("B-Tree structure:")
b_tree.display()
# Key to search in the B-Tree
search_key = 6
if b_tree.search(search_key):
print(f"Key {search_key} found in the B-Tree")
else:
print(f"Key {search_key} not found in the B-Tree")
if __name__ == "__main__":
main()