The Day–Stout–Warren (DSW) algorithm is a method for efficiently balancing binary search trees – that is, decreasing their height to O(log n) nodes, where n is the total number of nodes.
The algorithm was designed by Quentin F. Stout and Bette Warren in a 1986 CACM paper,[1] based on work done by Colin Day in 1976.
[3] The Stout–Warren modification generates a complete binary tree, namely one in which the bottom-most level is filled strictly from left to right.
[1][3] A 2002 article by Timothy J. Rolfe brought attention back to the DSW algorithm;[3] the naming is from the section title "6.7.1: The DSW Algorithm" in Adam Drozdek's textbook.
The following is a presentation of the basic DSW algorithm in pseudocode, after the Stout–Warren paper.