Search operation in B Tree in Python
B tree makes it convenient for users to search for an element in it like searching for an element in any other binary tree. Let us see how it searches for an element ‘m‘ in the tree.
- The search begins from the root node and compares them with the key values of the root node. If the value of the key is similar to m then it simply returns the index corresponding to that node where the key matched.
- If the key is not found, it goes down. It compares the value of the current key of the node to m. If the current element is smaller than m, then it searches for the right child of the node again and again.
- These steps are repeated until it finds the element or the leaf node is reached.
Step-by-step algorithm:
- m is not found in the root so we will compare it with the key. i.e. compare 10 and 100.
- Since 10<100, we will search in the left part of the tree.
- Now we will compare m with all the elements in the current node i.e. we will compare m with 35 and 65 in order.
- Since m is smaller than both 35 and 65, we will go to the left side of the tree to find the element.
- Now we will compare m with all the keys of the current node i.e. 10 and 20 but the first key of this node is equal to m so we found the element.
Below is the implementation of the approach:
# Searching a key on a B-tree in Python
# Create a node
class BTreeNode:
def __init__(self, leaf=False):
self.leaf = leaf
self.keys = []
self.child = []
# Tree
class BTree:
def __init__(self, t):
self.root = BTreeNode(True)
self.t = t
# Insert node
def insert(self, k):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
temp = BTreeNode()
self.root = temp
temp.child.insert(0, root)
self.split_child(temp, 0)
self.insert_non_full(temp, k)
else:
self.insert_non_full(root, k)
# Insert nonfull
def insert_non_full(self, x, k):
i = len(x.keys) - 1
if x.leaf:
x.keys.append((None, None))
while i >= 0 and k[0] < x.keys[i][0]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = k
else:
while i >= 0 and k[0] < x.keys[i][0]:
i -= 1
i += 1
if len(x.child[i].keys) == (2 * self.t) - 1:
self.split_child(x, i)
if k[0] > x.keys[i][0]:
i += 1
self.insert_non_full(x.child[i], k)
# Split the child
def split_child(self, x, i):
t = self.t
y = x.child[i]
z = BTreeNode(y.leaf)
x.child.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.child = y.child[t: 2 * t]
y.child = y.child[0: t - 1]
# Print the tree
def print_tree(self, x, l=0):
print("Level ", l, " ", len(x.keys), end=":")
for i in x.keys:
print(i, end=" ")
print()
l += 1
if len(x.child) > 0:
for i in x.child:
self.print_tree(i, l)
# Search key in the tree
def search_key(self, k, x=None):
if x is not None:
i = 0
while i < len(x.keys) and k > x.keys[i][0]:
i += 1
if i < len(x.keys) and k == x.keys[i][0]:
return (x, i)
elif x.leaf:
return None
else:
return self.search_key(k, x.child[i])
else:
return self.search_key(k, self.root)
def main():
B = BTree(3)
for i in range(10):
B.insert((i, 2 * i))
B.print_tree(B.root)
if B.search_key(8) is not None:
print("\nFound")
else:
print("\nNot Found")
if __name__ == '__main__':
main()
Output
Level 0 2:(2, 4) (5, 10) Level 1 2:(0, 0) (1, 2) Level 1 2:(3, 6) (4, 8) Level 1 4:(6, 12) (7, 14) (8, 16) (9, 18) Found
Time Complexity : O(log n)
Auxiliary Space: O(n)
B Tree in Python
A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
B Tree in Python
Table of Content
- Characteristics of B-Trees
- Traversal of B-Tree in Python
- Search operation in B Tree in Python
- Insert operation in B Tree in Python
- Delete operation in B Tree in Python