我正在研究 treap 数据结构。插入节点时，treap随机生成节点的优先级。但是如果69个节点生成的优先级是上图中的13呢？
parent 的优先级必须高于 child 的优先级。 treap的二叉树属性是否与堆属性冲突？
我想知道。谢谢。
最佳答案
假设您从没有 69 节点的图片中提取并想要添加 (69, 13) 节点:
1. 拆分现有的treap通过键69分为2个treap L和R(这里所有旧的treap都是L)
2. 创建单节点(69, 13)的treap M
3. 合并 M与L，然后与R产生
对于这种情况，节点 (69, 13) 成为新的根节点，而旧的 treap 将成为它的左子节点。
关于algorithm - treap数据结构中的优先级生成，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25028730/