TREAP数据结构中优先生成

Question

我正在研究TREAP数据结构。插入节点时，TREAP径向生成节点的优先级。但是，如果69个节点的生成优先级是上面的图片中的13次？

父母的优先级必须高于孩子的优先级。TREAP的二进制树属性与堆属性碰撞？

我想知道。谢谢。

Answer 1

假设没有69节点的图片中有Treap，并希望添加（69,13）节点：
1. 拆分现有的treap到2 traeps l和r键69（这里所有旧的treap都将l）

2. 创建 treap m，单节点（69,13）
3. 合并 m with l，然后结果与r
对于这种情况，节点（69,13）成为一个新的根，旧的Treap将是它的左孩子。

Answer 2

如果节点69具有优先级13，那么它将是树的根，节点31将是其左子。节点31的后代将如下图所示，除了节点69的课程。

始终可以安排一个TREAP，使其尊重堆和二进制搜索属性。事实上，在没有相同的值或相同的优先级，只有一个可能的安排。

优先事项的随机分配使得Treap可能会合理平衡。它可能不会完全平衡，但在积极的侧面建设中，TREAP快速且不复杂。