3 2分木

3.1 2分木のイメージ

2分木(binary tree)は，各ノードの子の数がたかだか2であるようなツリーである．これ は単純ではあるが，先に示した順序の中央順にデータを並べ，順序木を作ることで応用範 囲が広がる．そのようなわけで，ツリー構造の中でもっとも単純ではあるが，アルゴリズ ムで使用される頻度はもっとも高い．単純なものほど応用範囲が広い--という一つの例 である．

子と親の大小関係を決め，それに従って2分木を作ると順序木になる．たとえば，次のよ うに大小関係を決めるのである．

• 左側の子は，その親より必ず小さい．
• 右側に子は，その親より必ず大きい．

図6にその例を示す．

図6の2分木を，中央順(postorder)に並べると，

$$11\rightarrow 15\rightarrow 20\rightarrow 23\rightarrow 31\righta... ...tarrow 55\rightarrow 65\rightarrow 73\rightarrow 81\rightarrow 88\rightarrow 94$$

となる．昇順にデータが並んでいることが分かる．

この構造のあるノードの左側と右側はそれぞれの子を頂点とする木構造になる．この子孫 に対しても，同じ規準が適用されれるので，再帰による処理が可能となる．

図 6: ツリー構造(2分探索木)

3.2 データの作成

以下の順序で2分木を作成する．ルートから大小関係をたどっていき，子が無いところへ データを挿入する．

6,10,2,8,12,4

作成されるツリーは，図7のようになる．

図 7: ツリーのノードの作成順序

手順1	手順2	手順3
手順4	手順5	手順6

3.3 データの追加

先ほど作成したツリーにデータ9を追加する．これも，ルートから大小関係をたどってい き，子が無いところへデータを挿入する．すると，図8のようになる．

図 8: ツリーへのデータの追加

3.4 データの削除

元のツリー図9からデータを削除することを考える．

図 9: データを削除する前の2分木

データを削除する場合，子が無い場合，子がひとつの場合，子がふたつの場合にに分けて 考えなくてはならない．

• 削除するデータに子が無い場合は，そのまま削除する(図10)．
• 削除するデータがひとつの子をもつ場合は，削除した場所にその子と子孫を入れ る(図11)．
• 削除するデータがふたつの子を持つ場合．削除した場所に，左側の子孫の最大値 (あるいは右側の子孫の最少値)を移動させる(図12)．

図 10: 元のツリー図9から3を削除．子が無い場合は，そのまま削除す る．

図 11: 元のツリー図9から2を削除．子がひとつの場合は， 削除した部分にその子を移す．

図 12: 元のツリー図9から10を削除．子が二つの場合は，削 除した部分に，左側の子孫の最大の値をもつノードを移動させる．

ホームページ: Yamamoto's laboratory
著者: 山本昌志