Day–Stout–Warren algorithm

<h2 id="pseudocode">Pseudocode</h2>
The following is a presentation of the basic DSW algorithm in <a href="/facts/Pseudocode/XgN19duK">pseudocode</a>, after the Stout–Warren paper.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> It consists of a main routine with three <a href="/facts/Subroutine/9vFJrg0A">subroutines</a>. The main routine is given by

<ol><li>Allocate a node, the "pseudo-root", and make the tree's actual root the right child of the pseudo-root.</li>
<li>Call tree-to-vine with the pseudo-root as its argument.</li>
<li>Call vine-to-tree on the pseudo-root and the size (number of elements) of the tree.</li>
<li>Make the tree's actual root equal to the pseudo-root's right child.</li>
<li>Dispose of the pseudo-root.</li></ol>
The subroutines are defined as follows:<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

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

<h2 id="notes">Notes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Stout, Quentin F.; Warren, Bette L. (September 1986). "Tree rebalancing in optimal space and time" (PDF). Communications of the ACM. 29 (9): 902–908. doi:10.1145/6592.6599. hdl:2027.42/7801. S2CID 18599490. <a href="http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf" target="_blank">http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Day, A. Colin (1976). "Balancing a Binary Tree". Comput. J. 19 (4): 360–361. doi:10.1093/comjnl/19.4.360. <a href="https://doi.org/10.1093%2Fcomjnl%2F19.4.360" target="_blank">https://doi.org/10.1093%2Fcomjnl%2F19.4.360</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Rolfe, Timothy J. (December 2002). "One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm". SIGCSE Bulletin. 34 (4). ACM SIGCSE: 85–88. doi:10.1145/820127.820173. S2CID 14051647. Archived from the original on 2012-12-13. <a href="http://penguin.ewu.edu/~trolfe/DSWpaper/" target="_blank">http://penguin.ewu.edu/~trolfe/DSWpaper/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Stout, Quentin F.; Warren, Bette L. (September 1986). "Tree rebalancing in optimal space and time" (PDF). Communications of the ACM. 29 (9): 902–908. doi:10.1145/6592.6599. hdl:2027.42/7801. S2CID 18599490. <a href="http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf" target="_blank">http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Stout, Quentin F.; Warren, Bette L. (September 1986). "Tree rebalancing in optimal space and time" (PDF). Communications of the ACM. 29 (9): 902–908. doi:10.1145/6592.6599. hdl:2027.42/7801. S2CID 18599490. <a href="http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf" target="_blank">http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Rolfe, Timothy J. (December 2002). "One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm". SIGCSE Bulletin. 34 (4). ACM SIGCSE: 85–88. doi:10.1145/820127.820173. S2CID 14051647. Archived from the original on 2012-12-13. <a href="http://penguin.ewu.edu/~trolfe/DSWpaper/" target="_blank">http://penguin.ewu.edu/~trolfe/DSWpaper/</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Rolfe, Timothy J. (December 2002). "One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm". SIGCSE Bulletin. 34 (4). ACM SIGCSE: 85–88. doi:10.1145/820127.820173. S2CID 14051647. Archived from the original on 2012-12-13. <a href="http://penguin.ewu.edu/~trolfe/DSWpaper/" target="_blank">http://penguin.ewu.edu/~trolfe/DSWpaper/</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Drozdek, Adam (1996). Data Structures and Algorithms in C++. PWS Publishing Co. pp. 173–175. ISBN 0-534-94974-6. <a href="0-534-94974-6" target="_blank">0-534-94974-6</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Stout, Quentin F.; Warren, Bette L. (September 1986). "Tree rebalancing in optimal space and time" (PDF). Communications of the ACM. 29 (9): 902–908. doi:10.1145/6592.6599. hdl:2027.42/7801. S2CID 18599490. <a href="http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf" target="_blank">http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">This version does not produce perfectly balanced nodes; Stout and Warren present a modification that does, in which the first call to compress is replaced by a different subroutine. <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">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. <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

Day–Stout–Warren algorithm open-in-new

Day–Stout–Warren algorithm