探索二分木をバランス化する。

書き込みや削除を繰り返して深さに差の出た探索二分木をバランス化する手続きを作りたいのですが、どのようなアルゴリズムで組めばよいでしょうか。

使用言語はPascalです。
よろしくお願いします。

No.3 回答者： chie65536 回答日時： 2008/02/04 10:41

＞親の入れ替えを行う際枝の分かれ方によって入れ替え方が4パターンあると思うのですが、それは全て場合分けして書くのでしょうか。

場合分けは
右にズラしてバランスするか左にズラしてバランスするか、で2パターン
親から見て、ズラすノードが右腕にあるか左腕にあるか、で2パターン
になります。

これら２つの処理をいっぺんに書けば、2パターン×2パターンで4パターンになりますが、別々に書けば4パターンも要りません。

No.2 回答者： chie65536 回答日時： 2008/01/31 17:36

＞書き込みや削除を繰り返して深さに差の出た探索二分木をバランス化する手続きを作りたい

う～む。普通は「削除を終えた直後」「挿入を終えた直後」に「バランス化を行う」のですが。

因みに「更新（書き込み）」は「更新前データを削除して、更新データを挿入する」と言う手続きで可能です。

で、バランスを取る際は各ノードの「右腕の長さ」と「左腕の長さ」を調べる必要があります。
　　　　　　　　　根
　　　　　　　／
　　　　　 Ａ
　　　　／　＼
　　　Ｂ　　　 Ｃ
　／
Ｄ
の状態でＣを削除すると
　　　　　　　　　根
　　　　　　　／
　　　　　 Ａ
　　　　／
　　　Ｂ
　／
Ｄ
となり「Ａの左腕は長さ２、右腕は長さ０」になります。

ここで「左右の長さの差が２以上になっていたら」
　　　　　　根
　　　　／
　　　Ｂ
　／　　＼
Ｄ　　　　　Ａ
のように、親の入れ替えを行います。

これを「変化(挿入か削除)があったノードの親からスタートして、根に辿り付くまで」繰り返します。

なお「ある時点で一気にバランス化する」のであれば「最小値のノードから、最大値のノードまでを順に、各ノードすべてにおいて、上記の腕の長さのチェックと入れ替え」が必要になります。

この回答へのお礼

返事遅くなりました。
わかりやすい説明ありがとうございます。

重ねて質問なのですが、親の入れ替えを行う際枝の分かれ方によって入れ替え方が4パターンあると思うのですが、それは全て場合分けして書くのでしょうか。

お礼日時：2008/02/02 23:00

No.1 回答者： sakusaker7 回答日時： 2008/01/31 17:18

とりあえず「赤黒木」(red-black tree)とか

「AVL木」(AVL tree)というキーワードで検索してみて、
見つかった説明でわからなかったらどのあたりがわからないのかを
具体的に書いてみてください。