algorithm - 二項キューのランクを下げる

Question

ここで二項キュー操作について読んでいます。

リンクの下部に、次のように記載されています

二項キューの実装

1. deletemin 操作には、ルートのすべてのサブツリーを見つける機能が必要です。したがって、各ノードの子が利用可能である必要があります（リンクされたリストなど）
2. deletemin では、サブツリーのサイズによって子を並べ替える必要があります。
3. 房を簡単にマージできるようにする必要があります。2 つの二項ツリーは、同じサイズの場合にのみマージできます。したがって、ツリーのサイズをルートに格納する必要があります。マージ中、ツリーの 1 つが他のツリーの最後の子になるため、各ノードの最後の子を追跡する必要があります。使用するのに適したデータ構造は、各ノードが次の形式の循環二重リンク リストです。

データ | 最初 | 左 | 右 | 順位 | の数 |
--------------------------------------------
       子 |兄弟 |兄弟| 子供

上記で、著者は「ランク番号」を意味しますか? 例を挙げて説明してください。

Answer 1

私が理解している限りでは、彼は次のように言おうとしてrankいno. of childenます。したがって、各ノードに次のものを保存するだけです。

• dataツリー内の要素を表します
• first子のリンクされたリストへのポインタを表します (つまり、最初の子へのポインタ)
• left左隣へのポインタです
• right右隣へのポインタです
• rankは単に二項ツリーのランクです

Answer 2

「2 つの二項ツリーは同じサイズの場合にのみマージできるため、ツリーのサイズをルートに格納する必要がある」という要件に注意してください。

「サブツリーのサイズ」フィールドの代わりに、作成者は「子の数」フィールドを入れたようです。これは紛らわしいですが、サブツリーのサイズが 2^{# of children} であるため、実装上は問題ありません。したがって、サブツリーのサイズを比較する代わりに、子の数を比較できます。