DSWアルゴリズム

DSWアルゴリズム (Day-Stout-Warren algorithm) は、効率的に二分探索木を平衡化する手法である。つまり、ノード数を nとして、その高さを O(log n) に圧縮する。操作のたびに平衡化を行う平衡二分探索木とは異なり、平衡化のコストは累次の操作によって償却される。このアルゴリズムは、1976 年の Colin Day の研究に基づき、1986 年の CACM 論文において 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アルゴリズムの擬似コードである。3つのサブルーチンと1つのメインルーチンからなる。メインルーチンは以下で与えられる。

(一)﹁擬似根ノード﹂となるノードを作成し、その右の子を木の実際の根にする。

(二)引数として擬似根ノードを与えて tree-to-vine を呼ぶ。

(三)擬似根ノードおよび木のサイズ(要素数)で vine-to-tree を呼ぶ。

(四)木の実際の根を擬似根ノードの右の子に等しくする。

(五)擬似根ノードを破棄する。

サブルーチンは以下のように定義される。

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