数据结构编程实践20讲(Python版)—09B树
往期链接
| 01 数组 | 02 链表 | 03 栈 | 04 队列 | 05 二叉树 | 06 二叉搜索树 | 07 AVL树 | 08 红黑树 |
|---|
09 B树(B-tree)
S1 说明
B树是一种自平衡的树数据结构，它的主要特点是：
- 多路搜索树：B树的每个节点可以有多个子节点，而不是二叉树的两个子节点。每个节点可以存储多个键值。
- 平衡性：B树的所有叶子节点都在同一层级，保证了树的高度尽可能低，从而提高了查找效率。
- 节点的填充因子：每个节点的键值数量在一定范围内，通常是 [⌈m/2⌉, m-1]，其中 m 是树的最大度数（每个节点的最大子节点数量）。⌈m/2⌉ 为m/2向上取整。
- 插入与删除：B树支持高效的插入和删除操作，保持树的平衡性。
B树的实际应用
- 数据库索引：B树常用于数据库管理系统中的索引，因为它们可以有效处理大量数据的存储和检索。
- 文件系统：许多现代文件系统使用 B树来管理文件的元数据，以支持快速的查找和插入。
- 内存管理：B树可以用于动态内存分配中的分区管理，保持内存块的有序性。
- 网络路由表：在网络路由中，B树可以用来存储和快速查找路由信息。
S2 示例
import matplotlib.pyplot as plt
class BTreeNode:
def __init__(self, t, leaf=True):
self.t = t # 最小度数
self.keys = [] # 存储键值
self.children = [] # 存储子节点
self.leaf = leaf # 是否为叶子节点
class BTree:
def __init__(self, t):
self.root = BTreeNode(t) # 创建根节点
self.t = t # 设置B树的最小度数
def insert(self, k):
root = self.root
# 如果根节点已满，需要分裂
if len(root.keys) == (2 * self.t) - 1:
temp = BTreeNode(self.t, False)
self.root = temp
temp.children.insert(0, root)
self.split_child(temp, 0)
self.insert_non_full(temp, k)
else:
self.insert_non_full(root, k)
def insert_non_full(self, x, k):
i = len(x.keys) - 1
if x.leaf:
# 如果是叶子节点，直接插入键值
x.keys.append(None)
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.children[i].keys) == (2 * self.t) - 1:
# 如果子节点已满，需要先分裂
self.split_child(x, i)
if k > x.keys[i]:
i += 1
self.insert_non_full(x.children[i], k)
def split_child(self, x, i):
t = self.t
y = x.children[i]
z = BTreeNode(t, y.leaf)
x.children.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.children = y.children[t: 2 * t]
y.children = y.children[0: t]
def visualize(self):
fig, ax = plt.subplots(figsize=(12, 8))
self._draw_tree(self.root, ax, 0, 0, 100)
ax.axis('off')
plt.show()
def _draw_tree(self, node, ax, x, y, width):
if node:
node_text = ', '.join(map(str, node.keys))
ax.text(x, y, node_text原文地址：https://blog.csdn.net/qq_32882309/article/details/142870707
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！