第 11 章

二叉搜索树与平衡树

第十一章：二叉搜索树与平衡树

上一章我们学习了二叉树的遍历和递归思维。但普通二叉树没有任何"顺序"约束——你无法高效地搜索一个值。二叉搜索树（BST） 加上了一条简单的规则：左 < 根 < 右，就把一棵树变成了高效的搜索结构。

问题在于，BST 的性能完全取决于树的高度。如果插入的数据恰好是有序的，BST 就退化成链表，搜索变成 O(n)。为了解决这个问题，人们发明了各种自平衡二叉搜索树：AVL 树、红黑树、Treap、Splay 树……它们用不同的策略保证树的高度始终是 O(log n)。

这一章内容量大，但核心思想只有两个：(1) BST 的有序性质如何支撑高效操作；(2) 旋转如何恢复平衡。

Level 1 · 你需要知道的

11.1 BST 的定义和性质

二叉搜索树（Binary Search Tree） 是一棵二叉树，满足以下性质：

左子树中所有节点的值 < 根节点的值
右子树中所有节点的值 > 根节点的值
左子树和右子树本身也是 BST

注意：这里说的是所有节点，不只是直接子节点。常见错误是只检查左子节点 < 根，而忽略了左子树中更深层的节点也必须小于根。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

BST 最重要的性质：对 BST 做中序遍历（左 → 根 → 右），得到的序列是严格递增的。

def inorder(root):
    """对 BST 做中序遍历，结果是有序的"""
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# 例：BST:
#       5
#      / \
#     3   7
#    / \   \
#   2   4   8
# 中序遍历结果：[2, 3, 4, 5, 7, 8]

这个性质是 BST 的灵魂。很多面试题（如"BST 中第 K 小的元素"）本质上就是在利用中序遍历的有序性。

11.2 BST 基本操作

搜索：O(h)

def search_bst(root, target):
    """在 BST 中搜索目标值，返回对应节点或 None"""
    if not root:
        return None
    if target == root.val:
        return root
    elif target < root.val:
        return search_bst(root.left, target)
    else:
        return search_bst(root.right, target)

每次比较排除一半的子树，类似二分搜索。时间复杂度是 O(h)，其中 h 是树的高度。

迭代版本更节省栈空间：

def search_bst_iterative(root, target):
    node = root
    while node:
        if target == node.val:
            return node
        elif target < node.val:
            node = node.left
        else:
            node = node.right
    return None

插入：O(h)

BST 的插入始终在叶子位置：

def insert_bst(root, val):
    """向 BST 中插入一个值，返回根节点"""
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    elif val > root.val:
        root.right = insert_bst(root.right, val)
    # val == root.val 时不插入（不允许重复）
    return root

删除：三种情况

删除是 BST 最复杂的操作，分三种情况：

删除叶子节点：直接删除
删除只有一个子节点的节点：用子节点替代
删除有两个子节点的节点：用中序后继（右子树的最小值）或中序前驱（左子树的最大值）替代，然后递归删除替代节点

def delete_bst(root, key):
    """从 BST 中删除值为 key 的节点"""
    if not root:
        return None
    
    if key < root.val:
        root.left = delete_bst(root.left, key)
    elif key > root.val:
        root.right = delete_bst(root.right, key)
    else:
        # 找到了要删除的节点
        # 情况 1 & 2：没有子节点或只有一个子节点
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # 情况 3：有两个子节点
        # 找中序后继（右子树最小值）
        successor = root.right
        while successor.left:
            successor = successor.left
        # 用后继的值替换当前节点
        root.val = successor.val
        # 递归删除后继节点
        root.right = delete_bst(root.right, successor.val)
    
    return root

为什么用中序后继？ 中序后继是右子树中最小的节点，它比当前节点大，比右子树中所有其他节点小，用它替代当前节点后仍然满足 BST 性质。

11.3 BST 退化问题

如果按照有序序列 [1, 2, 3, 4, 5] 依次插入 BST，会得到什么？

一棵退化成链表的 BST！此时搜索的时间复杂度从 O(log n) 退化为 O(n)。

树的形态	高度 h	搜索/插入/删除
完美平衡	O(log n)	O(log n)
随机插入（平均）	O(log n)	O(log n)
有序插入（最坏）	O(n)	O(n)

这就是为什么我们需要自平衡 BST：通过旋转等操作，保证树的高度始终是 O(log n)。

11.4 AVL 树概述

AVL 树是第一种自平衡二叉搜索树，由苏联数学家 Adelson-Velsky 和 Landis 于 1962 年提出。

核心思想：每个节点维护一个平衡因子（Balance Factor）：

平衡因子 = 左子树高度 - 右子树高度

AVL 树要求每个节点的平衡因子只能是 -1、0 或 1。如果插入或删除操作导致某个节点的平衡因子变成 -2 或 2，就需要通过旋转来恢复平衡。

四种旋转：

失衡类型	失衡模式	修复方法
LL（左左）	在左子树的左子树插入	右旋
RR（右右）	在右子树的右子树插入	左旋
LR（左右）	在左子树的右子树插入	先左旋后右旋
RL（右左）	在右子树的左子树插入	先右旋后左旋

右旋示意（修复 LL 失衡）：

    z                y
   / \             /   \
  y   T4   →     x     z
 / \            / \   / \
x   T3         T1 T2 T3 T4
/ \
T1 T2

左旋示意（修复 RR 失衡）：

  z                  y
 / \               /   \
T1   y    →       z     x
    / \          / \   / \
   T2   x      T1 T2 T3 T4
       / \
      T3  T4

LR 双旋（先对 y 左旋，再对 z 右旋）：

    z              z              x
   / \            / \           /   \
  y   T4  →     x   T4  →    y     z
 / \           / \           / \   / \
T1  x         y   T3       T1 T2 T3 T4
   / \       / \
  T2  T3    T1  T2

RL 双旋（先对 y 右旋，再对 z 左旋）：

  z              z                x
 / \            / \             /   \
T1   y   →    T1   x    →    z     y
    / \           / \        / \   / \
   x   T4       T2  y      T1 T2 T3 T4
  / \               / \
 T2  T3            T3  T4

11.5 Python 中的实践

Python 标准库没有内置 BST 实现。在实际工程和竞赛中，最常用的替代方案是 sortedcontainers 库：

from sortedcontainers import SortedList, SortedDict, SortedSet

# SortedList — 自动维护有序的列表
sl = SortedList([5, 1, 3, 7, 2])
print(sl)  # SortedList([1, 2, 3, 5, 7])

sl.add(4)       # O(log n) 插入
sl.remove(3)    # O(log n) 删除
print(sl[2])    # O(log n) 按索引访问

# 查找范围
print(sl.irange(2, 5))  # 2 到 5 之间的所有元素

# SortedDict — 按 key 有序的字典
sd = SortedDict({'b': 2, 'a': 1, 'c': 3})
print(sd.keys())   # SortedKeysView(['a', 'b', 'c'])
print(sd.peekitem(0))   # ('a', 1) — 最小键
print(sd.peekitem(-1))  # ('c', 3) — 最大键

sortedcontainers 底层用的不是树，而是"分段列表"（类似于 B 树的思想），但它提供了和平衡 BST 相同的 O(log n) 保证，而且在实际测试中通常比纯树实现更快（利用了 CPU 缓存局部性）。

在面试中，如果题目需要有序数据结构且允许使用库，SortedList 是 Python 程序员的首选。

Level 2 · 深入掌握

11.6 AVL 树完整实现

下面是一个完整的 AVL 树 Python 实现，包含插入、删除和旋转：

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # 新节点高度为 1

class AVLTree:
    def get_height(self, node):
        if not node:
            return 0
        return node.height
    
    def get_balance(self, node):
        """计算平衡因子 = 左子树高度 - 右子树高度"""
        if not node:
            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
        
        # 更新高度（先更新 z，再更新 y，因为 y 现在是父节点）
        self.update_height(z)
        self.update_height(y)
        
        return y  # 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  # y 成为新的根
    
    def insert(self, root, val):
        """插入节点并保持 AVL 平衡"""
        # 1. 标准 BST 插入
        if not root:
            return AVLNode(val)
        if val < root.val:
            root.left = self.insert(root.left, val)
        elif val > root.val:
            root.right = self.insert(root.right, val)
        else:
            return root  # 不允许重复值
        
        # 2. 更新当前节点的高度
        self.update_height(root)
        
        # 3. 计算平衡因子
        balance = self.get_balance(root)
        
        # 4. 如果失衡，有四种情况
        # LL：左子树的左子树过高
        if balance > 1 and val < root.left.val:
            return self.right_rotate(root)
        
        # RR：右子树的右子树过高
        if balance < -1 and val > root.right.val:
            return self.left_rotate(root)
        
        # LR：左子树的右子树过高
        if balance > 1 and val > root.left.val:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        
        # RL：右子树的左子树过高
        if balance < -1 and val < root.right.val:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)
        
        return root
    
    def get_min_node(self, node):
        """获取以 node 为根的子树中最小的节点"""
        current = node
        while current.left:
            current = current.left
        return current
    
    def delete(self, root, val):
        """删除节点并保持 AVL 平衡"""
        # 1. 标准 BST 删除
        if not root:
            return None
        
        if val < root.val:
            root.left = self.delete(root.left, val)
        elif val > root.val:
            root.right = self.delete(root.right, val)
        else:
            # 找到要删除的节点
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                # 有两个子节点：用中序后继替代
                successor = self.get_min_node(root.right)
                root.val = successor.val
                root.right = self.delete(root.right, successor.val)
        
        # 2. 更新高度
        self.update_height(root)
        
        # 3. 计算平衡因子
        balance = self.get_balance(root)
        
        # 4. 重新平衡（删除时需要检查子树的平衡因子）
        # LL
        if balance > 1 and self.get_balance(root.left) >= 0:
            return self.right_rotate(root)
        
        # LR
        if balance > 1 and self.get_balance(root.left) < 0:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        
        # RR
        if balance < -1 and self.get_balance(root.right) <= 0:
            return self.left_rotate(root)
        
        # RL
        if balance < -1 and self.get_balance(root.right) > 0:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)
        
        return root
    
    def inorder(self, root):
        """中序遍历验证 BST 性质"""
        if not root:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)


# 使用示例
avl = AVLTree()
root = None

# 按顺序插入 1-7，如果是普通 BST 会退化成链表
for val in [1, 2, 3, 4, 5, 6, 7]:
    root = avl.insert(root, val)

print(avl.inorder(root))  # [1, 2, 3, 4, 5, 6, 7]
print(root.val)            # 4（根节点，平衡的！）
print(avl.get_height(root) - 1)  # 高度 = 2（接近 log2(7) ≈ 2.8）

插入和删除的关键区别：

插入时，只需要判断新值插入到失衡节点的哪个方向（通过比较 val 和子节点值）
删除时，需要检查子节点的平衡因子来确定旋转类型（因为删除可能发生在任何位置）

11.7 红黑树

红黑树是工程实践中最常用的自平衡 BST。它不追求像 AVL 树那样严格的平衡，而是允许一定程度的不平衡，从而减少旋转次数。

红黑树的五条性质

每个节点是红色或黑色
根节点是黑色
每个叶子节点（NIL/空节点）是黑色
红色节点的两个子节点都是黑色（不能有连续的红色节点）
从任意节点到其所有后代叶子节点的路径上，黑色节点数目相同（黑高相等）

为什么这五条性质能保证 O(log n)？

关键在于性质 4 和 5 的组合：

性质 5 保证所有路径的黑色节点数目相同，设为 B
性质 4 保证红色节点不相邻，所以最长路径上的红色节点数最多为 B
因此最长路径 ≤ 2B，最短路径 ≥ B
最长路径不超过最短路径的 2 倍

这意味着红黑树的高度最多是 2 * log₂(n+1)，所有操作的时间复杂度为 O(log n)。

红黑树 vs AVL 树

对比维度	AVL 树	红黑树
平衡严格度	高度差 ≤ 1	最长路径 ≤ 2 * 最短路径
搜索性能	略优（更矮）	略差（可能更高）
插入/删除性能	旋转次数多	旋转次数少（最多 3 次）
适用场景	读多写少（数据库索引）	读写均衡（通用容器）
实际应用	Windows NT 内核	Linux 内核、Java TreeMap

核心直觉：AVL 树更"完美"，红黑树更"实用"。红黑树允许轻微的不平衡换取更少的旋转操作，在频繁插入删除的场景下整体性能更好。

红黑树的插入修复

新插入的节点总是红色（如果插入黑色节点，会破坏性质 5）。如果父节点也是红色，就违反了性质 4，需要修复。

三种修复情况（假设父节点 P 是祖父节点 G 的左子节点）：

情况 1：叔叔节点 U 是红色

将 P 和 U 变黑，G 变红
将 G 作为新的"问题节点"，向上递归检查

      G(B)                G(R)  ← 可能继续违反
     / \                 / \
   P(R)  U(R)    →    P(B)  U(B)
   /                   /
 X(R)                X(R)

情况 2：叔叔节点 U 是黑色，X 是 P 的右子节点

对 P 做左旋，转化为情况 3

    G(B)              G(B)
   / \               / \
 P(R)  U(B)   →   X(R)  U(B)
   \               /
   X(R)          P(R)

情况 3：叔叔节点 U 是黑色，X 是 P 的左子节点

对 G 做右旋，然后交换 P 和 G 的颜色

      G(B)              P(B)
     / \               / \
   P(R)  U(B)   →   X(R)  G(R)
   /                         \
 X(R)                        U(B)

如果 P 是 G 的右子节点，情况是对称的。

红黑树的删除修复

删除比插入更复杂，主要处理"双黑"问题（删除一个黑色节点后，其替代节点携带了"额外的黑色"）。这里不展开完整代码，因为红黑树的删除修复有 8 种情况（4 种 + 对称的 4 种），工程中通常直接使用标准库实现。

11.8 Treap（Tree + Heap）

Treap 是一种随机化的平衡 BST，每个节点有两个属性：

key：满足 BST 性质（中序遍历有序）
priority：满足堆性质（父节点优先级 ≥ 子节点优先级）

由于 priority 是随机分配的，Treap 的期望高度是 O(log n)。

import random

class TreapNode:
    def __init__(self, key):
        self.key = key
        self.priority = random.random()  # 随机优先级
        self.left = None
        self.right = None

class Treap:
    def _right_rotate(self, node):
        left = node.left
        node.left = left.right
        left.right = node
        return left
    
    def _left_rotate(self, node):
        right = node.right
        node.right = right.left
        right.left = node
        return right
    
    def insert(self, root, key):
        """插入后通过旋转维护堆性质"""
        if not root:
            return TreapNode(key)
        
        if key < root.key:
            root.left = self.insert(root.left, key)
            # 如果左子节点优先级更高，右旋
            if root.left.priority > root.priority:
                root = self._right_rotate(root)
        elif key > root.key:
            root.right = self.insert(root.right, key)
            # 如果右子节点优先级更高，左旋
            if root.right.priority > root.priority:
                root = self._left_rotate(root)
        
        return root
    
    def delete(self, root, key):
        """删除：将节点旋转到叶子位置再删除"""
        if not root:
            return None
        
        if key < root.key:
            root.left = self.delete(root.left, key)
        elif key > root.key:
            root.right = self.delete(root.right, key)
        else:
            # 找到要删除的节点
            if not root.left and not root.right:
                return None  # 叶子节点，直接删除
            elif not root.left:
                root = self._left_rotate(root)
                root.left = self.delete(root.left, key)
            elif not root.right:
                root = self._right_rotate(root)
                root.right = self.delete(root.right, key)
            else:
                # 两个子节点都存在，将优先级高的旋转上来
                if root.left.priority > root.right.priority:
                    root = self._right_rotate(root)
                    root.right = self.delete(root.right, key)
                else:
                    root = self._left_rotate(root)
                    root.left = self.delete(root.left, key)
        
        return root


# 使用示例
treap = Treap()
root = None
for val in [1, 2, 3, 4, 5, 6, 7]:  # 顺序插入不会退化！
    root = treap.insert(root, val)

Treap 的优势：

实现比红黑树简单得多（只需要两种旋转）
期望时间复杂度 O(log n)，常数因子小
支持高效的分裂（split）和合并（merge）操作
在竞赛中非常流行

Treap 的劣势：

最坏情况是 O(n)（概率极小，但存在）
不是确定性的（依赖随机数生成器）

11.9 B 树简介

B 树是一种多路搜索树，每个节点可以有多个键和多个子节点。它是数据库和文件系统索引的核心数据结构。

B 树的特点：

每个节点最多有 m 个子节点（m 阶 B 树）
非根非叶节点至少有 ⌈m/2⌉ 个子节点
所有叶子节点在同一层

为什么数据库用 B 树而不用红黑树？因为磁盘 I/O 的代价远高于内存访问，B 树通过增加节点的"宽度"来减少树的"高度"，从而减少磁盘访问次数。

我们将在第 20 章详细讨论 B 树和 B+ 树的实现。

Level 3 · 历史与工程

11.10 AVL 树的历史

AVL 树由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 于 1962 年在论文 "An algorithm for the organization of information" 中提出。这是人类历史上第一个自平衡二叉搜索树。

Adelson-Velsky（1922-2014）是一位传奇人物。他不仅是 AVL 树的发明者，还是计算机国际象棋的先驱——他开发的 Kaissa 程序在 1974 年赢得了第一届世界计算机国际象棋锦标赛。

AVL 树的论文发表时，整个计算机科学领域还处于婴儿期。这项工作的重要性在于它证明了一个关键的可能性：可以在每次插入/删除后花 O(log n) 的额外工作来维持树的平衡，从而保证所有操作的最坏情况时间复杂度为 O(log n)。

11.11 红黑树的历史

红黑树的历史比很多人想象的更曲折：

1972 年：Rudolf Bayer 发明了"对称二叉 B 树"（Symmetric Binary B-trees）。这本质上就是红黑树，但当时还没有"红黑"这个名字。
1978 年：Leo Guibas 和 Robert Sedgewick 在论文 "A Dichromatic Framework for Balanced Trees" 中给出了"红黑树"这个名字。据 Sedgewick 在后来的采访中回忆，他们选择红色和黑色是因为当时 Xerox PARC 的激光打印机能打印红色和黑色两种颜色，论文中的图看起来很漂亮。
1993 年：Arne Andersson 提出了"左倾红黑树"（Left-Leaning Red-Black Tree, LLRB），简化了实现。
2008 年：Robert Sedgewick 在他的 Algorithms 教材中进一步推广了 LLRB，用约 50 行代码实现了完整的红黑树。

红黑树是教科书和工业界中最广泛使用的平衡 BST，原因很简单：它在各种工作负载下都表现良好，且实现虽然复杂但确定性强。

11.12 Linux CFS 调度器中的红黑树

Linux 内核的 CFS（Completely Fair Scheduler，完全公平调度器）由 Ingo Molnar 于 2007 年开发，在 Linux 2.6.23 中引入，是红黑树的一个经典应用。

问题：操作系统需要决定哪个进程/线程获得 CPU 时间。目标是"公平"——每个进程获得与其权重成比例的 CPU 时间。

CFS 的设计：

每个可运行的进程用一个节点表示
节点的 key 是进程的"虚拟运行时间"（vruntime）——进程已经使用的 CPU 时间（按权重归一化）
所有可运行进程按 vruntime 组织在一棵红黑树中
调度决策：总是选择 vruntime 最小的进程（红黑树的最左节点）
一个进程运行后，其 vruntime 增加，重新插入红黑树

为什么用红黑树？

插入和删除是 O(log n)，n 是可运行进程数
查找最小值是 O(1)（缓存最左节点）
红黑树比 AVL 树在频繁插入删除时更高效
不能用堆（需要高效删除任意节点）

从 Linux 6.6（2023年10月）开始，CFS 被替换为 EEVDF（Earliest Eligible Virtual Deadline First）调度器，但底层仍然使用红黑树作为核心数据结构。

11.13 Java TreeMap/TreeSet

Java 标准库的 TreeMap 和 TreeSet 是基于红黑树实现的：

// Java TreeMap 的关键源码（简化版）
public class TreeMap<K,V> {
    private transient Entry<K,V> root;
    
    static final class Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;  // 红黑树颜色
    }
    
    // 插入后修复红黑树性质
    private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED;
        while (x != null && x != root && x.parent.color == RED) {
            // ... 三种情况的修复逻辑 ...
        }
        root.color = BLACK;
    }
}

Java 集合框架中的有序结构对比：

数据结构	底层实现	搜索	插入	有序遍历
HashMap	哈希表+红黑树	O(1) 平均	O(1) 平均	不支持
TreeMap	红黑树	O(log n)	O(log n)	支持
LinkedHashMap	哈希表+双向链表	O(1) 平均	O(1) 平均	按插入序

注意 Java 8 之后，HashMap 在哈希冲突严重时（同一个桶中链表长度超过 8），会将链表转换为红黑树，这是对最坏情况的优化。

11.14 Splay 树

Splay 树由 Daniel Sleator 和 Robert Tarjan 于 1985 年提出。它的核心思想是自调整：每次访问一个节点后，通过一系列旋转（称为"展开"，splay）将该节点移到根位置。

关键特性：

没有显式的平衡条件（不存储高度或颜色）
单次操作的最坏情况是 O(n)
但 m 次操作的摊还时间是 O(m log n)
具有"工作集"性质：最近访问的元素查找更快

class SplayNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class SplayTree:
    def _right_rotate(self, x):
        y = x.left
        x.left = y.right
        y.right = x
        return y
    
    def _left_rotate(self, x):
        y = x.right
        x.right = y.left
        y.left = x
        return y
    
    def splay(self, root, key):
        """将 key 对应的节点旋转到根"""
        if not root or root.key == key:
            return root
        
        if key < root.key:
            if not root.left:
                return root
            # Zig-Zig（LL）
            if key < root.left.key:
                root.left.left = self.splay(root.left.left, key)
                root = self._right_rotate(root)
            # Zig-Zag（LR）
            elif key > root.left.key:
                root.left.right = self.splay(root.left.right, key)
                if root.left.right:
                    root.left = self._left_rotate(root.left)
            return self._right_rotate(root) if root.left else root
        
        else:  # key > root.key
            if not root.right:
                return root
            # Zag-Zig（RL）
            if key < root.right.key:
                root.right.left = self.splay(root.right.left, key)
                if root.right.left:
                    root.right = self._right_rotate(root.right)
            # Zag-Zag（RR）
            elif key > root.right.key:
                root.right.right = self.splay(root.right.right, key)
                root = self._left_rotate(root)
            return self._left_rotate(root) if root.right else root
    
    def search(self, root, key):
        """搜索并将节点展开到根"""
        root = self.splay(root, key)
        if root and root.key == key:
            return root
        return None

Splay 树的应用场景：

缓存系统（最近访问的数据在根附近，访问更快）
网络路由表
垃圾回收器中的内存管理

Splay 树 vs 红黑树：

Splay 树在有局部性的访问模式下更快
红黑树在均匀随机访问下更稳定
Splay 树不需要额外空间存储平衡信息

Level 4 · 实战陷阱与面试

11.15 BST 删除的常见陷阱

BST 删除中使用前驱/后继替代法时，有几个容易出错的地方：

陷阱 1：忘记处理后继就是右子节点的情况

# 错误代码：假设后继一定有父节点且不是直接右子节点
def delete_wrong(root, key):
    # ... 找到节点 ...
    # 找后继
    successor = node.right
    parent = node
    while successor.left:
        parent = successor
        successor = successor.left
    # 这里如果 successor == node.right，
    # parent.left = successor.right 就是错误的！
    parent.left = successor.right  # BUG when successor is node.right

陷阱 2：用"值替换"法丢失节点引用

我们在 Level 1 的实现中用了 root.val = successor.val（值替换法），这在面试中是可以接受的。但在实际工程中，如果有外部引用指向被替换的节点，值替换会导致问题。工程级实现应该做"指针替换"——真正把后继节点移到被删除节点的位置。

陷阱 3：删除后忘记更新平衡信息

在 AVL 树中，删除后需要从删除位置向上逐层更新高度和平衡因子，而且可能需要多次旋转（不像插入只需要一次旋转就能修复）。

11.16 红黑树面试策略

红黑树在面试中的考察方式通常不是让你手写完整实现（那需要 200+ 行代码），而是考察你对性质和应用场景的理解。

常见面试问题和参考回答：

Q: 为什么红黑树比 AVL 树更常用？

A: 红黑树允许更宽松的平衡（最长路径不超过最短路径的 2 倍），这意味着插入和删除时需要的旋转次数更少。AVL 树的严格平衡在读多写少的场景有优势（如数据库索引），但在通用容器（如 Java TreeMap、C++ std::map）中，读写频率接近时红黑树的综合性能更好。

Q: HashMap 什么时候会用到红黑树？

A: Java 8 的 HashMap 在一个桶中的链表长度超过 8 时，会将链表转换为红黑树。这是为了防止哈希碰撞攻击——攻击者可以构造大量具有相同哈希值的 key，使得 HashMap 退化为 O(n) 查找。转换为红黑树后，最坏情况变为 O(log n)。

Q: 红黑树的高度上界是多少？

A: 2 * log₂(n+1)。证明思路：黑高为 h_b 的红黑树至少有 2^h_b - 1 个内部节点；由于红色节点不相邻，树的总高度最多是 2 * h_b。

11.17 面试高频题详解

LeetCode 98: 验证二叉搜索树

题意：给定一棵二叉树，判断它是否是合法的 BST。

关键陷阱：不能只比较每个节点和它的直接子节点，必须确保左子树中所有节点都小于根，右子树中所有节点都大于根。

def isValidBST(root):
    """
    方法 1：递归传递上下界
    时间 O(n)，空间 O(h)
    """
    def validate(node, low, high):
        if not node:
            return True
        if node.val <= low or node.val >= high:
            return False
        return (validate(node.left, low, node.val) and 
                validate(node.right, node.val, high))
    
    return validate(root, float('-inf'), float('inf'))


def isValidBST_inorder(root):
    """
    方法 2：中序遍历必须严格递增
    时间 O(n)，空间 O(h)
    """
    prev = float('-inf')
    
    def inorder(node):
        nonlocal prev
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev:
            return False
        prev = node.val
        return inorder(node.right)
    
    return inorder(root)

面试提示：方法 1 最直观也最容易在面试中写对。注意边界用 float('-inf') 和 float('inf')，不要用具体的整数值（题目中 node.val 可能等于 INT_MIN 或 INT_MAX）。

LeetCode 230: BST 中第 K 小的元素

题意：给定 BST 的根节点和整数 k，返回第 k 小的节点值。

def kthSmallest(root, k):
    """
    中序遍历到第 k 个就停止
    时间 O(H + k)，空间 O(H)，H 是树的高度
    """
    stack = []
    node = root
    count = 0
    
    while stack or node:
        # 一路向左
        while node:
            stack.append(node)
            node = node.left
        
        node = stack.pop()
        count += 1
        if count == k:
            return node.val
        
        node = node.right
    
    return -1  # 不应该走到这里

进阶：如果这棵 BST 经常被修改（插入/删除），且频繁查找第 k 小的元素，可以在每个节点额外存储"左子树的节点数"，这样查找第 k 小变成 O(log n)。这就是Order-Statistic Tree（顺序统计树）。

LeetCode 108: 将有序数组转换为平衡 BST

题意：给定升序排列的整数数组，将其转换为一棵高度平衡的 BST。

def sortedArrayToBST(nums):
    """
    每次取中间元素作为根，递归构建左右子树
    时间 O(n)，空间 O(log n)（递归栈）
    """
    def build(left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        node.left = build(left, mid - 1)
        node.right = build(mid + 1, right)
        return node
    
    return build(0, len(nums) - 1)

为什么取中间元素？ 中间元素作为根，左右两边的元素数量最接近，保证构建出来的树是平衡的。这本质上是分治思想。

LeetCode 450: 删除 BST 中的节点

这题就是 11.2 节中的删除操作。关键是处理好三种情况，特别是有两个子节点时用中序后继替代。

def deleteNode(root, key):
    if not root:
        return None
    
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        # 情况 1 & 2
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # 情况 3：找中序后继
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = deleteNode(root.right, successor.val)
    
    return root

11.18 BST vs 哈希表：何时选择哪个

这是一个高频的系统设计面试问题。

需求	BST (TreeMap)	哈希表 (HashMap)
精确查找	O(log n)	O(1) 平均
范围查询（如 key 在 [a, b] 之间的所有值）	O(log n + k)	不支持
找最小/最大值	O(log n) 或 O(1)	O(n)
按序遍历	O(n)	O(n log n)（需排序）
找前驱/后继	O(log n)	不支持
空间利用率	较差（指针开销）	较好
最坏情况	O(log n)（平衡树）	O(n)（哈希碰撞）

简单决策规则：

如果只需要"存在性查询"或"精确查找"，用哈希表
如果需要"有序性"（范围查询、排名、前驱后继），用 BST/TreeMap
如果两种需求都有，考虑同时维护两种结构，或用 sortedcontainers

经典例题：

"设计一个支持 insert/delete/getRandom 的数据结构"→ 哈希表 + 数组
"设计一个支持 insert/delete/getMin 的数据结构"→ 平衡 BST 或堆
"设计一个支持范围查询的数据结构"→ 平衡 BST

本章小结

数据结构	搜索	插入	删除	特点
BST（无平衡）	O(h)	O(h)	O(h)	h 可能退化为 n
AVL 树	O(log n)	O(log n)	O(log n)	严格平衡，读多写少场景好
红黑树	O(log n)	O(log n)	O(log n)	宽松平衡，工程首选
Treap	O(log n) 期望	O(log n) 期望	O(log n) 期望	实现简单，竞赛常用
Splay 树	O(log n) 摊还	O(log n) 摊还	O(log n) 摊还	局部性好时性能佳
B 树	O(log n)	O(log n)	O(log n)	磁盘 I/O 友好，数据库索引

核心要点：

BST 的中序遍历是有序的——这是它一切性质的基础
旋转是所有平衡树的核心操作——它改变树的形状但保持 BST 性质
AVL 树用高度差衡量平衡，红黑树用颜色规则衡量平衡
红黑树在工程中更常用，因为它在读写混合负载下旋转次数更少
面试中，BST 的验证、搜索、删除是高频考点；红黑树只需理解性质不需手写

下一章预告：第 12 章我们将学习堆（Heap）和优先队列——一种只需要部分有序性的树形结构，它放弃了全局有序来换取更快的最值操作。

本章评分

4.8 / 5 (34 评分)