algorithm - 在树内存在的键处拆分一个trap

Question

我一直在尝试实施和split/merge理解treap. 每个节点都有两个键：一个堆键和一个树键。查看堆键，您应该会看到一个有效的堆，并且与树键相同。

拆分treap 比平常更容易，因为您可以插入一个具有最大或最小优先级的虚拟节点（取决于它是最大堆还是最小堆）。但是，此链接只是假设拆分键不在树中。但是，如果我总是想要右树或左树中的现有密钥怎么办？我该怎么办？

Answer 1

1. 找到有问题的键的节点。
2. 将其向上移动以成为新的根（通过给予它非常高或非常低的优先级）。
3. 拆分左（或右）子树。