データ構造における二分木の表現方法｜配列と連結リストの違いを解説

コンピュータメモリ上での二分木の表現方法

ここでは、二分木をコンピュータのメモリ上でどのように表現するかについて解説します。表現方法には主に2種類あり、配列を使う方法と連結リスト（リンクリスト）を使う方法があります。

配列による表現

まず、次のような二分木を例に考えてみましょう。

配列による表現では、木の要素をレベル順（幅優先順）に走査しながら格納していきます。つまり、ノードを上のレベルから順番に保存する方式です。存在しない要素がある場合は、その位置を空白のまま残します。上記の木を配列で表現すると、次のようになります。

インデックス1には根（ルート）である「10」が格納されており、その2つの子「5」と「16」はそれぞれインデックス2と3に配置されます。子が存在しないノードについては、対応する位置が空白のままになっています。

親と子のインデックスを求める計算式

この表現方法では、次の式を使うことで、あるノードの子の位置を簡単に求められます。

$$child_{1}=2*parent$$ 

$$child_{2}=\lgroup2*parent\rgroup+1$$

逆に、子のインデックスから親の位置を求める場合は、次の式に従います。

$$parent=\begin{bmatrix}\frac{child}{2} \end{bmatrix}$$

このアプローチは、親や子のインデックスを数式だけで即座に計算できる点が大きな利点です。しかし一方で、メモリ効率の面では劣るという欠点があります。木が不完全な場合、使用されない空白領域が大量に発生してしまうためです。したがって、この表現方法は完全二分木や全二分木のような、ノードが密に詰まった木に適しています。

連結リストによる表現

もう一つの方法は、連結リストを使用するものです。この場合、各要素に対して個別のノードを作成し、各ノードはデータと左右の子へのポインタを持ちます。イメージは以下のようになります。

連結リストによる表現では、存在しない子のための無駄な領域を確保する必要がないため、ノードが疎な木でもメモリを効率的に利用できるというメリットがあります。