平衡二分探索木の範囲削除の比較検討

内容概要

　本研究では，平衡二分探索木の一種であるAVL木における範囲削除操作の最適化を目指し研究を行った．具体的には，範囲削除機能が備わっていないAVL木，スプレー木と範囲削除を行う３つの手法を導入したAVL木の範囲削除における処理時間を比較した．この研究により，効率的な範囲削除が可能となれば，データ構造の最適化に貢献できると考えられる．

はじめに

研究背景

　データベース，検索エンジンなどの多岐にわたる分野でデータ構造の効率性が求められている．その中でAVL木は，挿入や検索，削除の操作が効率よく行えるという特性から，広く採用されている．しかし，範囲削除においては従来のAVL木の削除操作では十分な性能が得られないと考えられる．本研究では，この問題に焦点を当てて，範囲削除の様々な手法を提案し，評価を行う．

研究内容

　本研究では，再帰を利用した範囲削除手法，削除対象を特定後に削除操作を行う手法，範囲内を一括削除した後にバランス調整を行う手法をAVL木に導入し，範囲削除機能を持たないAVL木，範囲削除に優れたスプレー木との範囲削除時の処理時間を比較，評価を行う．

二分探索木

　探索木とは，ノードに要素を割り当てたものであり，ノードの挿入，検索，削除を効率よく実行するためものである．基本的は探索木としては，二分探索木，Ｂ木，平衡二分探索木などがあるが，本研究では最も基本的とされる二分探索木について取り上げる．
　二分探索木は，各ノード v に割り当てられる要素を key[v] と表すと，任意の節点 v において，v の左の子の任意の子孫 u および v の右の子の任意の子孫 w に対して，

が成り立つように割当られたものである．この性質により，検索や挿入，削除操作が効率的に行なえる．

平衡二分探索木

　二分探索木では，データに偏りがある場合，枝分かれが一方向に延び，二分探索木の深さがデータのサイズに一致してしまう．このとき，ノードの数をnとすると，最悪の場合にはどの操作にはO(n) 時間がかかることになる．しかし，木の各ノードや葉がある程度調整されていて高さの差がないとき，すなわち， O(logn)のとき，探索の手間は O(logn)時間となる．この深さが O(logn)の二分探索木を平衡二分探索木という．

AVL木

　AVL木は，バランスが崩れないように設計された平衡二分探索木であり，各ノードにおいて右部分木の深さから左部分木の深さを引いた値の平衡係数が１以下という条件を満たす平衡木のことである．データの操作後に平衡係数が変化した場合，平衡係数が崩れている箇所で再平衡化が行われる．
　再平衡化は１回転操作と２重回転操作の２つの主要な操作によって行われる．これらの操作によって木のバランスが維持される．

スプレー木

　スプレー木は，通常の二分探索木と異なり，操作が行われるたびにアクセスされたノードを根に持ってくることで，最近アクセスされたデータが常に効率的にアクセスできるようになっている．これにより，アクセス頻度の高いデータが木の浅い部分に集中し，探索操作の平均時間が短縮される．

使用する範囲削除アルゴリズム

　本研究では，従来の平衡二分探索木における削除操作の制約に注目し，その問題点を解決するために新たな範囲削除アルゴリズムを３つ提案する．従来の操作では一度に１つのデータのみを処理でき，複数のデータを削除する場合，各データを１つずつ削除する必要がある．この個別の削除操作が行われる際，削除されたデータごとにルートまで戻ることが必要となり，これが効率の低下を招く可能性がある．

（手法１）削除対象を特定後，削除操作を行う手法

　従来の二分探索木で範囲削除を行う際，従来の方法だと削除範囲のデータを削除した後，その都度ルートに戻り再度削除範囲のデータの検索を行う必要がある．これに対して，範囲内を一度収集してから一括に削除を行う手法では，削除範囲内のノードをまとめて検索し，それを一括で処理するため，ルートに戻る必要がない．

（手法２）再帰を利用した範囲削除

　従来の二分探索木の範囲削除操作では，範囲の最小値から最大値まで順に検索操作を行う．データの有無に関わらずすべての範囲に検索をかける．これを改善するため、ノードのキーが指定された範囲よりも小さい場合、右側のサブツリーを、大きい場合は左側のサブツリーに再帰的に処理を行う．この条件分岐により、不要なノードを効率的にスキップし、処理対象の絞り込みを行うことが可能になる．
　範囲内のノードに対しては、再帰的に削除関数を呼び出し、ノードを削除する．削除後は、再び範囲削除を行う。このサイクルを通じて、範囲内の全てのノードが効率的に削除される。

（手法３）リストを利用した範囲削除

　削除範囲を一度リストにいれ，一括削除を行った後，再び探索木を再構築する手法である．従来のAVL木だと個別に削除後，再平衡化が行われるが，提案した手法は，範囲内のノードをまとめて削除した後、再構築のために一度だけ再平衡化が行われる．これにより，範囲削除も効率的に行いつつ，平衡操作も一度で済むため，従来のAVL木よりも効率的に範囲削除を行う可能性がある．

実験

　本研究では，ランダムの数値データを使用し，木構造のサイズを1000から10万までを使用した．その時の削除範囲を100,1000,10000と変化させてその時の処理時間の比較を行った．結果は以下の表である．

木構造サイズ	従来のAVL木	スプレー木	手法１	手法２	手法３
1000	1385	1225	1337	1150	842
10000	1697	1422	1657	1463	1203
100000	2038	1765	1984	1812	1479

表1　削除範囲が100のときの処理時間(ナノ秒)

木構造サイズ	従来のAVL木	スプレー木	手法１	手法２	手法３
1000	3942	1438	1265	1258	873
10000	4153	1649	2232	1788	1215
100000	4981	2424	5100	3067	1537

表2　削除範囲が1000のときの処理時間(ナノ秒)

木構造サイズ	従来のAVL木	スプレー木	手法１	手法２	手法３
1000	23142	2487	2103	1727	1144
10000	27121	3216	8393	5020	1240
100000	33432	6423	30713	5780	1577

表3　削除範囲が10000のときの処理時間(ナノ秒)

考察

　手法１の削除対象を特定後，削除操作を行う範囲削除は，小さい木構造では効果的に範囲削除操作を行うことが出来たが，木構造のサイズが大きくなると処理が遅くなる．これは木構造全体に対して検索をかけ，削除対象を見つけるためである．

　手法２，手法３の再帰を利用した範囲削除，リストを利用した範囲削除は，スプレー木同等またはそれ以上の性能を示した．これは再帰を利用する手法は，自然な方法で木構造をたどり削除操作を実行することが出来たと考えられ，リストを利用した手法は，複数のノードを一度に処理するため，特に範囲削除において優れた性能を発揮することができたと考えられる．

　今後の課題として，今回の実験では計ることができなかったメモリの使用量だが，リストを使用した手法において，メモリの使用量を削減する方法を模索する必要がある．特に大規模なデータに対して効率的なメモリ管理が求められる．
　また，提案手法が範囲削除において安定して動作するかどうかを確認する必要がある．例えば，データが偏ったケースや昇順，降順などのデータ．

おわりに