第4回 もっとAVL木で木構造を学ぼう

　第3回「AVL木で木構造を学ぼう」では、AVL木に節点を追加する際に、バランスを回復する動作までを解説しました。

　今回は、AVL木の実装をさらに進めて、節点を削除する際の動作を取り上げます。

　筆者はDelphi 2009でサンプルプログラムを作成していますが、Delphiをお持ちでない方は下記のURLからTurboDelphiをダウンロードして、インストールしてみてください。

関連リンク：
	Delphiトライアル版／無償バージョン http://www.codegear.com/jp/downloads/free/delphi

AVL木からの節点の削除

　AVL木はソート木の一種なので、節点を削除する場合、木のソートが保たれている必要があります。ソート木で節点を削除する際に注意する点が3つあります。

1. 削除される節点に子が1つだけある場合、削除した後でその子を削除した節点の位置に入れ替える

2. 削除される節点に子が2つある場合、削除した後で左側の部分木の一番右側の子を削除した節点の位置に入れ替える

3. 2の場合、入れ替える節点の左側に子があった場合（条件的に右側には存在しませんね）には、入れ替え前の位置にその左側の子を移す

　ところが、こうした操作を行うと木の高さが変化する可能性があります。そのためAVL木では、これらの処理を行った後で木全体のバランスをチェックして、バランスが崩れている場合には回復する動作を行う必要があります。

左回転でバランスを回復させる

　バランスが崩れる場面は複数想定されるわけですが、要約すると以下の2つしかありません。

• ある節点の右側の部分木が高い場合に、左側の部分木が低くなった
• ある節点の左側の部分木が高い場合に、右側の部分木が低くなった

　AVL木では、高さの差は1までと決まっています。ある節点に着目した場合、右側が高いか、左側が高いか、高さは等しいかの3通りしか木の状態は存在しません。サンプルプログラムでは、これをDelphiの列挙型 TBalance = (brLeft, brEqual, brRight) で表現しました。

　削除に際して、バランスが崩れるというのは高さの差が2になるということなので、低い方がより低くなるという条件になるわけです。

　さて、右側の部分木が高い場合を考えてみると、さらに2つの条件でバランス回復の動作が異なることが分かります。例えば、節点Aに着目したとき、右側が高く（Balance=brRight）、右側の子である節点Bのさらに下で右部分木より左部分木が低い（または等しい）高さの場合には、左回転動作を行うことで、A節点での木の高さを変化させることなくバランスを回復できます。

1/2

Index
もっとAVL木で木構造を学ぼう
	Page1 AVL木からの節点の削除 左回転でバランスを回復させる
	Page2 右−左回転でバランスを回復させる AVLTreeの拡張 AVL木はいろいろなところで使われている
	Appendix1 AVLTree2.pasのソースコード
	Appendix2 avllisttree.pasのソースコード

Delphiアルゴリズムトレーニング

	いまさらアルゴリズムを学ぶ意味 コーディングに役立つ！ アルゴリズムの基本（1）　コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう
	Zope 3の魅力に迫る Zope 3とは何ぞや？（1）　Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？
	貧弱環境プログラミングのススメ 柴田 淳のコーディング天国　高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？
	Haskellプログラミングの楽しみ方 のんびりHaskell（1）　関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう
	ちょっと変わったLisp入門 Gaucheでメタプログラミング（1）　Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう
	more

　　Coding Edgeフォーラムフィード　 2.0／1.0／0.91