トレンドデータ構造の優先順位生成

Question

トレンドデータ構造を検討しています。ノードを挿入するとき、トレンプはノードの優先順位を生成します。しかし、69ノードの生成された優先順位が上記の写真では13の場合はどうでしょうか。

親の優先順位は、子の優先順位よりも高くなければなりません。Treepのバイナリツリー属性はヒープ属性と衝突しますか？

知りたい。ありがとう。

Answer 1

69ノードなしであなたの写真からトレイプがあると仮定し、追加（69,13）ノードを追加したい：
1. Split 既存のトレイプを2トイプLとRキー69（ここですべての古いトレイプはLになります） 2. シングルノード付き Treep M（69,13）
3. m mをlで、rの結果を得た。 この場合、ノード（69,13）が新しいルートになり、古いトレイプはそれが残りの子になります。

Answer 2

ノード69が優先13を有していた場合、それはツリーのルートとなり、ノード31はその左の子であろう。ノード31の子孫は、ノード69の場合は、図のようになるでしょう。

ヒープとバイナリ検索プロパティの両方を尊重するようにトレッペを整理することは常に可能です。実際、等しい値または等しい優先順位がない場合、1つの可能な配置は1つだけです。

優先順位のランダムな割り当てにより、トレイプが合理的にバランスが取れている可能性があります。それは完全にバランスが取れていないかもしれませんが、肯定的な側面にトレイは速くて複雑ではありません。