随机二叉搜索树与替罪羊树的深入解析

### 随机二叉搜索树与替罪羊树的深入解析 #### 1. 随机二叉搜索树 随机二叉搜索树是一种重要的数据结构，其中Treap和SkiplistSSet是两种常见的实现，它们都能在 $O(logn)$ 的期望时间内完成SSet操作。 ##### 1.1 Treap与SkiplistSSet的比较 | 数据结构 | 搜索路径期望长度 | 特点 | | --- | --- | --- | | SkiplistSSet | $2logn + O(1)$ | 实现SSet操作期望时间为 $O(logn)$，add(x)和remove(x)涉及搜索和常数次指针更改 | | Treap | $2lnn + O(1) ≈ 1.386logn + O(1)$ | 搜索路径明显更短，操作速度比Skiplist更快 | 即使SkiplistSSet通过有偏硬币抛掷优化，其搜索路径期望长度为 $elnn + O(1) ≈ 1.884logn + O(1)$，仍比Treap长。 ##### 1.2 Treap的优化与变体 - **空间优化**：可以通过对节点地址进行哈希计算来消除对优先级p的显式存储。哈希函数应具有随机性和最小独立属性，例如制表哈希。 - **Martínez和Roura的随机二叉搜索树**： - 每个节点存储以该节点为根的子树的大小。 - **添加操作**： - 以 $1/(size(u)+1)$ 的概率，将值x作为叶子节点添加，并通过旋转将其提升到子树的根。 - 以 $1 - 1/(size(u) + 1)$ 的概率，将值x递归添加到u的左子树或右子树中。 - **删除操作**：找到包含x的节点u，通过随机旋转增加u的深度，直到u成为叶子节点，然后将其从树中移除。 ##### 1.3 相关练习 - **练习7.1**：在图7.5的Treap中依次添加4.5（优先级7）和7.5（优先级20）。 - **练习7.2**：在图7.5的Treap中依次移除5和7。 - **练习7.3**：证明存在21,964,800个序列可以生成图7.1右侧的树。 - **练习7.4**：设计并实现permute(a)方法，对包含n个不同值的数组a进行随机排列，时间复杂度为 $O(n)$，并证明a的 $n!$ 种可能排列的概率相等。 - **练习7.5**：使用引理7.2的两部分证明add(x)操作（以及remove(x)操作）执行的旋转次数的期望为 $O(1)$。 - **练习7.6**：修改Treap实现，不显式存储优先级，而是通过对每个节点的hashCode()进行哈希来模拟。 - **练习7.7**： 1. 展示在节点u进行左旋转或右旋转时，如何在常数时间内更新以u为根的子树的高度和大小。 2. 解释为什么如果尝试存储每个节点的深度，就无法实现相同的结果。 - **练习7.8**：设计并实现一个算法，从包含n个元素的有序数组a构建Treap，最坏情况下的时间复杂度为 $O(n)$，构建的Treap应与使用add(x)方法逐个添加元素得到的Treap相同。 - **练习7.9**： 1. 设计并实现一个Treap，每个节点跟踪其子树中的最小值和最大值。 2. 添加fingerFind(x,u)方法，借助指向节点u的指针执行find(x)操作。该操作从u开始向上遍历，直到找到满足 $w.min ≤ x ≤ w.max$ 的节点w，然后从w开始进行标准搜索。 3. 将实现扩展为从最近找到的节点开始所有find(x)操作的Treap版本。 - **练习7.10**：设计并实现一个包含get(i)操作的Treap版本，该操作返回Treap中排名为i的键。 - **练习7.11**：实现一个TreapList，将List接口实现为Treap。每个节点存储一个列表项，中序遍历Treap的结果与列表中的项顺序相同。所有List操作get(i)、set(i,x)、add(i,x)和remove(i)的期望时间复杂度为 $O(logn)$。 - **练习7.12**：设计并实现一个支持split(x)操作的Treap版本。该操作移除Treap中所有大于x的值，并返回一个包含这些值的新Treap。 - **练习7.13**：设计并实现一个支持absorb(t2)操作的Treap版本。该操作将t2中的所有值移除并添加到当前Treap中，前提是t2中的最小值大于当前Treap中的最大值。 - **练习7.14**：实现Martínez的随机二叉搜索树，并与Treap实现的性能进行比较。 #### 2. 替罪羊树 替罪羊树是一种通过部分重建操作保持平衡的二叉搜索树。 ##### 2.1 部分重建操作 当需要对以节点u为根的子树进行重建时，可以通过以下步骤实现： 1. 遍历u的子树，将所有节点收集到数组a中。 2. 递归地使用数组a构建平衡子树。 以下是相关代码实现： ```java void rebuild(Node<T> u) { int ns = size(u); ```