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

题目/知识点描述
随机化二叉搜索树是一种通过在标准二叉搜索树（BST）中引入随机性来维持平衡性的数据结构。与传统的自平衡BST（如AVL树、红黑树）通过旋转操作严格维护平衡条件不同，随机化BST利用随机性保证树高在期望情况下为O(log n)，从而实现平均O(log n)的查找、插入和删除操作。本专题将重点讲解随机化BST的核心思想——Treap（Tree + Heap），它通过为每个节点随机分配优先级，同时满足BST性质和堆性质来实现平衡。

解题过程循序渐进讲解

第一步：理解Treap的基本结构
Treap的每个节点包含：

1. 键（key）：遵循BST性质——左子树所有节点的键 ≤ 当前节点的键 ≤ 右子树所有节点的键。
2. 优先级（priority）：一个随机生成的数值，遵循堆性质（通常是大顶堆）——父节点的优先级 ≥ 子节点的优先级。
3. 左右子节点指针。

示例：
插入键序列[5, 2, 8]，随机分配的优先级假设为[10, 5, 15]。最终Treap结构为：

• 根节点：键=5，优先级=10（最高）
• 左子节点：键=2，优先级=5
• 右子节点：键=8，优先级=15（但优先级15>10，违反堆性质，需调整）

第二步：插入操作与旋转调整
插入新节点时，先按BST规则找到插入位置，赋予随机优先级，然后通过旋转操作向上调整，使堆性质成立。

旋转操作（以右旋为例）：

• 场景：当当前节点的左子节点优先级更高时（大顶堆）。
• 操作：
  1. 让左子节点成为新的父节点。
  2. 将原左子节点的右子树作为原父节点的左子树。
  3. 原父节点成为新父节点的右子节点。

插入示例：继续上例，插入键=8（优先级=15）到键=5的右子树后，发现优先级15>10，违反堆性质。但此时8是5的右子节点，需要通过左旋提升8：

• 左旋操作：让节点8成为父节点，节点5成为8的左子节点，原8的左子树（空）成为5的右子树。
  调整后树结构：

    8(优先级15)
   /
  5(优先级10)
 /
2(优先级5)

此时同时满足：

• BST性质：2 ≤ 5 ≤ 8。
• 堆性质：优先级15 ≥ 10 ≥ 5。

第三步：删除操作
删除节点时，分两种情况：

1. 叶节点：直接删除。
2. 非叶节点：通过旋转将其降为叶节点再删除。具体步骤：
   • 比较待删除节点的左右子节点优先级。
   • 若左子节点优先级高，则右旋，使左子节点上位，待删除节点下移。
   • 若右子节点优先级高，则左旋，使右子节点上位，待删除节点下移。
   • 重复旋转直到待删除节点成为叶节点，然后删除。

删除示例：删除上例中的键=5（优先级10）：

• 比较其左右子节点优先级：左子2（优先级5），右子无。
• 左子优先级高，右旋：节点2成为父节点，节点5成为2的右子节点。
• 此时5变为叶节点，直接删除。最终树仅剩节点2。

第四步：随机性保证平衡性的原理
Treap的平衡性依赖优先级完全随机生成，这保证了：

1. 期望树高：优先级随机相当于节点以随机顺序插入标准BST，理论证明期望树高为O(log n)。
2. 避免最坏情况：传统BST在有序插入时退化成链表（O(n)树高），而随机优先级使插入顺序随机化，避免退化。

数学直观：优先级随机等价于所有节点排列顺序随机，随机BST的平均深度为2 ln n ≈ 1.39 log₂ n。

第五步：性能分析

• 时间复杂度：
  • 查找：O(树高)，期望O(log n)。
  • 插入/删除：每次旋转O(1)，最多进行O(树高)次旋转，期望O(log n)。
• 空间复杂度：O(n)。
• 优势：实现简单，无需记录平衡因子或颜色标志，常数因子小。
• 劣势：极端情况下（小概率）仍可能退化成近似链状，但实践中极少发生。

关键点总结

1. Treap = BST + 堆，通过随机优先级和旋转维持平衡。
2. 插入时先BST定位，再旋转满足堆性质。
3. 删除时通过旋转降为叶节点后删除。
4. 随机性保证了期望O(log n)的性能，且实现比AVL树/红黑树更简洁。