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

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

はやしつとむ
アナハイムテクノロジー株式会社

2009/5/25

オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか(編集部)

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

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

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

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

icon AVL木からの節点の削除

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

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

削除される節点に子が1つだけある場合

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

削除される節点に子が2つある場合

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

入れ替える節点の左側に子があった場合

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

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

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

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

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

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

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

左回転
 
1/2
next

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

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

 Coding Edgeお勧め記事
いまさらアルゴリズムを学ぶ意味
コーディングに役立つ! アルゴリズムの基本(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の世界を体験してみよう
  Coding Edgeフォーラムフィード  2.01.00.91


Coding Edge フォーラム 新着記事
@ITメールマガジン 新着情報やスタッフのコラムがメールで届きます(無料)

注目のテーマ

>

Coding Edge 記事ランキング

本日 月間