木構造の左子・右兄弟表現（Left-Child Right-Sibling）とは？仕組みとメリット・デメリットを解説

左子・右兄弟表現とは

左子・右兄弟表現は、n分木（n-ary tree）を表現するためのもうひとつのデータ構造です。従来の方法では、ノードはすべての子ノードへのポインタを個別に保持していましたが、この表現では各ノードが持つポインタはわずか2つだけです。

• 最初の子へのポインタ（左子：Left Child）
• 直後の兄弟へのポインタ（右兄弟：Right Sibling）

この変換により、ノードが持つ子の数をあらかじめ知っておく必要がなくなるだけでなく、ポインタの数も最大2つに抑えられるため、実装が格段にシンプルになります。

表現のルール

• 同じ親を持つ子ノード同士を、左から右へ順に連結する。
• 親ノードは、最初の子ノードにのみリンクする。

具体例

以下は、左子・右兄弟表現による木構造の一例です。

10
|
2 -> 3 -> 4 -> 5
|              |
6              7 -> 8 -> 9

この図では、ノード10が最初の子として2を持ち、2・3・4・5が兄弟として左から右へ連結されています。さらに、ノード2の子は6、ノード5の子は7・8・9という階層構造になっています。実際の親子関係は「10 → {2, 3, 4, 5}」「2 → {6}」「5 → {7, 8, 9}」となります。

メリット

• ノードごとのポインタ数が最大2つに制限されるため、メモリを節約できる。
• 子の数が事前に不明でも対応でき、柔軟な木構造を表現できる。
• 実装がシンプルになり、コーディングが容易になる。

デメリット

• 検索・挿入・削除といった基本操作に時間がかかる場合がある。目的の位置を特定するには、対象ノードのすべての兄弟を順番にたどる必要があるためである（最悪の場合、兄弟全体を走査することになる）。

まとめ

左子・右兄弟表現は、ポインタを2つに絞ることでメモリ効率と実装のしやすさを実現した、n分木の代表的な表現方法です。一方で、要素へのアクセスには兄弟の走査が必要となるため、操作速度を重視する場面では注意が必要です。用途に応じて通常の配列ベース表現や他の木構造との使い分けを検討するとよいでしょう。