Python中的树形数据结构: B-树
B-树是一种自平衡的树形数据结构,它能够高效地支持插入、删除和查找操作,特别适用于大规模的存储和查询。B-树的特点是每个节点都含有多个关键字,可以有多个子节点,子节点的数量范围在一个固定的范围内。
B-树中的节点会按照关键字的大小顺序排列,同一层级的节点拥有相同的子节点数目,这个固定的数目称为B树的阶数。对于阶数为B的B树,其节点上至少包含ceil(B/2)个关键字,至多包含B-1个关键字。
以下是Python实现B-树的代码示例:
class BTreeNode: def __init__(self, leaf=False): self.leaf = leaf self.keys = [] self.child = [] class BTree: def __init__(self, t): self.root = BTreeNode(True) self.t = t def search(self, k, x=None): if x is not None: i = 0 while i < len(x.keys) and k > x.keys[i]: i += 1 if i < len(x.keys) and k == x.keys[i]: return (x, i) elif x.leaf: return None else: return self.search(k, x.child[i]) else: return self.search(k, self.root) def insert(self, k): r = self.root if len(r.keys) == (2*self.t)-1: s = BTreeNode() self.root = s s.child.insert(0, r) self._split_child(s, 0) self._insert_nonfull(s, k) else: self._insert_nonfull(r, k) def _insert_nonfull(self, x, k): i = len(x.keys)-1 if x.leaf: x.keys.append(0) while i >= 0 and k < x.keys[i]: x.keys[i+1] = x.keys[i] i -= 1 x.keys[i+1] = k else: while i >= 0 and k < x.keys[i]: i -= 1 i += 1 if len(x.child[i].keys) == (2*self.t)-1: self._split_child(x, i) if k > x.keys[i]: i += 1 self._insert_nonfull(x.child[i], k) def _split_child(self, x, i): t = self.t y = x.child[i] z = BTreeNode(leaf=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]
假设我们需要将字符串"pidancode.com"和"皮蛋编程"插入到B树中,可以按如下方式进行:
btree = BTree(t=3) btree.insert("pidancode.com") btree.insert("皮蛋编程")
在插入操作完成后,我们可以通过search方法查询插入的值:
node, index = btree.search("pidancode.com") if node: print("Found at position:", index) else: print("Not found")
需要注意的是,我们在构造B树时需要指定它的阶数,这里我们使用了t=3的B树作为示例。实际使用中,阶数的选择应该根据实际情况进行调整。
相关文章