DSWアルゴリズム (Day-Stout-Warren algorithm) は、効率的に二分探索木を平衡化する手法である。つまり、ノード数を n として、その高さを O(log n) に圧縮する。操作のたびに平衡化を行う平衡二分探索木とは異なり、平衡化のコストは累次の操作によって償却される。このアルゴリズムは、1976 年の Colin Day の研究に基づき、1986 年の 論文において Quentin F. Stout と Bette Warren によって設計された。
このアルゴリズムは、線形時間 (O(n)) のIn-placeアルゴリズムである。Day による元々のアルゴリズムでは、可能な限り高さの低い木が生成される。これによって最も下を除くすべての階層は完全に満たされた状態となる。この操作は2つの段階に分けられ、まず（糸付きの）木のノードのポインタを利用し、木を通りがけ順 (in-order) に走査して連結リストに変換する。そして一連の左回転操作が第2段階となる。
Stout-Warren による修正では、完全二分木、すなわち最も下の階層が左から右へ連続的に満たされた木が生成される。この変換は、それ以上の挿入を行わないことが分かっているときに有用である。木が糸付き木である必要はなく、操作も定数空間で行える。元々のアルゴリズムと同様に、Day-Stout-Warren は2段階で動作する。1段階目はまったく新しいものであり、2段階目は Day による回転の段階を修正したものである。
Timothy J. Rolfe による 2002 年の論文が、DSW アルゴリズムが再び注目されるきっかけとなった。その名前は、Adam Drozdek の教科書におけるセクション名 "6.7.1: The DSW Algorithm" に由来する。Rolfe は、このアルゴリズムが適した場面を2つ挙げている。すなわち、「処理の開始時に二分探索木の全体を生成し、残りの処理はノードの探索のみである状況」、また「二分探索木における回転操作に最初に触れられることから、二分探索木から自己調整木 (self-adjusting tree) に進むデータ構造の学習過程」である。
擬似コード 以下は、Stout-Warren の論文で示された、基本的なDSWアルゴリズムの擬似コードであるこのバージョンでは、完全な平衡木は生成されない。Stout と Warren は、 の最初の呼び出しを異なるサブルーチンに置き換えた修正版を示している。。3 つのサブルーチンと 1 つのメインルーチンからなる。メインルーチンは以下で与えられる。 「擬似根ノード」となるノードを作成し、その右の子を木の実際の根にする。 引数として擬似根ノードを与えて tree-to-vine を呼ぶ。 擬似根ノードおよび木のサイズ(要素数)で vine-to-tree を呼ぶ。 木の実際の根を擬似根ノードの右の子に等しくする。 擬似根ノードを破棄する。
サブルーチンは以下のように定義される元々のものは、tree-to-vine は木のサイズも計算していた。簡略化のため、ここでは木のサイズは既知とする。。
routine tree-to-vine(root) // Convert tree to a "vine", i.e., a sorted linked list, // using the right pointers to point to the next node in the list tail ← root rest ← tail.right while rest ≠ nil if rest.left = nil tail ← rest rest ← rest.right else temp ← rest.left rest.left ← temp.right temp.right ← rest rest ← temp tail.right ← temp
routine vine-to-tree(root, size) leaves ← size + 1 − 2⌊log2(size + 1))⌋ compress(root, leaves) size ← size − leaves while size > 1 compress(root, ⌊size / 2⌋) size ← ⌊size / 2⌋
routine compress(root, count) scanner ← root for i ← 1 to count child ← scanner.right scanner.right ← child.right scanner ← scanner.right child.right ← scanner.left scanner.left ← child
注釈
参考文献