Treap：一种基于随机化的二叉搜索树

与红黑树和AVL树一样，Treap 也是一种平衡二叉搜索树，不过它的高度并不保证总是 O(Log n)。它的核心思想在于利用“随机化”和“二叉堆”的特性，以极高的概率来维持树的平衡。在搜索、插入和删除操作中，其期望的时间复杂度均为 O(Log n)。

<img src="https://media.geeksforgeeks.org/wp-content/cdn-uploads/treap.png" alt="treap" />

Treap 的每一个节点都维护两个值：

• Key（键值）：遵循标准的二叉搜索树（BST）排序规则（左子节点小于父节点，右子节点大于父节点）。
• Priority（优先级）：这是一个随机分配的值，遵循最大堆的属性。

Treap 的基本操作：

与其他自平衡二叉搜索树类似，Treap 在插入和删除过程中也使用旋转操作来维持最大堆的属性。

T1, T2 and T3 are subtrees of the tree rooted with y (on left side) 
or x (on right side)           
                y                               x
               / \     Right Rotation          /  \
              x   T3   – – – – – – – >        T1   y 
             / \       < - - - - - - -            / \
            T1  T2     Left Rotation            T2  T3
Keys in both of the above trees follow the following order 
      keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.

search(x)

执行标准的二叉搜索树搜索来查找 x。

Insert(x):

• 创建一个新节点，其键值等于 x，优先级值等于一个随机值。
• 执行标准的二叉搜索树插入操作。
• 使用旋转操作，确保新插入节点的优先级符合最大堆的属性。

<img src="https://media.geeksforgeeks.org/wp-content/cdn-uploads/treapInsert1.png" alt="treapInsert" />
Delete(x):

• 如果待删除的节点是叶子节点，直接将其删除。
• 否则，将该节点的优先级替换为负无穷（ -INF ），然后进行适当的旋转，将该节点向下移动直到变为叶子节点。

<img src="https://media.geeksforgeeks.org/wp-content/cdn-uploads/treapDelete.png" alt="treapDelete" />

关于 Treap 搜索、插入和删除的更多实现细节，请参阅Treap 搜索、插入和删除的实现。

参考资料：

https://en.wikipedia.org/wiki/Treap
https://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture19/sld017.htm