split/merge
の操作を実装して理解しようとしていtreap
ます。すべてのノードには、ヒープ キーとツリー キーの 2 つのキーがあります。ヒープ キーを見ると、有効なヒープがあり、ツリー キーと同じであることがわかります。
最大優先度または最小優先度 (最大ヒープか最小ヒープかによって異なります) を持つダミー ノードを挿入するだけでよいため、Treap の分割は通常よりも簡単です。ただし、このリンクは、分割キーがツリーにないことを前提としているだけです。ただし、常に右ツリーまたは左ツリー内に既存のキーが必要な場合はどうすればよいでしょうか? 私は何をしますか?