Python中如何实现B树查找算法
B树可以看作是一种平衡的多叉树，它的节点存储着多个关键字，并且每个节点有多个子节点。B树的特点是，每个节点最多存储m个关键字，而且m次分裂后，高度最多为logn，其中n是B树中关键字的总数。B树查找的时间复杂度为O(logn)。
下面是一个简单的B树实现，用于存储字符串。示例中使用了“pidancode.com”、“皮蛋编程”作为测试数据。
class BNode: def __init__(self, m): self.m = m # 节点最多存储m-1个关键字 self.keys = [] # 节点存储的关键字 self.children = [] # 子节点 self.leaf = True # 是否为叶子节点 def add_key(self, key, child=None): # 在B树节点中添加一个关键字 if len(self.keys) < self.m-1: # 如果节点未满，直接添加 self.keys.append(key) self.keys.sort() # 维护关键字有序性 if child is not None: self.children.append(child) self.children.sort() # 维护子节点有序性 return None else: # 如果节点已满，需要分裂 return self.split(key, child) def split(self, key, child=None): # 节点分裂 new_node = BNode(self.m) mid_point = int(len(self.keys)/2) median = self.keys[mid_point] new_node.children = self.children[mid_point+1:] self.children = self.children[:mid_point+1] new_node.keys = self.keys[mid_point+1:] self.keys = self.keys[:mid_point] new_node.leaf = self.leaf self.leaf = False if key < median: self.add_key(key, child) else: new_node.add_key(key, child) return median, new_node class BTree: def __init__(self, m): self.m = m # B树最多存储m-1个关键字 self.root = BNode(m) def search(self, key, node=None): # 在B树中查找一个关键字 if node is None: node = self.root if key in node.keys: return True elif node.leaf: return False else: for i in range(len(node.keys)): if key < node.keys[i]: return self.search(key, node.children[i]) return self.search(key, node.children[-1]) def insert(self, key): # 在B树中插入一个关键字 if not self.search(key): median, new_node = self.root.add_key(key) if median is not None: # 如果根节点分裂，需要新建一个节点作为根节点 old_root = self.root self.root = BNode(self.m) self.root.keys = [median] self.root.children = [old_root, new_node] self.leaf = False return True else: return False # 创建一个B树 btree = BTree(3) # 添加关键字 btree.insert("pidancode.com") btree.insert("皮蛋编程") # 查找关键字 print(btree.search("pidancode.com")) # True print(btree.search("pandan")) # False
相关文章