树：一个每条边都是桥的连通图。
二叉树：一棵有根树。每个节点的分支数量 \(\leq 2\) 个，分支称为“左子树”和“右子树”，顺序不能随意颠倒。
特别的，wikipedia 提到“很多人喜欢使用“有根二叉树”而非二叉树，以强调二叉树是有根的，但归根结底二叉树是有根的”。
二叉搜索树：一棵二叉树。每个内部节点的键大于该节点左子树中的所有键，而小于该节点右子树中的所有键。
二叉搜索树最常见的名字，Binary Search Tree，大家通常喜欢写作 BST 。有些地方也会叫做“有序二叉树”或者“排序二叉树”，指的都是同一种树。
显然，基于 BST 的定义，BST 的子树也是 BST 。
定理 1 ：BST 中左链上的最左节点为最小节点。
证明：
设左链上的节点为 \(root=N_0, N_1, \cdots, N_k\) ，对于 \(0 \leq i < k\), \(N_{i + 1}\) 是 \(N_{i}\) 的左儿子，\(N_{k}\) 是左链上的最左节点。
首先有 \(N_k < N_{k - 1} < \cdots < N_{0} = root\) 。\(\forall\) 非左链节点 \(z\) ，\(\exists j, 0 \leq j \leq k\) 满足 \(z\) 是 \(N_{j}\) 的右子树节点。
则 \(N_{k} \leq N_{j} < z\) ，即 BST 中左链上的最左节点是 BST 中的最小节点。
\(\square\)
实现：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{findMinNode}(root) \\
2: \ &\quad \textbf{while} \ root.\text{left} \neq \text{NIL} \ \textbf{do} \\
3: \ &\quad\quad root \leftarrow cur.\text{left} \\
4: \ &\quad \textbf{return} \ root
\end{aligned}
\]
定理 2 ：BST 中右链上的最右节点为最大节点。
证明：
设右链上的节点为 \(root=M_0, M_1, \cdots, M_l\) ，对于 \(0 \leq i < l\), \(M_{i + 1}\) 是 \(M_{i}\) 的右儿子，\(M_{l}\) 是右链上的最右节点。
首先有 \(M_l > N_{l - 1} > \cdots > M_{0} = root\) 。\(\forall\) 非右链节点 \(z\) ，\(\exists j, 0 \leq j \leq l\) 满足 \(z\) 是 \(M_{j}\) 的左子树节点。
则 \(M_{k} \geq M_{j} > z\) ，即 BST 中右链上的最右节点是 BST 中的最大节点。
\(\square\)
实现：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{findMaxNode}(root) \\
2: \ &\quad \textbf{while} \ root.\text{right} \neq \text{NIL} \ \textbf{do} \\
3: \ &\quad\quad root \leftarrow root.\text{right} \\
4: \ &\quad \textbf{return} \ root
\end{aligned}
\]
定理 3 ：BST 的节点 \(x\) 的前驱（升序序列中该节点的前一个节点）。
- 若 \(x\) 存在左子树，前驱是左子树上右链的最右节点；
- 否则前驱是 \(x\) 最近的将其置于右子树中的祖先 \(y\) 。
证明：
考虑当前的根 \(root\) ，他的子树在升序序列中的区间一定为 \([1, n]\) ，令 \(L = 1, R = n\) 。
考虑节点 \(x\) 的排名为 \(k\) ，他在升序序列中的子树区间为 \([l, r]\) 满足 \(L \leq l \leq k \leq R\) 。
考虑从根到 \(x\) 的路径，每次向左走，当前节点和右子树都比左子树大，则存在一个 \(p\) 满足 \(r < p \leq R\) ，使得新子树的区间为 \([L, p - 1]\) ，更新 \(R \gets p - 1\) ；每次向右走，当前节点和左子树都比其右子树小，则存在一个 \(q\) 满足 \(L \leq q < l\) ，使得新子树的区间为 \([q + 1, R]\) ，更新 \(L \gets q + 1\) 。
显然非 \(x\) 的子树节点中，最大的比 \(x\) 小的节点在最后一次向右走时出现，且是离 \(x\) 最近的将其置于右子树的祖先 \(y\) 。
考虑如何找到 \(y\) ，自顶向下的方法是从 \(root\) 往 \(x\) 走，更新右拐的节点，则最后一次更新的节点为 \(y\) 。
考虑自底向上的方法，从 \(x\) 往根节点走的路径中，若当前节点是其父亲的左儿子则 \(x\) 在其父亲的左子树中，若当前节点是其父亲的右儿子则 \(x\) 在其父节点的右子树中，于是只需向上跳到第一个节点满足其是父节点的右儿子，则其父亲为离 \(x\) 最近的将 \(x\) 置于右子树的祖先。
若 \(x\) 存在左子树，由于 \(x\) 在 \(y\) 的左子树中，\(x\) 的左子树也一定比 \(y\) 小，则 \(x\) 的前驱是 \(x\) 左子树中的最大节点，即左子树上右链的最右节点。若 \(x\) 不存在左子树，则只有非 \(x\) 子树的节点可能比 \(x\) 小，则 \(x\) 的前驱是离它最近的将它置于右子树的节点 \(y\) ，即非 \(x\) 子树中最大的比 \(x\) 小的节点。
\(\square\)
如果记录 \(parent\) 节点，可以从 \(x\) 往上跳。实现形式 1：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{predecessor}(x) \\
2: \ &\quad \textbf{if} \ x.\text{left} \neq \text{NIL} \ \textbf{then} \\
3: \ &\quad\quad \textbf{return} \ \text{findMaxNode}(x.\text{left}) \\
4: \ &\quad \textbf{else} \\
5: \ &\quad\quad \textbf{while} \ x.\text{parent} \neq \text{NIL} \ \textbf{and} \ x = x.\text{parent}.\text{left} \ \textbf{do} \\
6: \ &\quad\quad\quad x \gets x.\text{parent} \\
7: \ &\quad\quad \textbf{return} \ x.\text{parent}
\end{aligned}
\]
如果不记录 \(parent\) 节点，则从根往 \(x\) 跳。时间复杂度同第一种实现。实现形式 2：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{predecessor}(root, x, pred) \\
2: \ &\quad \textbf{if} \ root = \text{NIL} \ \textbf{then} \\
3: \ &\quad\quad \textbf{return} \ \text{NIL} \\
4: \ &\quad \textbf{if} \ x.\text{key} = root.\text{key} \ \textbf{then} \\
5: \ &\quad\quad \textbf{if} \ x.\text{left} \neq \text{NIL} \ \textbf{then} \\
6: \ &\quad\quad\quad \textbf{return} \ \text{findMaxNode}(root.\text{left}) \\
7: \ &\quad\quad \textbf{else} \ \textbf{return} \ pred \\
8: \ &\quad \textbf{elseif} \ x.\text{key} < root.\text{key} \ \textbf{then} \\
9: \ &\quad\quad \textbf{return} \ \text{predecessor}(root.\textbf{left}, x, pred) \\
10: \ &\quad \textbf{else} \ \textbf{return} \ \text{predecessor}(root.\textbf{right}, x, root) \\
\end{aligned}
\]
定理 4 ：BST 的节点 \(x\) 的后继（升序序列中该节点的后一个节点）。
- 若 \(x\) 存在右子树，后继是右子树上左链的最左节点；
- 否则后继是 \(x\) 到根的右链段中最近的祖先 \(y\) 。
证明：
考虑当前的根 \(root\) ，他的子树在升序序列中的区间一定为 \([1, n]\) ，令 \(L = 1, R = n\) 。
考虑节点 \(x\) 的排名为 \(k\) ，他在升序序列中的子树区间为 \([l, r]\) 满足 \(L \leq l \leq k \leq R\) 。
考虑从根到 \(x\) 的路径，每次向左走，当前节点和右子树都比左子树大，则存在一个 \(p\) 满足 \(r < p \leq R\) ，使得新子树的区间为 \([L, p - 1]\) ，更新 \(R \gets p - 1\) ；每次向右走，当前节点和左子树都比其右子树小，则存在一个 \(q\) 满足 \(L \leq q < l\) ，使得新子树的区间为 \([q + 1, R]\) ，更新 \(L \gets q + 1\) 。
显然非 \(x\) 的子树节点中，最小的比 \(x\) 大的节点在最后一次向左走时出现，且是离 \(x\) 最近的将其置于左子树的祖先 \(y\) 。
考虑如何找到 \(y\) ，自顶向下的方法是从 \(root\) 往 \(x\) 走，更新左拐的节点，则最后一次更新的节点为 \(y\) 。
考虑自底向上的方法，从 \(x\) 往根节点走的路径中，若当前节点是其父亲的右儿子则 \(x\) 在其父亲的右子树中，若当前节点是其父亲的左儿子则 \(x\) 在其父节点的左子树中，于是只需向上跳到第一个节点满足其是父节点的左儿子，则其父亲为离 \(x\) 最近的将 \(x\) 置于左子树的祖先。
若 \(x\) 存在右子树，由于 \(x\) 在 \(y\) 的右子树中，\(x\) 的右子树也一定比 \(y\) 大，则 \(x\) 的后继是 \(x\) 右子树中的最小节点，即右子树上左链的最左节点。若 \(x\) 不存在右子树，则只有非 \(x\) 子树的节点可能比 \(x\) 大，则 \(x\) 的后继是离它最近的将它置于左子树的节点 \(y\) ，即非 \(x\) 子树中最小的比 \(x\) 大的节点。
实现：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{successor}(root, x, pred) \\
2: \ &\quad \textbf{if} \ root = \text{NIL} \ \textbf{then} \\
3: \ &\quad\quad \textbf{return} \ \text{NIL} \\
4: \ &\quad \textbf{if} \ x.\text{key} = root.\text{key} \ \textbf{then} \\
5: \ &\quad\quad \textbf{if} \ x.\text{left} \neq \text{NIL} \ \textbf{then} \\
6: \ &\quad\quad\quad \textbf{return} \ \text{findMaxNode}(root.\text{left}) \\
7: \ &\quad\quad \textbf{else} \ \textbf{return} \ pred \\
8: \ &\quad \textbf{elseif} \ x.\text{key} < root.\text{key} \ \textbf{then} \\
9: \ &\quad\quad \textbf{return} \ \text{successor}(root.\textbf{left}, x, pred) \\
10: \ &\quad \textbf{else} \ \textbf{return} \ \text{successor}(root.\textbf{right}, x, root) \\
\end{aligned}
\]
定理 5 ：BST 的中序遍历是二叉树的升序序列。
证明：
对于节点个数为 \(1\) 的 BST ，显然成立。
否则由归纳假设，\(root\) 的左子树的中序遍历是升序序列 \(L_1\) ，\(root\) 的右子树的升序遍历是升序序列 \(L2\) 。由 \(L_1 < root.\text{key} < L_2\) ，则该 BST 的中序遍历 \([L_1, root.\text{key}, L_2]\) 是升序遍历。
\(\square\)
实现：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{inorderTraversal}(root) \\
2: \ &\quad \textbf{if} \ root = \text{NIL} \ \textbf{then} \\
3: \ &\quad \quad \textbf{return} \\
4: \ &\quad \text{inorderTraversal}(root.\text{left}) \\
5: \ &\quad \text{print} \ root.\text{key} \\
6: \ &\quad \text{inorderTraversal}(root.\text{right}) \\
\end{aligned}
\]
定理 6 ：BST 中查询 \(target\) 。
- 若 \(target = root.\text{key}\) 则目标节点是当前节点；
- 若 \(target < root.\text{left}.\textbf{key}\) 则目标节点在左子树中；
- 若 \(target > root.\text{right}.\text{key}\) 则目标节点在右子树中；
- 若访问到了空节点，则目标节点不存在。
实现：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{search}(root, target) \\
2: \ &\quad \textbf{if} \ root = \text{NIL} \ \textbf{then} \\
3: \ &\quad\quad \textbf{return} \ \text{FALSE} \\
4: \ &\quad \textbf{if} \ target = root.\text{key} \ \textbf{then} \\
5: \ &\quad\quad \textbf{return} \ \text{TRUE} \\
6: \ &\quad \textbf{elseif} \ traget < root.\text{kty} \ \textbf{then} \\
7: \ &\quad\quad \textbf{return} \ \text{search}(root.\text{left}, target) \\
8: \ &\quad \textbf{else} \ \textbf{return} \ \text{search}(root.\text{right}, target) \\
\end{aligned}
\]
定理 7 ：BST 中插入 \(target\) 。
实现：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{insert}(root, target) \\
2: \ &\quad \textbf{if} \ root = \text{NIL} \ \textbf{then} \\
3: \ &\quad\quad \textbf{return} \ \text{newNode}(target) \\
4: \ &\quad root.\text{size} \gets root.\text{size} + 1 \\
5: \ &\quad \textbf{if} \ target = root.\text{key} \ \textbf{then} \\
6: \ &\quad\quad root.\textbf{cnt} \gets root.\textbf{cnt} + 1 \\
7: \ &\quad \textbf{elseif} \ target < root.\text{key} \ \textbf{then} \\
8: \ &\quad\quad root.\text{left} \gets \text{insert}(root.\text{left}, target) \\
9: \ &\quad \textbf{else} \\
10: \ &\quad\quad root.\text{left} \gets \text{insert}(root.\text{right}, target) \\
11: \ &\quad \textbf{return} \ root \\
\end{aligned}
\]
定理 8 ：BST 中删除 \(target\) 。
删除 \(target\) 之前需要先查询一遍其是否在 BST 中，否则删除失败需要回溯更新操作。
实现：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{remove}(root, target) \\
2: \ &\quad \textbf{if} \ root = \text{NIL} \ \textbf{then} \\
3: \ &\quad\quad \textbf{return} \ root \\
4: \ &\quad root.\text{szie} \gets root.\text{szie} - 1 \\
5: \ &\quad \textbf{if} \ target = root.\text{key} \ \textbf{then} \\
6: \ &\quad\quad \textbf{if} \ root.\text{cnt} > 1 \ \textbf{then} \\
7: \ &\quad\quad\quad root.\text{cnt} \gets root.\text{cnt} - 1 \\
8: \ &\quad\quad \textbf{elseif} \ root.\text{left} \neq \text{NIL} \ \textbf{then} \\
9: \ &\quad\quad\quad predecessor = \text{findMaxNode}(root.\text{left}) \\
10: \ &\quad\quad\quad \text{swap}(root, predecessor) \\
11: \ &\quad\quad\quad root.\text{left} = \text{remove}(root.\text{left}, predecessor.\text{key}) \\
12: \ &\quad\quad \textbf{else} \\
13: \ &\quad\quad\quad successor = \text{findMinNode}(root.\text{right}) \\
14: \ &\quad\quad\quad \text{swap}(root, successor) \\
15: \ &\quad\quad\quad root.\text{right} = \text{remove}(root.\text{right}, predecessor.\text{key}) \\
16: \ &\quad \textbf{elseif} \ target < root.\text{key} \ \textbf{then} \\
17: \ &\quad\quad root.\text{left} \gets \text{remove}(root.\text{left}, target) \\
18: \ &\quad \textbf{else} \\
19: \ &\quad\quad root.\text{right} \gets \text{remove}(root.\text{right}, target) \\
20: \ &\quad \textbf{return} \ root \\
\end{aligned}
\]
定理 9 ：BST 中查询 \(target\) 的排名（排名从 1 开始）。
查询 \(target\) 的排名之前需要先查询一遍其是否在 BST 中，否则会返回错误排名。
实现：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{SZ}(root) \\
2: \ &\quad \textbf{if} \ root = \text{NIL} \ \textbf{then} \\
3: \ &\quad\quad \textbf{return} \ 0 \\
4: \ &\quad \textbf{else} \ \textbf{return} \ root.\text{size} \\
\\
1: \ &\text{queryRank}(root, target) \\
2: \ &\quad \textbf{if} \ root = \text{NIL} \ \textbf{then} \\
3: \ &\quad\quad \textbf{return} \ 0 \\
4: \ &\quad \textbf{if} \ target = root.\text{key} \ \textbf{then} \\
5: \ &\quad\quad \textbf{return} \ \text{SZ}(root.\text{left}) + 1 \\
6: \ &\quad \textbf{elseif} \ traget < root.\text{key} \ \textbf{then} \\
7: \ &\quad\quad \textbf{return} \ \text{queryRank}(root.\text{left}, target) \\
8: \ &\quad \textbf{else}\ \textbf{return} \ \text{SZ}(root.\text{left}) + \text{queryRank}(root.\text{right}, target) \\
\end{aligned}
\]
定理 10 ：BST 查询排名为 \(k\) 的节点。
实现：
\[\hspace{-32em}\begin{aligned}
1: \ &\text{queryKth}(root, k) \\
2: \ &\quad \textbf{if} \ root = \text{NIL} \ \textbf{then} \\
3: \ &\quad\quad \textbf{return} \ NIL \\
4: \ &\quad v \gets \text{SZ}(root.\text{left}) \\
5: \ &\quad \textbf{if} \ k \leq v \ \textbf{then} \\
6: \ &\quad\quad \textbf{return} \ \text{queryKth}(root.\text{ left} \\
7: \ &\quad \textbf{elseif} \ k \leq v + root.\text{cnt} \ \textbf{then} \\
8: \ &\quad\quad \textbf{return} \ root \\
9: \ &\quad \textbf{else} \ \textbf{return} \ \text{queryKth}(root.\text{right}, k - v - root.\text{cnt}) \\
\end{aligned}
\]