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段階となる。