Searching and Addition in B-Tree
Learn about searching and addition in the B-trees.
We'll cover the following...
Searching
The implementation of the find(x) operation, which is illustrated below generalizes the find(x) operation in a binary search tree. The search for x starts at the root and uses the keys stored at a node, u, to determine in which of u’s children the search should continue.
A successful search is shown below (for the value ) and an unsuccessful search (for the value ) in a -tree. Shaded nodes show where the value of is updated during the searches.
More specifically, at a node u, the search checks if x is stored in u.keys. If so, x has been found and the search is complete. Otherwise, the search finds the smallest integer, i, such that u.key[i] > x and continues the search in the subtree rooted at u.children[i]. If no key in u.keys is
greater than x, then the search continues in u’s rightmost child. Just like binary search trees, the algorithm keeps track of the most recently seen
key, z that is larger than x. In case x is not found, z is returned as the smallest value that is greater or equal to x.
class BTree(BaseSet):class Node(object):def __init__(self, btree):self.btree = btreeself.keys = new_array(self.btree.b)self.children = new_int_array(self.btree.b+1, -1)self.id = self.btree.bs.place_block(self)def __init__(self, b):self._initialize(b)def find(self, x):z = Noneui = self.riwhile ui >= 0:u = self.bs.read_block(ui)i = find_it(u.keys, x)if i < 0:return u.keys[-(i+1)] # found itif u.keys[i] is not None:z = u.keys[i]ui = u.children[i]return z
Central to the find(x) method is the findIt(a,x) method that searches in a null-padded sorted array, a, for the value x.
This method, illustrated
in above illustration, works for any array, a, where is a sequence of keys in sorted order and are all ...
Create a free account to access the full course.
By signing up, you agree to Educative's Terms of Service and Privacy Policy