第七讲与第八讲 Binary Search Trees

满二叉树：所有结点的孩子数均为0或者2

完美二叉树：非叶子结点均有2个孩子，且所有叶子姐点深度相同

二叉搜索树（Binary Search Trees）

元素查找（参考数据结构）

查找元素的前驱与后继

在 BST 的中序遍历序列中，这两个元素分别紧邻 $x$ 的左右两侧。

查找后继（Successor）：寻找比 $x$ 大的最小节点，分两种情况讨论：

（1）$x$ 有右子树

（2）$x$ 没有右子树

这意味着以 $x$ 为根的子树已经遍历完了。我们需要向上寻找，找到第一个“把 $x$ 所在子树当做左子树”的祖先。 * 操作：沿着父节点 parent 向上找，直到发现某个节点 $y$，使得其左孩子是 $x$（或者 $x$ 的祖先）。此时 $y$ 就是后继。

查找前驱（Predecessor）：前驱的逻辑与后继完全对称：

（1）$x$ 有左子树

（2）$x$ 没有左子树

时间复杂度为 $O(h)$。

元素的插入与删除（参考数据结构）

随机二叉搜索树（Randomized Binary Search Trees）

为确保树高尽可能小，避免搜索树退化成链，考虑随机化算法。

树堆Treap（BST+Heap）

每一个结点包含键值与优先级两个数

证明：若Treap中每一个结点的键值互不相同，优先级互不相同，则这个Treap是唯一的。

Treap不一定是二叉堆

第一种视角：Random-order BST insertions

按最小堆处理，优先级越低，越早插入

第二章视角：Quicksort recursion tree

仿照快速排序，每次选择优先级最小的元素作为界限进行划分，将这一过程表成树，即有限级最小的元素作为根节点，将左右元素划分到它的左右子树中，如此构造得到二叉搜索树。

详细证明：给定序列$A[1,\cdots,n]$和对应的随机优先级$P[1,\cdots,n]$，类比快速排序过程，可知$A[k]$在二叉搜索树中的深度为$A[k]$与界限pivot的比较次数

$A[k]$ 与 $A[i]$ 发生比较的概率： $$\Pr \{A[k] \text{ compares with pivot } A[i]\} = \Pr \{P[i] = \min_{j \in [i, k]} \{P[j]\}\} \le \frac{1}{|k-i|}$$

假设 $A$ 数组已经按键值排好序。考虑 $A[i]$ 和 $A[k]$ 之间的所有元素（包含端点），共有 $|k-i|+1$ 个元素。
在快速排序或 Treap 构造中，$A[i]$ 和 $A[k]$ 会发生比较，当且仅当 $A[i]$ 或 $A[k]$ 是这 $|k-i|+1$ 个元素中优先级 $P$ 最小的（即最先被选为 pivot 的）。
如果该区间中任何一个中间元素 $A[j]$ 先被选为 pivot，那么 $A[i]$ 会被分到左区间，$A[k]$ 会被分到右区间，它们此后永远不会被比较。 $$\text{Expected comparisons} \le \sum_{i \neq k} \frac{1}{|k-i|} \le O(\log n)$$

跳表（Skip List）