第4回 もっとAVL木で木構造を学ぼう
はやしつとむ
アナハイムテクノロジー株式会社
2009/5/25
オブジェクト指向によって、アルゴリズムは隠ぺいされていることが多くなった。しかし、「用意されていない処理」が求められたときに対応できるだろうか(編集部)
第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アルゴリズムトレーニング |
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の世界を体験してみよう |
|
- プログラムの実行はどのようにして行われるのか、Linuxカーネルのコードから探る (2017/7/20)
C言語の「Hello World!」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。最終回は、Linuxカーネルの中では、プログラムの起動時にはどのような処理が行われているのかを探る - エンジニアならC言語プログラムの終わりに呼び出されるexit()の中身分かってますよね? (2017/7/13)
C言語の「Hello World!」プログラムで使われる、「printf()」「main()」関数の中身を、デバッガによる解析と逆アセンブル、ソースコード読解などのさまざまな側面から探る連載。今回は、プログラムの終わりに呼び出されるexit()の中身を探る - VBAにおけるFileDialog操作の基本&ドライブの空き容量、ファイルのサイズやタイムスタンプの取得方法 (2017/7/10)
指定したドライブの空き容量、ファイルのタイムスタンプや属性を取得する方法、FileDialog/エクスプローラー操作の基本を紹介します - さらば残業! 面倒くさいエクセル業務を楽にする「Excel VBA」とは (2017/7/6)
日頃発生する“面倒くさい業務”。簡単なプログラミングで効率化できる可能性がある。本稿では、業務で使うことが多い「Microsoft Excel」で使えるVBAを紹介する。※ショートカットキー、アクセスキーの解説あり
|
|