View source for Day–Stout–Warren algorithm

{{Short description|Method for efficiently balancing binary search trees}}
The '''Day–Stout–Warren (DSW) algorithm''' is a method for efficiently balancing [[binary search tree]]s{{snd}} that is, decreasing their height to [[Big-O notation|O]](log ''n'') nodes, where ''n'' is the total number of 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 analysis|amortized]] over many operations. The algorithm was designed by Quentin F. Stout and Bette Warren in a 1986 [[Communications of the ACM|''CACM'']] paper,<ref name="sw">{{cite journal |first1=Quentin F. |last1=Stout |first2=Bette L. |last2=Warren |date=September 1986 |journal= 	Communications of the ACM |volume=29 |issue=9 |pages=902–908 |title=Tree rebalancing in optimal space and time |doi= 10.1145/6592.6599 |url=http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf|hdl=2027.42/7801 |s2cid=18599490 |hdl-access=free }}</ref> based on work done by Colin Day in 1976.<ref>{{cite journal |first=A. Colin |last=Day |title=Balancing a Binary Tree |journal=[[The Computer Journal|Comput. J.]] |volume=19 |issue=4 |year=1976 |pages=360–361 |doi=10.1093/comjnl/19.4.360 |doi-access=free}}</ref>

The algorithm requires linear (O(''n'')) time and is [[in-place algorithm|in-place]]. The original algorithm by Day generates as compact a tree as possible: all levels of the tree are completely full except possibly the bottom-most. It operates in two phases. First, the tree is turned into a [[linked list]] by means of an [[in-order traversal]], reusing the pointers in the ([[Threaded binary tree|threaded]]) tree's nodes. A series of [[Tree rotation|left-rotations]] forms the second phase.<ref name="rolfe">{{cite journal |first=Timothy J. |last=Rolfe |title=One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm |url=http://penguin.ewu.edu/~trolfe/DSWpaper/ |journal=SIGCSE Bulletin |volume=34 |issue=4 |pages=85–88 |publisher=ACM SIGCSE |date=December 2002 |doi=10.1145/820127.820173 |s2cid=14051647 |archive-url=https://archive.today/20121213000401/http://penguin.ewu.edu/~trolfe/DSWpaper/ |url-status=live |archive-date=2012-12-13 |url-access=subscription }}</ref>
The Stout–Warren modification generates a complete binary tree, namely one in which the bottom-most level is filled strictly from left to right.  This is a useful transformation to perform if it is known that no more inserts will be done. It does not require the tree to be threaded, nor does it require more than [[Space complexity|constant space]] to operate.<ref name="sw"/> Like the original algorithm, Day–Stout–Warren operates in two phases, the first entirely new, the second a modification of Day's rotation phase.<ref name="sw"/><ref name="rolfe"/>

A 2002 article by Timothy J. Rolfe brought attention back to the DSW algorithm;<ref name="rolfe"/> the naming is from the section title "6.7.1:  The DSW Algorithm" in Adam Drozdek's textbook.<ref>{{cite book |first=Adam |last=Drozdek |title=Data Structures and Algorithms in C++ |publisher=PWS Publishing Co. |year=1996 |pages=173–175 |isbn=0-534-94974-6}}</ref> Rolfe cites two main advantages: "in circumstances in which one generates an entire binary search tree at the beginning of processing, followed by item look-up access for the rest of processing" and "pedagogically within a course on data structures where one progresses from the binary search tree into self-adjusting trees, since it gives a first exposure to doing rotations within a binary search tree."

== Pseudocode ==

The following is a presentation of the basic DSW algorithm in [[pseudocode]], after the Stout–Warren paper.<ref name="sw"/><ref group=note>This version does not produce perfectly balanced nodes; Stout and Warren present a modification that does, in which the first call to {{mono|compress}} is replaced by a different subroutine.</ref> It consists of a main routine with three [[subroutine]]s. The main routine is given by

# Allocate a node, the "pseudo-root", and make the tree's actual root the right child of the pseudo-root.
# Call ''tree-to-vine'' with the pseudo-root as its argument.
# Call ''vine-to-tree'' on the pseudo-root and the size (number of elements) of the tree.
# Make the tree's actual root equal to the pseudo-root's right child.
# Dispose of the pseudo-root.

The subroutines are defined as follows:<ref group=note>In the original presentation, ''tree-to-vine'' computed the tree's size as it went. For the sake of brevity, we assume this number to be known in advance.</ref>

 '''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<sup>⌊log<sub>2</sub>(size + 1)⌋</sup>
     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

== Notes ==
{{reflist|group=note}}

== References ==
{{reflist}}

{{DEFAULTSORT:Day-Stout-Warren algorithm}}
[[Category:Search trees]]
[[Category:Amortized data structures]]