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

第3回 AVL木で木構造を学ぼう

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

2009/4/13

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

 第2回「単純なキューと循環キュー」では、循環キュー構造を実装したCyclicQueueの解説と、TListやLinkedListを利用したキューについての比較を行いました。

 今回は、木構造を取り上げます。引き続き筆者はDelphi 2009でサンプルプログラムを作成していますが、Delphiをお持ちでない方は下記のURLからTurboDelphiをダウンロードしてぜひインストールして見て下さい。

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

icon 木構造とは何か?

 木構造は、データの関係を(ROOT)から複数の(EDGE)をたどって節点(NODE)を経由しながら(LEAF)へと至るようなデータ構造です。また、各ノードをルートに見立てて、それ以下の木構造を部分木と呼びます。

木構造

 どうして根が一番上なんだというのはいつも思う疑問ですが、逆さまに書くと見辛いかもしれません。試しに逆さまの木構造の図を作ってみました。

逆向きにした木構造

 他方、NODE間の上下関係は(PARENT)と(CHILD)と呼ばれますし、高さ(深さ?)が同じ位置にある節点同士は兄弟(SIBLING)と呼ばれて、この辺は家系図の呼称が使われています。こちらの方は、上から下へたどるのが普通だし、考え方としても分かりやすいですね。

 思いつきですが、いっそのこと根から葉へ向かうのではなくて、単子葉植物の「ひげ根(MUSTACHE)」のように根が枝分かれしながら地中へ向かっていると考えた方がいいかもしれません。つまり、木構造ではなくて根構造ですね。まあ、冗談ですが。

icon 木構造をたどる

 さて、木構造はその定義上ループは含まれていないので、ルートから始めてどんどん先へとたどって行くと、必ず行き止まり=リーフにたどり着きます。そのため、行って戻ってを再帰的に繰り返していくと、すべてのノード・リーフをたどれます。これを深さ優先探索(Depth first search)といいます。

深さ優先探索

 深さ優先探索で木構造をたどる場合には、再帰的に各ノード・リーフのデータを処理するわけですが、どこでデータを処理するかによって取り出し順が3つ存在します。節点の左側は自分より小さい値、右側は大きい値となるように木を構成した場合、以下の「通りがけ順」にたどって行くと、ソートされた結果が返ってきます。

行きがけ順(PREORDER):

  1. ノードのデータを処理する
  2. 左側の部分木を行きがけ順で再帰的に処理する
  3. 右側の部分木を行きがけ順で再帰的に処理する

通りがけ順(INORDER):

  1. 左側の部分木を通りがけ順で再帰的に処理する
  2. ノードのデータを処理する
  3. 右側の部分木を通りがけ順で再帰的に処理する

帰りがけ順(POSTORDER):

  1. 左側の部分木を帰りがけ順で処理する
  2. 右側の部分木を帰りがけ順で処理する
  3. ノードのデータを処理する

 これに対して、上から順に同じ深さのノードをたどって行く方法があります。しらみつぶしにすべてをたどるのであれば、こちらの方が効率がいいですね。幅優先探索(Breadth first search)と呼ばれています。データベースのインデックスとして考えると、Full Index Scanの場合には、こちらを使った方が良いということになるんじゃないかと思います。

幅優先探索

icon ロシアからやってきたAVL木

 それではこの木構造をDelphiでクラスとして実装して行きたいと思います。実装するのは平衡二分探索木(self-balancing binaryu search tree)のうち、AVL木とします。AVL木はロシア人の数学者アデルソンヴェルスキ(Georgy Maximovich Adelson-Velsky)とランディス(Yevgeniy Mikhailovich Landis)が考案したもので、以下の2つの特徴を持ちます。

  • 2つの子を持つ各節点において、左側部分木と右側部分木の高さが1以内であること
  • 1つの子しか持たない各節点において、その子は葉であること

AVL木

 AVL木では、節点を追加するときに、上記のバランスが崩れていないかをチェックしつつ、崩れていればそれを回復する処理を行う必要があります。それだけ手間が掛かるわけですが、バランスを取りながら木の高さを低く保つことで、探索時のコストを抑えることが可能になります。

 木がバランスしていない場合、最悪のケースでは上図のように1つずつすべてたどって行かなくてはならないケースも考えられます。この場合は、O記法でいうO(N)のコストが掛かってしまうわけですから、リストと変わらないことになります。

 ところが、左右のバランスが取れているのであれば、例えば1000要素あってもlog2(1000)≒10、つまり木の高さは10程度になるわけです。O(log(N))になるので、これはかなり速いことになります。

高さ 各段の要素数 合計要素数
0
1
1
1
2
3
2
4
7
3
8
15
4
16
31
5
32
63
6
64
127
7
128
255
8
256
511
9
512
1023
10
1024
2047

 もちろん、探索が速くなるかわりに挿入や削除の際のコストは余計に掛かることになります。そこで増加するコストが莫大なものでないのであれば、探索がひんぱんに行われる場合にはこちらの方が有利になるわけです。

 データベースにインデックスを付けるのもまさにこの理由からで、挿入や削除の際には余計なコストが掛かりますが、後々データを参照する際には圧倒的なスピードが実現できます。しかし、挿入や削除が頻繁に行われるときはインデックスを止めますよね。

 
1/2
next

Index
AVL木で木構造を学ぼう
Page1
木構造とは何か?
木構造をたどる
ロシアからやってきたAVL木
  Page2
AVL木への節点の追加
Listにそっくりな木構造のクラス
アルゴリズムの実装は編み物に似ている
  Appendix
AVLTreeのソースコード

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 記事ランキング

本日 月間