algorithm - trep数据结构中的优先级生成

Question

我正在研究trap数据结构。在插入节点时，trap 随机生成节点的优先级。但是如果上图中69个节点生成的优先级是13呢？

父母的优先级必须高于孩子的优先级。treap 的二叉树属性是否与堆属性冲突？

我想知道。谢谢。

Answer 1

假设您从没有 69 节点的图片中获得了 treap 并且想要添加 (69, 13) 节点：
1.将现有的 treap拆分为 2 个 treap L 和 R 按键 69（这里所有旧的 treap 都是 L）
2.创建treap M 与单个节点 (69, 13)
3.将 M 与 L合并
，然后将结果与 R 在这种情况下，节点 (69, 13) 成为一个新的根，而旧的 treap 将是它的左孩子。

Answer 2

如果节点 69 的优先级为 13，那么它将是树的根节点，节点 31 将是它的左孩子。节点 31 的后代将与您的图表中一样，当然除了节点 69。

总是可以安排一个陷阱，以便它同时尊重堆和二进制搜索属性。事实上，在没有相等的值或相等的优先级的情况下，只有一种可能的安排。

优先级的随机分配使得treap 很可能得到合理的平衡。它可能不是完全平衡的，但从积极的方面来说，构建treap 是快速且简单的。