左子右兄弟二分木

コンピュータサイエンスで研究されているすべての多分岐またはk分木構造は、二分木として表現することができ、子兄弟表現^{[ 1 ]}、左子、右兄弟二分木^{[ 2 ]}、二重連鎖木または子相続連鎖^{[ 3 ]}など、さまざまな名前で呼ばれています。

多分岐木Tを表す二分木では、各ノードはT内のノードに対応し、2 つのポインタを持ちます。1 つはノードの最初の子へのポインタ、もう 1 つはT内の次の兄弟へのポインタです。したがって、ノードの子は単方向連結リストを形成します。ノードnのk番目の子を見つけるには、このリストをたどる必要があります。

手続きkth-child(n, k): 子ども ← n.子ども k ≠ 0かつchild ≠ nilの間: 子 ← 子の次の兄弟 k ← k − 1 子 を返す// nilを返す場合がある

k 進木から LC-RS 二分木への変換プロセスは、Knuth変換と呼ばれることもあります。^{[ 4 ]}この方法で任意の k 進木から二分木を形成するには、元の木のルートを二分木のルートにします。次に、ルートから始めて、元の木で各ノードの左端の子を二分木の左の子にし、元の木で右に最も近い兄弟を二分木の右の子にします。

二重連鎖木は、1963年にエドワード・H・サッセンガスによって記述された。 ^{[ 5 ]}

k分木をLC-RS二分木に変換する場合、すべてのノードは左の子とリンクされ、整列され、次に近いノードは兄弟ノードとなります。例えば、以下のような三分木があります。

 1 /|\ / | \ / | \ 2 3 4 / \ | 5 6 7 / \ 8 9

左の子ノードを親ノードの1つ下の階層に配置し、子ノードの隣に兄弟ノードを同じ階層に配置することで、これを書き換えることができます。そうすることで、直線（同じ線）になります。 

 1 / / / 2---3---4 / / 5---6 7 / 8-9

各兄弟を時計回りに45°回転させることで、この木を二分木に変換できます。^{[ 6 ]}

 1 / 2 / \ 5 3 \ \ 6 4 / 7 / 8 \ 9

LCRS表現は従来のマルチウェイツリーよりもスペース効率が良いですが、インデックスによるノードの子の検索が遅くなるという欠点があります。したがって、LCRS表現は次のような場合に好ましいです。

1. メモリ効率が懸念事項であり、
2. ノードの子ノードへのランダムアクセスは必須ではありません。

ケース（1）は、大規模な多分岐ツリーが必要な場合、特にツリーに大量のデータが含まれる場合に適用されます。たとえば、系統樹を格納する場合、LCRS表現が適している可能性があります。

ケース（2）は、ツリー構造が非常に特殊な方法で使用されている特殊なデータ構造で発生します。たとえば、多分岐ツリーを使用する多くのタイプのヒープデータ構造は、LCRS表現を使用することでスペースを最適化できます。（例として、フィボナッチヒープ、ペアリングヒープ、弱ヒープなどがあります。）この主な理由は、ヒープデータ構造では、最も一般的な操作が次のようになる傾向があるためです。

1. 木の根を取り除き、その子をそれぞれ処理するか、
2. 2つの木を結合するには、一方の木をもう一方の木の子にします。

操作（１）は非常に効率的です。LCRS表現では、兄弟がないため右の子を持つようにツリーを整理し、ルートを簡単に削除できます。

操作（２）も効率的である。２本の木を簡単に結合できる。^[７]