Day–Stout–Warren algorithm
The DSW algorithm, or in full Day/Stout/Warren algorithm, is a method for efficently balancing binary search trees — that is, decreasing their height to O(log n) nodes. Unlike a self-balancing binary search tree, it does not do this incrementally during each operation, but periodically, so that its cost can be amortized over many operations. The algorithm was designed by Quentin Stout and Bette Warren in their 1986 paper Tree Rebalancing in Optimal Time and Space, based on work done by Colin Day in 1976.
The algorithm requires linear time (O(n), where n is the number of nodes in the tree) and is in-place. Besides being simpler than many earlier tree-balancing algorithms, simple enough to teach in elementary data structure classes, it can also be easily modified to balance trees perfectly; that is, such that no two leaves differ in depth by two or more. This is a useful transformation to perform if it's known that no more inserts will be done.
A 2002 article by Timothy J. Rolfe has recently brought attention back to the DSW algorithm after a long hiatus.
External links
- An explanation and some experiments by Timothy J. Rolfe
- The original paper by Stout and Warren
 | This computing article is a stub. You can help Wikipedia by expanding it. |