第12章二叉搜索树理论

本章导读

二叉搜索树（BST）是最基础且最重要的有序数据结构之一，是平衡树、B树等高级数据结构的基础。本章从形式化角度深入分析BST的数学基础，包括BST性质的数学定义、操作正确性证明、期望复杂度分析，以及BST与排序问题的理论联系。

学习目标

完成本章学习后，读者将能够：

掌握BST性质的形式化定义与不变式
理解BST操作的正确性证明
掌握BST期望复杂度的概率分析
理解BST与比较排序的理论联系
掌握BST的变体与应用

12.1 二叉搜索树的形式化定义

12.1.1 BST性质的数学定义

定义 12.1（二叉搜索树性质） 二叉搜索树是一棵二叉树，满足对于每个节点 $x$：

$$\forall y \in left_subtree(x): key(y) < key(x)$$

$$\forall y \in right_subtree(x): key(y) > key(x)$$

定义 12.2（BST不变式） BST不变式定义为：

$$Invariant(T) = \forall x \in T, \forall y \in left(x), \forall z \in right(x): key(y) < key(x) < key(z)$$

定理 12.1（BST中序有序性） 对BST进行中序遍历，输出序列严格递增。

证明：对树的高度进行归纳。

基础情况：空树的中序遍历为空序列，显然有序。

归纳步骤：设BST $T$ 的根为 $r$，左子树为 $T_L$，右子树为 $T_R$。

中序遍历输出为：$inorder(T_L) \cdot [r] \cdot inorder(T_R)$

由BST性质，$T_L$ 中所有键 < $key(r)$ < $T_R$ 中所有键。

由归纳假设，$inorder(T_L)$ 和 $inorder(T_R)$ 都是递增序列。

因此连接后的序列递增。∎

12.1.2 BST ADT规范

ADT 12.1（BinarySearchTree）

ADT BinarySearchTree[K: Ordered]
  Types: BinarySearchTree[K]
  
  Operations:
    empty: → BinarySearchTree[K]
    insert: BinarySearchTree[K] × K → BinarySearchTree[K]
    delete: BinarySearchTree[K] × K → BinarySearchTree[K]
    search: BinarySearchTree[K] × K → Boolean
    min: BinarySearchTree[K] → K
    max: BinarySearchTree[K] → K
    successor: BinarySearchTree[K] × K → K
    predecessor: BinarySearchTree[K] × K → K
  
  Axioms:
    ∀t: BinarySearchTree[K], ∀k: K
    (A1) search(empty, k) = false
    (A2) search(insert(t, k), k) = true
    (A3) k' ≠ k → search(insert(t, k), k') = search(t, k')
    (A4) min(insert(empty, k)) = k
    (A5) k < min(t) → min(insert(t, k)) = k
    (A6) k > min(t) → min(insert(t, k)) = min(t)
    (A7) delete(insert(empty, k), k) = empty
    (A8) BST不变式在所有操作后保持

定理 12.2（BST ADT一致性） BST ADT的公理系统是一致的。

证明：构造具体模型。设BST为满足BST性质的二叉树。

$empty = \emptyset$
$insert(T, k)$ 在正确位置插入新节点
$search(T, k)$ 沿树向下搜索
$delete(T, k)$ 找到节点后按规则删除

所有操作保持BST不变式，公理成立。∎

12.2 BST操作与正确性证明

12.2.1 查找操作

算法 12.1（BST查找）

TREE-SEARCH(x, k)
    if x == NIL or k == x.key
        return x
    if k < x.key
        return TREE-SEARCH(x.left, k)
    else
        return TREE-SEARCH(x.right, k)

定理 12.3（查找正确性） 若 $k$ 在BST中，TREE-SEARCH返回包含 $k$ 的节点；否则返回NIL。

证明：对树的高度进行归纳。

基础情况：空树返回NIL，正确。

归纳步骤：设当前节点为 $x$。

若 $k = x.key$，返回 $x$，正确
若 $k < x.key$，由BST性质，$k$ 只能在左子树，递归搜索左子树
若 $k > x.key$，由BST性质，$k$ 只能在右子树，递归搜索右子树

由归纳假设，递归调用正确返回。∎

12.2.2 插入操作

算法 12.2（BST插入）

TREE-INSERT(T, z)
    y = NIL
    x = T.root
    while x != NIL
        y = x
        if z.key < x.key
            x = x.left
        else
            x = x.right
    z.p = y
    if y == NIL
        T.root = z
    else if z.key < y.key
        y.left = z
    else
        y.right = z

定理 12.4（插入正确性） TREE-INSERT将新节点插入正确位置，且保持BST性质。

证明：算法沿树向下找到插入位置，该位置是唯一满足BST性质的位置。

设插入位置为 $y$ 的子节点位置。由搜索路径：

路径上所有左转节点的键 > $z.key$
路径上所有右转节点的键 < $z.key$

因此插入后BST性质保持。∎

12.2.3 删除操作

定理 12.5（后继存在性） 若节点 $x$ 有右子树，则 $x$ 的后继是右子树的最小节点。

证明：设 $x$ 的右子树为 $T_R$。$T_R$ 的最小节点 $y$ 满足：

$y > x$（因为 $y \in T_R$）
不存在 $z$ 使得 $x < z < y$（否则 $z$ 在 $T_R$ 中且比 $y$ 小，矛盾）

因此 $y$ 是 $x$ 的后继。∎

定理 12.6（删除正确性） BST删除操作保持BST性质。

证明：分三种情况：

叶子节点：直接删除，不影响其他节点
只有一个子节点：用子节点替换，BST性质保持
两个子节点：用后继替换，然后删除后继（转化为情况1或2）

后继替换的正确性：设用后继 $y$ 替换 $x$。$y$ 是右子树的最小节点，因此：

$y$ 的左子树为空
$y$ 的值大于左子树所有值，小于右子树其他值

因此替换后BST性质保持。∎

12.2.4 BST实现

python

from typing import TypeVar, Generic, Optional, List, Iterator, Callable

K = TypeVar('K')

class BSTNode(Generic[K]):
    """BST节点"""
    __slots__ = ['key', 'left', 'right', 'parent']
    
    def __init__(self, key: K):
        self.key = key
        self.left: Optional['BSTNode[K]'] = None
        self.right: Optional['BSTNode[K]'] = None
        self.parent: Optional['BSTNode[K]'] = None


class BinarySearchTree(Generic[K]):
    """
    二叉搜索树实现
    
    时间复杂度：
    - 查找：O(h)，平均O(log n)，最坏O(n)
    - 插入：O(h)，平均O(log n)，最坏O(n)
    - 删除：O(h)，平均O(log n)，最坏O(n)
    
    空间复杂度：O(n)
    """
    
    def __init__(self):
        self._root: Optional[BSTNode[K]] = None
        self._size: int = 0
    
    def search(self, key: K) -> Optional[BSTNode[K]]:
        """查找 - O(h)"""
        current = self._root
        while current:
            if key == current.key:
                return current
            elif key < current.key:
                current = current.left
            else:
                current = current.right
        return None
    
    def contains(self, key: K) -> bool:
        """判断是否包含 - O(h)"""
        return self.search(key) is not None
    
    def insert(self, key: K) -> bool:
        """插入 - O(h)，返回是否插入成功"""
        new_node = BSTNode(key)
        
        if not self._root:
            self._root = new_node
            self._size += 1
            return True
        
        parent = None
        current = self._root
        
        while current:
            parent = current
            if key == current.key:
                return False
            elif key < current.key:
                current = current.left
            else:
                current = current.right
        
        new_node.parent = parent
        if key < parent.key:
            parent.left = new_node
        else:
            parent.right = new_node
        
        self._size += 1
        return True
    
    def _transplant(self, u: BSTNode[K], v: Optional[BSTNode[K]]) -> None:
        """用子树v替换子树u"""
        if not u.parent:
            self._root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        
        if v:
            v.parent = u.parent
    
    def _minimum_node(self, node: Optional[BSTNode[K]]) -> Optional[BSTNode[K]]:
        """找最小节点"""
        while node and node.left:
            node = node.left
        return node
    
    def _maximum_node(self, node: Optional[BSTNode[K]]) -> Optional[BSTNode[K]]:
        """找最大节点"""
        while node and node.right:
            node = node.right
        return node
    
    def delete(self, key: K) -> bool:
        """删除 - O(h)"""
        node = self.search(key)
        if not node:
            return False
        
        if not node.left:
            self._transplant(node, node.right)
        elif not node.right:
            self._transplant(node, node.left)
        else:
            successor = self._minimum_node(node.right)
            if successor.parent != node:
                self._transplant(successor, successor.right)
                successor.right = node.right
                successor.right.parent = successor
            self._transplant(node, successor)
            successor.left = node.left
            successor.left.parent = successor
        
        self._size -= 1
        return True
    
    def minimum(self) -> Optional[K]:
        """最小值 - O(h)"""
        node = self._minimum_node(self._root)
        return node.key if node else None
    
    def maximum(self) -> Optional[K]:
        """最大值 - O(h)"""
        node = self._maximum_node(self._root)
        return node.key if node else None
    
    def successor(self, key: K) -> Optional[K]:
        """后继 - O(h)"""
        node = self.search(key)
        if not node:
            return None
        
        if node.right:
            result = self._minimum_node(node.right)
            return result.key if result else None
        
        parent = node.parent
        while parent and node == parent.right:
            node = parent
            parent = parent.parent
        
        return parent.key if parent else None
    
    def predecessor(self, key: K) -> Optional[K]:
        """前驱 - O(h)"""
        node = self.search(key)
        if not node:
            return None
        
        if node.left:
            result = self._maximum_node(node.left)
            return result.key if result else None
        
        parent = node.parent
        while parent and node == parent.left:
            node = parent
            parent = parent.parent
        
        return parent.key if parent else None
    
    def inorder(self) -> List[K]:
        """中序遍历（有序输出）- O(n)"""
        result = []
        
        def _traverse(node: Optional[BSTNode[K]]):
            if node:
                _traverse(node.left)
                result.append(node.key)
                _traverse(node.right)
        
        _traverse(self._root)
        return result
    
    def range_query(self, low: K, high: K) -> List[K]:
        """范围查询 - O(h + k)，k为结果数量"""
        result = []
        
        def _query(node: Optional[BSTNode[K]]):
            if not node:
                return
            
            if low < node.key:
                _query(node.left)
            
            if low <= node.key <= high:
                result.append(node.key)
            
            if node.key < high:
                _query(node.right)
        
        _query(self._root)
        return result
    
    def __len__(self) -> int:
        return self._size
    
    def __contains__(self, key: K) -> bool:
        return self.contains(key)
    
    def __iter__(self) -> Iterator[K]:
        return iter(self.inorder())
    
    def __repr__(self) -> str:
        return f"BST({self.inorder()})"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212

12.3 BST复杂度分析

12.3.1 最坏情况分析

定理 12.7（BST最坏高度） BST的高度可能达到 $n - 1$（退化为链表）。

证明：按递增或递减顺序插入 $n$ 个元素，每个新元素都成为前一个的右子节点（或左子节点），形成高度为 $n - 1$ 的链表。∎

推论 12.1 BST操作的最坏时间复杂度为 $O(n)$。

12.3.2 期望复杂度分析

定义 12.3（随机BST） 随机BST是指从 $n$ 个键的随机排列构建的BST，或等价地，按随机顺序插入 $n$ 个键得到的BST。

定理 12.8（随机BST期望高度） 随机BST的期望高度为 $O(\log n)$。

证明：设 $X_n$ 为 $n$ 个节点的随机BST的高度。定义指示变量：

$$Y_{ij} = \begin{cases} 1 & \text{if } i \text{ is ancestor of } j \ 0 & \text{otherwise} \end{cases}$$

节点 $i$ 是节点 $j$ 的祖先，当且仅当 $i$ 是 $i$ 和 $j$ 之间（包含）第一个被插入的节点。

因此 $P(Y_{ij} = 1) = \frac{1}{|i - j| + 1}$。

树高 $h = \max_{j} \sum_{i \neq j} Y_{ij}$。

通过复杂的概率分析，可证明 $E[h] = O(\log n)$。∎

定理 12.9（随机BST期望搜索代价） 随机BST中成功查找的期望比较次数为：

$$E[C_n] = 2\ln n + O(1) \approx 1.39 \log_2 n$$

证明：设 $D(n)$ 为 $n$ 个节点的随机BST的平均查找路径长度。

$$D(n) = \frac{1}{n}\sum_{i=1}^{n}(D(i-1) + D(n-i) + 1)$$

解得 $D(n) = 2(n+1)H_n - 4n \approx 2n\ln n$。

平均比较次数为 $D(n)/n \approx 2\ln n$。∎

12.3.3 竞争分析

定义 12.4（最优BST） 对于给定的访问序列，最优BST是使总访问代价最小的BST。

定理 12.10（BST竞争比下界） 任何BST算法的竞争比至少为 $\Omega(\log n)$。

证明：存在访问序列使得任何静态BST的总访问代价为 $\Omega(n \log n)$，而最优离线算法的代价为 $O(n)$。∎

12.4 BST与排序

12.4.1 BST排序

定理 12.11（BST排序复杂度） 使用BST对 $n$ 个元素排序：

最好情况：$O(n \log n)$
最坏情况：$O(n^2)$
平均情况：$O(n \log n)$

证明：排序过程包括 $n$ 次插入和 $n$ 次中序遍历。

最好情况：树平衡，每次插入 $O(\log n)$，总 $O(n \log n)$
最坏情况：树退化为链表，插入代价 $1 + 2 + \ldots + n = O(n^2)$
平均情况：由定理 12.8，期望插入代价 $O(\log n)$，总 $O(n \log n)$

中序遍历总是 $O(n)$。∎

12.4.2 与比较排序的联系

定理 12.12（BST与比较排序等价性） BST排序是比较排序的一种实现，其比较次数与决策树高度相关。

证明：BST的形状由比较顺序决定。每次插入对应决策树的一条路径。

$n$ 个元素的决策树高度 $\geq \lceil \log_2(n!) \rceil = \Omega(n \log n)$。

因此BST排序的最坏比较次数 $\Omega(n \log n)$，与一般比较排序下界一致。∎

12.5 BST变体

12.5.1 带频率统计的BST

python

class FrequencyBST(BinarySearchTree[K]):
    """带频率统计的BST"""
    
    def __init__(self):
        super().__init__()
        self._counts: dict = {}
    
    def insert(self, key: K) -> bool:
        if key in self._counts:
            self._counts[key] += 1
            return True
        self._counts[key] = 1
        return super().insert(key)
    
    def count(self, key: K) -> int:
        return self._counts.get(key, 0)
    
    def delete(self, key: K) -> bool:
        if key not in self._counts:
            return False
        
        self._counts[key] -= 1
        if self._counts[key] == 0:
            del self._counts[key]
            return super().delete(key)
        return True

12.5.2 线索二叉搜索树

定义 12.5（线索二叉树） 线索二叉树利用空指针存储前驱/后继信息。

python

class ThreadedBSTNode(Generic[K]):
    """线索BST节点"""
    __slots__ = ['key', 'left', 'right', 'left_thread', 'right_thread']
    
    def __init__(self, key: K):
        self.key = key
        self.left: Optional['ThreadedBSTNode[K]'] = None
        self.right: Optional['ThreadedBSTNode[K]'] = None
        self.left_thread: bool = False
        self.right_thread: bool = False


class ThreadedBST(Generic[K]):
    """
    线索二叉搜索树
    
    特点：
    - 中序遍历无需栈
    - 查找前驱后继O(1)
    - 空间开销：每个节点2个布尔标记
    """
    
    def __init__(self):
        self._root: Optional[ThreadedBSTNode[K]] = None
    
    def inorder_successor(self, node: ThreadedBSTNode[K]) -> Optional[ThreadedBSTNode[K]]:
        """找后继 - O(1)平均"""
        if node.right_thread:
            return node.right
        
        current = node.right
        while current and not current.left_thread:
            current = current.left
        return current
    
    def inorder_traversal(self) -> List[K]:
        """中序遍历 - O(n)，无需栈"""
        result = []
        
        current = self._root
        while current and not current.left_thread:
            current = current.left
        
        while current:
            result.append(current.key)
            current = self.inorder_successor(current)
        
        return result

12.5.3 随机化BST

python

import random

class RandomizedBST(BinarySearchTree[K]):
    """
    随机化BST
    
    通过随机选择根节点保证期望平衡
    期望高度：O(log n)
    """
    
    def insert_at_root(self, key: K) -> bool:
        """在根位置插入"""
        def _split(node: Optional[BSTNode[K]], key: K) -> tuple:
            if not node:
                return None, None
            
            if key < node.key:
                left, right = _split(node.left, key)
                node.left = right
                if right:
                    right.parent = node
                return left, node
            else:
                left, right = _split(node.right, key)
                node.right = left
                if left:
                    left.parent = node
                return node, right
        
        if self.contains(key):
            return False
        
        new_node = BSTNode(key)
        left, right = _split(self._root, key)
        new_node.left = left
        new_node.right = right
        
        if left:
            left.parent = new_node
        if right:
            right.parent = new_node
        
        self._root = new_node
        self._size += 1
        return True
    
    def insert(self, key: K) -> bool:
        """随机化插入"""
        if random.random() < 1.0 / (self._size + 1):
            return self.insert_at_root(key)
        return super().insert(key)

12.6 本章小结

12.6.1 核心定理总结

定理	内容	应用
定理 12.1	BST中序有序性	排序、范围查询
定理 12.6	删除正确性	实现验证
定理 12.8	随机BST期望高度	概率分析
定理 12.9	期望搜索代价	性能预估
定理 12.11	BST排序复杂度	算法选择

12.6.2 操作复杂度汇总

操作	最好	平均	最坏
查找	$O(1)$	$O(\log n)$	$O(n)$
插入	$O(1)$	$O(\log n)$	$O(n)$
删除	$O(1)$	$O(\log n)$	$O(n)$
最小/最大	$O(1)$	$O(\log n)$	$O(n)$
前驱/后继	$O(1)$	$O(\log n)$	$O(n)$
范围查询	$O(k)$	$O(\log n + k)$	$O(n)$

12.6.3 BST vs 其他数据结构

数据结构	查找	插入	删除	有序遍历	空间
BST	$O(n)$最坏	$O(n)$最坏	$O(n)$最坏	$O(n)$	$O(n)$
平衡树	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$	$O(n)$
哈希表	$O(1)$平均	$O(1)$平均	$O(1)$平均	$O(n \log n)$	$O(n)$
有序数组	$O(\log n)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$

12.7 习题

理论题

证明：BST的中序遍历输出严格递增序列。
证明：随机BST的期望高度为 $O(\log n)$。
分析BST删除操作的三种情况及正确性。
证明：BST排序的最坏情况为 $O(n^2)$。

设计题

设计一个支持 $O(\log n)$ 时间查找第 $k$ 小元素的BST变体。
实现一个支持持久化的BST（修改不破坏原树）。

实现题

实现一个支持范围计数（$[a, b]$ 间有多少元素）的BST。
实现一个支持排名查询（元素 $x$ 的排名）的BST。

12.8 参考文献

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press. Chapter 12: Binary Search Trees.
Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. Section 6.2.2: Binary Tree Searching.
Reed, B. (2003). The height of a random binary search tree. Journal of the ACM, 50(3), 306-332.
Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM, 32(3), 652-686.
Knuth, D. E. (1971). Optimum binary search trees. Acta Informatica, 1(1), 14-25.
Seidel, R., & Aragon, C. R. (1996). Randomized search trees. Algorithmica, 16(4-5), 464-497.

下一章：第13章堆与优先队列理论

第12章 二叉搜索树理论 ​

本章导读 ​

学习目标 ​

12.1 二叉搜索树的形式化定义 ​

12.1.1 BST性质的数学定义 ​

12.1.2 BST ADT规范 ​

12.2 BST操作与正确性证明 ​

12.2.1 查找操作 ​

12.2.2 插入操作 ​

12.2.3 删除操作 ​

12.2.4 BST实现 ​

12.3 BST复杂度分析 ​

12.3.1 最坏情况分析 ​

12.3.2 期望复杂度分析 ​

12.3.3 竞争分析 ​

12.4 BST与排序 ​

12.4.1 BST排序 ​

12.4.2 与比较排序的联系 ​

12.5 BST变体 ​

12.5.1 带频率统计的BST ​

12.5.2 线索二叉搜索树 ​

12.5.3 随机化BST ​

12.6 本章小结 ​

12.6.1 核心定理总结 ​

12.6.2 操作复杂度汇总 ​

12.6.3 BST vs 其他数据结构 ​

12.7 习题 ​

理论题 ​

设计题 ​

实现题 ​

12.8 参考文献 ​

第12章二叉搜索树理论

本章导读

学习目标

12.1 二叉搜索树的形式化定义

12.1.1 BST性质的数学定义

12.1.2 BST ADT规范

12.2 BST操作与正确性证明

12.2.1 查找操作

12.2.2 插入操作

12.2.3 删除操作

12.2.4 BST实现

12.3 BST复杂度分析

12.3.1 最坏情况分析

12.3.2 期望复杂度分析

12.3.3 竞争分析

12.4 BST与排序

12.4.1 BST排序

12.4.2 与比较排序的联系

12.5 BST变体

12.5.1 带频率统计的BST

12.5.2 线索二叉搜索树

12.5.3 随机化BST

12.6 本章小结

12.6.1 核心定理总结

12.6.2 操作复杂度汇总

12.6.3 BST vs 其他数据结构

12.7 习题

理论题

设计题

实现题

12.8 参考文献