DSWアルゴリズム
From Wikipedia, the free encyclopedia
DSWアルゴリズム (Day-Stout-Warren algorithm) は、効率的に二分探索木を平衡化する手法である。つまり、ノード数を n として、その高さを O(log n) に圧縮する。操作のたびに平衡化を行う平衡二分探索木とは異なり、平衡化のコストは累次の操作によって償却される。このアルゴリズムは、1976 年の Colin Day の研究[1]に基づき、1986 年の CACM 論文において Quentin F. Stout と Bette Warren によって設計された[2]。
このアルゴリズムは、線形時間 (O(n)) のIn-placeアルゴリズムである。Day による元々のアルゴリズムでは、可能な限り高さの低い木が生成される。これによって最も下を除くすべての階層は完全に満たされた状態となる。この操作は2つの段階に分けられ、まず（糸付きの）木のノードのポインタを利用し、木を通りがけ順 (in-order) に走査して連結リストに変換する。そして一連の左回転操作が第2段階となる[3]。
Stout-Warren による修正では、完全二分木、すなわち最も下の階層が左から右へ連続的に満たされた木が生成される。この変換は、それ以上の挿入を行わないことが分かっているときに有用である。木が糸付き木である必要はなく、操作も定数空間で行える[2]。元々のアルゴリズムと同様に、Day-Stout-Warren は2段階で動作する。1段階目はまったく新しいものであり、2段階目は Day による回転の段階を修正したものである[2][3]。
Timothy J. Rolfe による 2002 年の論文が、DSW アルゴリズムが再び注目されるきっかけとなった[3]。その名前は、Adam Drozdek の教科書におけるセクション名 "6.7.1: The DSW Algorithm" に由来する[4]。Rolfe は、このアルゴリズムが適した場面を2つ挙げている。すなわち、「処理の開始時に二分探索木の全体を生成し、残りの処理はノードの探索のみである状況」、また「二分探索木における回転操作に最初に触れられることから、二分探索木から自己調整木 (self-adjusting tree) に進むデータ構造の学習過程」である。