二叉树、平衡树、B 树与 B+ 树核心原理及代码实现

1 二叉树

这是最基础的树形结构。

• 定义：每个节点最多只有两个子节点（左子树和右子树）。
• 优点：比链表快，插入和查找的平均时间复杂度是 O(log N)。

缺点：不稳定。在极端情况下（比如插入的数据本身已经是有序的，如 6, 7, 8, 9），它会退化成一条链表。

此时查找时间复杂度会降到 O(N)，性能急剧下降。

2 二叉平衡树

为了解决二叉树的退化问题，平衡树诞生了。

• 定义：在二叉树的基础上增加了约束：左右子树的高度差不能超过 1。
• 工作原理：每次插入或删除数据时，如果平衡被破坏，它会通过旋转操作来自动调整结构，使其始终保持平衡。
• 优点：避免了二叉树退化成链表的问题，查找效率非常稳定，始终维持在 O(log N)。
• 缺点：
  • 树太高：当数据量非常大时（例如几百万条），log N 的深度可能依然有 20-30 层。每一次从磁盘读取一层数据，就是一次磁盘 I/O，非常慢。
  • 数据量问题：它适用于内存中的查找，但不适用于海量数据的磁盘存储。
• 平衡二叉树插入数据导致破坏平衡的类型分为四种：LL、LR、RR、RL，具体解决方法包括对应的旋转操作。

3 B 树

当数据量大到无法全部放入内存，必须存放在磁盘上时，B 树出现了。它是一种多路搜索树。

• 核心思想：不再像二叉树那样只有一个节点一个数据，而是一个节点可以存储多个值，并且拥有多个子节点（多叉的）。
• 结构特点：
  • 每个节点包含键值和数据（或指针）。
  • 节点内的键值从小到大排序。
  • 所有节点（包括根节点和中间节点）都可能存储实际的数据。
• 优点：降低了树的高度。因为一个节点存了多个值，树变得更矮更胖，从而减少了磁盘 I/O 次数。
• 缺点：
  • 查询不稳定：数据可能存在于根节点，也可能存在于叶子节点。查找根节点就找到的话很快，但找到叶子节点就慢一些。
  • 范围查询麻烦：要进行范围查询（如 > 20），需要多次从根节点遍历到叶子节点（中序遍历），比较繁琐。

4 B+ 树

B+ 树是 B 树的升级版，也是目前关系型数据库（如 MySQL 的 InnoDB 引擎）最常用的索引结构。

• 核心改进：
  • 数据只存储在叶子节点：非叶子节点（内节点）只存储指针和键值，不存储数据。这就意味着非叶子节点可以容纳更多的索引项，让树变得更矮更宽。
  • 叶子节点之间形成有序链表：所有的叶子节点通过指针连接成了一个有序的链表。
• 为什么数据库用 B+ 树而不是 B 树？
  1. 范围查询能力极强：比如查 age > 18。B+ 树只需要在叶子节点的链表上顺序遍历即可，不需要像 B 树那样回溯到父节点。这正是数据库最常用的操作。
  2. 查询效率稳定：任何数据的查找都必须从根节点走到叶子节点，路径长度一样。这使得查询时间非常稳定，便于数据库优化器进行评估。
  3. 更充分利用磁盘预读：非叶子节点不存数据，占用的空间更小，操作系统一次 I/O 可以读取更多的索引项到内存中。

5 二叉树遍历方式

5.1 深度优先 DFS

class TreeNode:
    """二叉树节点"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val  # 节点的值
        self.left = left  # 左子节点
        self.right = right  # 右子节点

5.1.1 前序遍历

def preorder_recursive(self, node):
    """前序遍历：根 -> 左 -> 右"""
    if node is None:
        return []
    result = [node.val]
    result.extend(self.preorder_recursive(node.left))
    result.extend(self.preorder_recursive(node.right))
    return result

5.1.2 中序遍历

def inorder_recursive(self, node):
    """中序遍历：左 -> 根 -> 右"""
    if node is None:
        return []
    result = self.inorder_recursive(node.left)
    result.append(node.val)
    result.extend(self.inorder_recursive(node.right))
    return result

5.1.3 后序遍历

def postorder_recursive(self, node):
    """后序遍历：左 -> 右 -> 根"""
    if node is None:
        return []
    result = self.postorder_recursive(node.left)
    result.extend(self.postorder_recursive(node.right))
    result.append(node.val)
    return result

5.2 广度优先 BFS

def level_order(self):
    """层序遍历，使用队列"""
    if not self.root:
        return []
    result = []
    queue = [self.root]  # 用列表模拟队列
    while queue:
        level_size = len(queue)
        level_nodes = []
        for i in range(level_size):
            node = queue.pop(0)  # 取出队列头部
            level_nodes.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_nodes)  # 按层存储
    return result