木の基本用語
このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
始めに順序木の用語を復習します。 順序木は有向二分木で、左の子孫、親、右の子孫の間で、順に値が大きくなる ようなものを言います。 根の頂点からもっとも遠い葉までの頂点数を深さと言います。
以後、大きな木の細部を省略する記号として、三角形を使用することにします。
順序木
すると順序木を左のように略記することができます。 この時、L に含まれるすべての要素は c より小さく、また R に含まれるすべ ての要素は c より大きくなります。
頂点数4の二分木をすべて書き出すと以下のようになります。
4頂点の二分木
上記のそれぞれの木に対して、順序木になるように各頂点に 1, 2, 3, 4 を与 えよ。
木の数
頂点数が決まったとき、木が何種類あるかを計算しましょう。 n 頂点の木の種類が T(n) 通りあるとします。 左右を意識すると、根の左側に来る頂点数は 0 個から n-1 個まであり えます。 この時右側に来る頂点数は n-1 個から 0 個までとなります。
根の左に k 個、右に n-1-k 個の頂点がある場合の木の種類は、左右独立に考 えると、部分木の種類がそれぞれ T(k) 通りと T(n-1-k) 通りになります。 従って、根の左に k 個頂点がある木の種類は T(k)T(n-1-k) 通りあることに なります。 頂点数 0 の木は 1 通りであると考えると、次の式を得ます。
実際に値を入れて計算すると次のような値になります。
| n | T(n) |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
次に、木の平均の深さを求めましょう。 ランダムな入力に対して、それにより木を構成し、木に対するアルゴリズムを 使用した場合、そのアルゴリズムの平均実行時間は木の平均の高さに比例する 場合があります。
4頂点木の深さ
木の深さの平均とは、例えば、右図のような4頂点の木の場合は (1+2+2+3)/4 となりますが、これをさらに14種類全部で平均を取ることを考えます。 n 頂点の木の各頂点の平均の深さを d(n) で表すことにします。 これの見積りも、前節と同様に考えます。 つまり、左の部分木に k 頂点、右の部分木に n-1-k 頂点ある時、 左の k 個の頂点の深さの合計は k(d(k)+1) で、右は (n-1-k)(d(n-1-k)+1) となります。 これに根の深さ 1 を加えることで全頂点の深さの合計が分かるので、次の漸 化式が得られます。
ここで両辺を で割ります。
木の深さ
素朴な順序木に順に要素を与えたとき
順序木を扱うプログラムの効率は順序木の高さに依存するので、データの格納 法を工夫しないと、高さの高い木ができて効率が悪くなることがあります。
データの任意の検索をするのではなく、最大値、あるいは最小値のみを検索す
るだけで良い場合、
二分木において、単に親が子より大きいという関係だけで木を作ることも考え
られます。
このような木を
Heap木
完全二分木を維持するように、葉の部分に要素を追加します。 その後、親と大小関係を比較していき、ヒープの条件を満たすように親子関係 を入れ替えていきます。 すると、高々根までの要素の入れ替えでヒープの条件を満たすように要素を追 加できます。
最大値の取り出し1
最大値である根の頂点を取り出し、削除できます。
この時、任意の葉を削除し、その葉にあった要素を根に入れます。
最大値の取り出し2
そして、子との大小を比較して、親が最大になるように要素を入れ替えていき ます。 すると、高々葉までの要素の入れ替えでヒープの条件を満たすように根の要素 を削除できます。
配列
Heap は常に完全二分木を保つように実装できるので、図のように配列の添字 と木の頂点を1対1対応させることができます。 さらに、このように対応させると、親の添字が k の場合、子の添字は 2k+1 と 2k+2 になり、また子の添字が m の場合、(m-1)/2 が親の添字になります。
この配列の実装を用いて、入力列を一旦配列の Heap 木に入れ、大きい順に要
素を取り出すようにする並び替えアルゴリズムを実装することができます。
この、並び替えのアルゴリズムを
なお、クイックソートの最悪計算量は O(n2) になるのに対して、 このヒープソートは最悪でも O(n log n) で動作する。 しかし、実際は平均的にはクイックソートの方が速いことが経験的に知られて いる。 但し、このヒープソートは再帰的なソートアルゴリズムに対して、スタックを 使用せず、補助的に使用する領域が少ないため、組み込み系など特殊な処理系 で利用しやすい。
木の回転
効率の良い順序木を作成するのに、木を効率よく変形することを考える。 順序木において、回転とは図のように、大小関係を変化させずに一部の親子関 係を逆転させる操作である。
図において A≤x≤ B≤ y≤ C という関係は保たれている。
平衡木
さて、順序木を作る際に、要素の追加の度に全ての部分木の高さを管理して、 葉から根に向けて各左右の部分木の高さが±1になるようにこの回転を適用す る素朴なアルゴリズムを考えます。 このようなアルゴリズムで管理された木はバランス木や AVL木と呼ばれます。
B木
B木 は多分木の平衡木で、ハードディスクなどのブロック単位でランダムアクセス するような媒体に対して実用的で効率的なデータ構造です。 NTFSなどのファイルシステムやデータベースシステムなどに使用されてます。 B木を改良した B+木や B*木なども知られてますが、本稿では B木のみを説明 します。
データ構造は、図のような多分木になります。 各ノードが与えられた次数-1分だけマスがあります。 マスの境界が両端を含めて次数分だけあります。 各マスには昇順でデータを入れます。 子ノードは親ノードのデータの境界に接続していて、子ノードのデータはすべ て親ノードの（あれば）境界の左側のデータより大きく、（あれば）境界の右 側のノードより小さくなっています。 つまり、右図では A≤x≤B≤y≤C≤z≤D が成り立ちます。
データの挿入は必ず葉に行います。 但し、ノードがいっぱいでデータが入れられない場合は、入れようとしている データとノード内のデータのうちの中央値を一つ選び、中央値より小さいデー タで一つノードを作り、中央値より大きいデータでも一つノードを作り、その 二つのノードが左右の境界に接続するように中央値を親ノードに追加します。 但し、これで親ノードがいっぱいになったら、この中央値からノードを二分す る操作を再帰的に行います。
|
|
| 4次のB木へ「1,2,3,4,5,6,7」を挿入 | 3次のB木へ「1,2,3,4,5,6,7」を挿入 |
|---|---|
赤黒木
赤黒木は次の性質を持つ二分順序木です。
頂点数７の完全二分木の赤黒木を右に示します。
赤黒木は黒の頂点の数を考えると、葉までの頂点数は黒の頂点数と一致するか、 それと同じ数だけの赤の頂点も含むかのいずれかになるので、次の性質が得ら れます。
根から葉までの最短の道の長さが n の時、 最長の道の長さはたかだか 2n 以下である。
さらに、これから頂点数 N の時の最長の道の長さを求める。 根から葉までの黒頂点の数を k とすると、木の形はすべて黒頂点の時が最小になっ て、すべての道が黒赤の連続の時が最大になるので、次の式が成り立つ。
この時最長の道の長さは 2log N 以下になる。
赤黒木にデータを挿入するには、まず、通常の順序木と同様に葉に赤色の頂点 として追加します。 その後、もし、追加した頂点の親の頂点が赤の場合、赤の頂点が隣接しないと いうルールに反することになるので、上記のルールを満たすように、次の手続 きを根に向かって再帰的に行います。 これは親の兄弟の頂点（親との左右の区別無く叔父頂点と呼ぶことにします） の色と大小関係により次の3つの条件に分かれます。 なお、もともと条件の適合した赤黒木に頂点を挿入したという条件より、親が 赤頂点ならば、親頂点の親頂点（祖父頂点とします）は黒頂点に なります。
赤黒木case1
親頂点と叔父頂点を黒にし、祖父頂点を赤にします。 そして、祖父頂点に関して、またこの手続きを再帰的に適用します。
赤黒木case2
親頂点と祖父頂点で回転を行います。 そして、親頂点を黒、祖父頂点を赤にします。 この場合は部分木の根が親頂点になり、黒となるので、ここで再帰処理は終了 です。
赤黒木case3
子頂点と親頂点で回転を行います。親頂点と子頂点はともに赤のままですが、 大小関係に関して親子関係が逆転するので、これで case2 に帰着できます。
赤黒木に「5,2,1,6,7,4,3」を挿入
右は赤黒木に「5,2,1,6,7,4,3」を挿入をしたときの、データ構造である。