层层分叉的世界 —— 树与二叉树

树是自然界最优雅的结构——从树干分出枝干，从枝干分出树枝，从树枝长出叶子。计算机科学把这个结构倒过来画，用来解决”层级”和”高效查找”的问题。

📋 开篇自测：你已经知道多少？

1. 你电脑里的文件夹结构就是一棵树——你能说出根节点、叶子节点、子树各对应什么吗？
2. 二叉搜索树的查找为什么平均只需要O(log n)？在什么情况下它会退化成O(n)？
3. 红黑树和AVL树都是”自平衡”的，但Java的HashMap为什么选了红黑树而不是AVL树？

---

一、为什么需要树结构

前面几章学的数组、链表、栈、队列，都是”一条线”式的线性结构。但现实世界中很多关系并不是线性的：

• 公司的组织架构：CEO管副总，副总管总监，总监管经理…
• 操作系统的文件目录：根目录下有多个文件夹，每个文件夹又可以有子文件夹
• HTML网页的DOM结构：html下面有head和body，body下面有div、p、img…

这些关系天然就是层级式的，用线性结构来表示会非常别扭。而树结构则完美匹配这种”一对多”的层次关系。

树的基本术语

          CEO
        /     \
      VP1      VP2
     / \        |
   Dir1 Dir2   Dir3
   |          / \
  Mgr1     Mgr2 Mgr3

• 根节点（Root）： 最顶上的节点，比如CEO。没有父节点。
• 叶子节点（Leaf）： 没有子节点的节点，比如Mgr1、Dir2、Mgr2、Mgr3。
• 父节点和子节点： VP1是Dir1的父节点，Dir1是VP1的子节点。
• 深度（Depth）： 从根到某个节点的层数。根节点深度为0。
• 高度（Height）： 从某个节点到最远叶子的层数。整棵树的高度就是根节点的高度。
• 子树（Subtree）： 每个节点和它的所有后代构成一棵子树。

---

二、二叉树——树家族中的超级明星

二叉树（Binary Tree） 是最常用的树结构，它有一个简单的规则：每个节点最多有两个子节点，分别叫左子节点和右子节点。

class TreeNode:
    """二叉树节点"""
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 手动构建一棵二叉树
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

三种遍历方式——把树”捋直”

树是二维的，但我们经常需要把它按某种顺序”捋”成一维的序列。三种最基本的遍历方式：

def preorder(node):
    """前序遍历：根 -> 左 -> 右"""
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

def inorder(node):
    """中序遍历：左 -> 根 -> 右"""
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def postorder(node):
    """后序遍历：左 -> 右 -> 根"""
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]

print("前序:", preorder(root))    # [1, 2, 4, 5, 3, 6]
print("中序:", inorder(root))     # [4, 2, 5, 1, 3, 6]
print("后序:", postorder(root))   # [4, 5, 2, 6, 3, 1]

怎么记这三种遍历？“前中后”说的是根节点的位置：

• 前序：根在前面（根-左-右）
• 中序：根在中间（左-根-右）
• 后序：根在后面（左-右-根）

还有一种层序遍历——一层一层地从上到下、从左到右，需要用队列来实现：

from collections import deque

def level_order(root):
    """层序遍历：逐层从左到右"""
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

print("层序:", level_order(root))  # [1, 2, 3, 4, 5, 6]

🤔 想一想 你的电脑遍历一个文件夹中的所有文件，用的是哪种遍历方式？（提示：os.walk()是层序还是深度优先？）

---

三、二叉搜索树——让查找变得飞快

普通二叉树没有什么特殊规则，所以查找一个元素还是得遍历所有节点，跟链表差不多。但如果我们加上一条规则呢？

二叉搜索树（BST, Binary Search Tree）的规则： 对于任意节点，它的左子树中所有值都比它小，右子树中所有值都比它大。

        8
       / \
      3   10
     / \    \
    1   6   14
       / \  /
      4  7 13

有了这条规则，查找就变得像翻字典一样高效：

class BST:
    """二叉搜索树"""

    def __init__(self):
        self.root = None

    def insert(self, value):
        """插入一个值"""
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return TreeNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node

    def search(self, value):
        """查找一个值"""
        return self._search(self.root, value)

    def _search(self, node, value):
        if node is None:
            return False
        if value == node.value:
            return True
        elif value < node.value:
            return self._search(node.left, value)
        else:
            return self._search(node.right, value)

    def inorder(self):
        """中序遍历得到有序序列"""
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.value)
            self._inorder(node.right, result)

# 使用
bst = BST()
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    bst.insert(val)

print(bst.search(7))     # True
print(bst.search(9))     # False
print(bst.inorder())     # [1, 3, 4, 6, 7, 8, 10, 13, 14] 自动排好序了！

每次查找都排除一半的节点，所以平均时间复杂度是 O(log n)——和二分查找一样快。

BST的致命弱点——退化

如果你把1, 2, 3, 4, 5按顺序插入BST，会得到什么？

1
 \
  2
   \
    3
     \
      4
       \
        5

它退化成了一条链表！查找变成了O(n)。这就像一棵树只朝一个方向长，完全失去了”分叉”带来的效率优势。

解决办法：让树始终保持”平衡”。这就是接下来要讲的AVL树和红黑树。

---

四、AVL树——严格的平衡主义者

AVL树（以发明者Adelson-Velsky和Landis命名）是第一种自平衡二叉搜索树。它的规则是：任何节点的左右子树高度差不超过1。

一旦插入或删除操作破坏了这个平衡条件，就通过”旋转”来恢复平衡。

四种旋转操作

旋转听起来复杂，但本质上就是调整几个指针的指向。以”右旋”为例：

    失衡前（左边太重）        右旋后
        30                    20
       /                     /  \
      20                   10    30
     /
    10

def right_rotate(root):
    """右旋操作"""
    new_root = root.left
    root.left = new_root.right
    new_root.right = root
    return new_root

def left_rotate(root):
    """左旋操作"""
    new_root = root.right
    root.right = new_root.left
    new_root.left = root
    return new_root

四种失衡情况及对应的旋转：

失衡类型	形状	修复方法
LL（左-左）	歪向左下	右旋一次
RR（右-右）	歪向右下	左旋一次
LR（左-右）	左子树歪向右	先左旋左子树，再右旋根
RL（右-左）	右子树歪向左	先右旋右子树，再左旋根

AVL树的完整插入实现

光有旋转函数还不够，我们需要把它们整合到插入操作中。每次插入后，需要从插入位置向上检查每个祖先节点的平衡因子（左子树高度减右子树高度），一旦发现失衡就立即旋转修复。

class AVLNode:
    """AVL树节点（额外存储高度信息）"""
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1  # 新节点高度为1

class AVLTree:
    """AVL自平衡二叉搜索树"""

    def __init__(self):
        self.root = None

    def _get_height(self, node):
        """获取节点高度，空节点高度为0"""
        if node is None:
            return 0
        return node.height

    def _get_balance(self, node):
        """获取平衡因子：左子树高度 - 右子树高度"""
        if node is None:
            return 0
        return self._get_height(node.left) - self._get_height(node.right)

    def _update_height(self, node):
        """更新节点高度"""
        node.height = 1 + max(self._get_height(node.left),
                              self._get_height(node.right))

    def _right_rotate(self, z):
        """右旋（处理LL失衡）"""
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        self._update_height(z)
        self._update_height(y)
        return y

    def _left_rotate(self, z):
        """左旋（处理RR失衡）"""
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        self._update_height(z)
        self._update_height(y)
        return y

    def insert(self, value):
        """对外接口：插入一个值"""
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        """递归插入并自动平衡"""
        # 第一步：执行标准BST插入
        if node is None:
            return AVLNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        else:
            return node  # 不插入重复值

        # 第二步：更新当前节点的高度
        self._update_height(node)

        # 第三步：计算平衡因子，判断是否失衡
        balance = self._get_balance(node)

        # 四种失衡情况的处理（注意：这里通过比较 value 与子节点值来判断
        # 失衡类型，此方法仅适用于插入操作。删除操作应比较子树的平衡因子）：
        # LL型：左子树的左边太高 -> 右旋
        if balance > 1 and value < node.left.value:
            return self._right_rotate(node)

        # RR型：右子树的右边太高 -> 左旋
        if balance < -1 and value > node.right.value:
            return self._left_rotate(node)

        # LR型：左子树的右边太高 -> 先左旋左子树，再右旋
        if balance > 1 and value > node.left.value:
            node.left = self._left_rotate(node.left)
            return self._right_rotate(node)

        # RL型：右子树的左边太高 -> 先右旋右子树，再左旋
        if balance < -1 and value < node.right.value:
            node.right = self._right_rotate(node.right)
            return self._left_rotate(node)

        return node

    def inorder(self):
        """中序遍历（验证BST性质）"""
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.value)
            self._inorder(node.right, result)

# 验证：插入有序序列，AVL树不会退化
avl = AVLTree()
for val in [1, 2, 3, 4, 5, 6, 7]:
    avl.insert(val)

print(avl.inorder())  # [1, 2, 3, 4, 5, 6, 7]
print(f"根节点: {avl.root.value}")         # 4（自动平衡后的根）
print(f"树高度: {avl.root.height}")         # 3（而非退化成7）

对比一下：同样插入1到7这7个数字，普通BST会退化成高度为7的链表，而AVL树的高度只有3。这就是自平衡的威力。

AVL树保证了任何操作的时间复杂度都是O(log n)，因为树的高度始终被控制在log(n)附近。

---

五、红黑树——实用主义的平衡方案

AVL树虽然平衡性很好，但每次插入和删除都可能触发多次旋转，维护成本较高。红黑树是一种更”宽松”的平衡方案——它不要求左右子树高度差不超过1，而是通过给节点涂上红色或黑色来维持一种”大致平衡”。

红黑树的五条规则：

1. 每个节点要么是红色，要么是黑色
2. 根节点必须是黑色
3. 所有叶子节点（NIL哨兵节点，即不存储数据的空节点）是黑色
4. 红色节点的两个子节点必须是黑色（不能有连续两个红节点）
5. 从任意节点到其每个叶子的路径上，黑色节点的数量相同

这五条规则共同保证了：红黑树的最长路径不会超过最短路径的两倍。 所以虽然不像AVL那样严格平衡，但也足够好了——所有操作仍然是O(log n)。

AVL树 vs 红黑树

特性	AVL树	红黑树
平衡程度	严格平衡	近似平衡
查找效率	略好（树更矮）	略差
插入/删除效率	较差（旋转多）	较好（旋转少）
适用场景	查找密集型	插入/删除密集型
应用实例	数据库索引	Java的TreeMap、Linux的进程调度

为什么实际工程中红黑树更常见？因为大多数场景下插入删除操作比查找更频繁，而红黑树在这方面的开销更小。

自平衡的实际效果演示

红黑树的完整实现涉及大量的旋转和变色操作，代码量较大。但我们可以用Python的sortedcontainers库来直观感受有序容器的效果——它底层使用的是”排序列表的列表”（类似B-tree的分块策略），而非红黑树或AVL树，但同样能在插入有序数据时保持O(log n)的性能，不会像普通BST那样退化。

# 方法1：用sortedcontainers直观感受有序容器的效果
# 安装：pip install sortedcontainers
from sortedcontainers import SortedList

sl = SortedList()

# 即使按顺序插入，内部仍保持平衡，查找/插入都是O(log n)
for i in range(1, 100001):
    sl.add(i)

# 查找操作依然飞快（不会退化成O(n)）
print(50000 in sl)                 # True，O(log n)
print(sl[0], sl[-1])               # 1 100000
print(sl.bisect_left(50000))       # 49999（第50000个位置）

# 方法2：用我们上面实现的AVL树对比普通BST
import time

# 普通BST插入有序数据——退化成链表，性能极差
bst = BST()
start = time.time()
for i in range(1, 5001):
    bst.insert(i)
bst_time = time.time() - start
print(f"普通BST插入5000个有序元素: {bst_time:.3f}秒")

# AVL树插入有序数据——保持平衡，性能稳定
avl = AVLTree()
start = time.time()
for i in range(1, 5001):
    avl.insert(i)
avl_time = time.time() - start
print(f"AVL树插入5000个有序元素: {avl_time:.3f}秒")
print(f"AVL树高度: {avl.root.height}（理想高度约{13}）")
# 你会发现AVL树比退化的BST快得多

这个对比清楚地展示了自平衡的价值：面对有序数据，普通BST退化成链表后性能急剧下降，而自平衡树（无论是AVL树还是红黑树）始终保持O(log n)的高效性能。

🤔 想一想 你可能听说过Java的HashMap在链表长度超过8时会把链表转换成红黑树（前提是表的容量也达到了64，否则只会触发扩容而不是树化）。为什么不是一开始就用红黑树？为什么阈值是8而不是其他数字？

---

六、堆——另一种特殊的树

堆（Heap） 也是用二叉树的结构，但规则和BST不同：

• 大顶堆： 每个节点的值都大于等于其子节点的值（根是最大值）
• 小顶堆： 每个节点的值都小于等于其子节点的值（根是最小值）

堆的最大特点：可以在O(1)时间内获取最大值（或最小值），在O(log n)时间内插入或删除。

堆通常用数组来实现（而不是链式结构），因为完全二叉树有一个巧妙的性质——父子节点的索引存在简单的数学关系：

对于索引为i的节点：
- 父节点索引：(i - 1) // 2
- 左子节点索引：2 * i + 1
- 右子节点索引：2 * i + 2

堆的核心操作是上浮（sift up）和下沉（sift down）：插入新元素时放到末尾再上浮，取出堆顶时用末尾填顶再下沉。这两个操作保证了堆性质始终被维护。

在Python中，heapq 模块提供了现成的小顶堆实现：

import heapq

data = [5, 3, 8, 1, 2, 7]
heapq.heapify(data)         # 把列表原地转成堆
print(heapq.heappop(data))  # 1
print(heapq.heappop(data))  # 2
heapq.heappush(data, 0)     # 插入0
print(heapq.heappop(data))  # 0

堆是优先队列、堆排序、Top-K问题等场景的核心数据结构。我们会在第12章深入学习堆的完整实现、堆排序算法以及一系列经典应用题。

⚠️ 常见误区

• 误区1：“二叉搜索树和堆是一回事” —— 完全不同。BST的规则是”左小右大”，堆的规则是”父大于子”或”父小于子”。BST的中序遍历是有序的，堆不是。
• 误区2：“树越平衡越好” —— 维持平衡是有代价的。如果你的场景只需要插入不需要查找，用普通BST甚至链表可能更合适。
• 误区3：“红黑树比AVL树好” —— 不是绝对的。如果你的场景以查找为主（比如数据库索引），AVL树由于更矮，查找次数更少，反而更合适。

---

七、树在现实世界中的应用

• 文件系统： 目录树就是一棵多叉树
• 数据库索引： B树和B+树是多叉搜索树，能在磁盘上高效查找
• 编译器： 把代码解析成抽象语法树（AST）再进行编译
• 网页渲染： 浏览器把HTML解析成DOM树
• 人工智能： 决策树、博弈树
• 压缩算法： 哈夫曼编码用的是哈夫曼树

---

📝 掌握度自测

1. 概念题： 什么是完全二叉树？它和满二叉树有什么区别？为什么堆要求是完全二叉树？
2. 手算题： 将 [5, 2, 8, 1, 4, 7, 9, 3] 逐个插入一棵空的BST，画出最终的树形结构。然后写出中序遍历结果。
3. 分析题： 一棵有1000000个节点的平衡BST，最多需要比较多少次才能确定某个值是否存在？
4. 编码题： 实现一个函数，计算二叉树的最大深度。
5. 设计题： 如果你要设计一个实时排行榜（支持插入成绩、删除成绩、查询第k名），你会用什么数据结构？为什么？

💡 自我评估

• 全部答对：树结构已经是你的强项了，向更深处探索吧。
• 答对3-4题：基础很好，建议手动实现一下AVL树的旋转操作来加深理解。
• 答对1-2题：树是比较抽象的数据结构，建议拿纸笔画图辅助理解。
• 全部答错：先确保你理解了递归，因为树的大部分操作都基于递归思想。

---

数据结构的学习暂告一段落，接下来我们把注意力转向算法本身。第一个登场的是计算机科学中研究最深入的经典问题之一——排序。从最朴素的冒泡到精妙的快速排序，下一章带你领略排序算法的演进之路。