Leonardoヒープのルートの左と右の子を見つけるには？

Question

this articleによると、 木のルートは位置L（k） - 1にあります。 Ltk-1サブツリーの根は位置L（k-1） - 1にあります。 Ltk- 2サブツリーが位置L（k）-2にあります。

誰かが私にこれを理解するのを手伝ってもいいですか？私はsmoothsortを実装しようとしています。

Answer 1

オーダーkのLeonardoヒープが配列に格納されているとしたら、レイアウトを再帰的に実行して、大きなサブツリー、次に小さいサブツリー、ルートノードをレイアウトするとします。つまり、0,1,2,3 ...、L（k） - 1という番号が付いた位置に、L（k）個のノードがあります。これは次のようになります。

+---------------------------+----------------------+------+ 
| Tree of order k - 1 | Tree of order k - 2 | root | 
+---------------------------+----------------------+------+ 

ルートが最後に来ることに注意してください。ゼロインデックス付けを使用しているため、ルートはL（k） - 1の位置にあることに注意してください。

2つのサブツリーはどこにありますか？まあ、次数k - 2の部分木はルートノードの直前です。そのルートが最右端にあるようにレイアウトされています。その根を見つけるために、木全体（L（k）-1）の根に行き、1つのステップをバックアップしてL（k）-2になるようにします。

注文のサブツリーはどうですかk-1？まあ、それが私たちの表現の前に楽にあることに注意してください。そのルートノードは、位置L（k-1）にあるそのブロックの終わりにあるだろう（次数kの大きな木が位置L（k）-1に根を持つのと同様に）

あなたは私の記事を楽しんでいたと思います！ :-)