Jump to content

Day–Stout–Warren algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Qwertyus (talk | contribs) at 18:52, 30 September 2014 (2002 isn't really recent, and apparently the algorithm was in a 1996 textbook, so the hiatus wasn't that long). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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. 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 F. Stout and Bette Warren in a 1986 CACM paper,[1] based on work done by Colin Day in 1976.[2]

The algorithm requires linear (O(n)) time and is 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) tree's nodes. A series of left-rotations formed the second phase.[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. This is a useful transformation to perform if it is known that no more inserts will be done.

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.[4] 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."

References

  1. ^ Stout, Quentin F.; Warren, Bette L. (1986). "Tree rebalancing in optimal space and time" (PDF). CACM. 29 (9).
  2. ^ Day, A. Colin (1976). "Balancing a Binary Tree". Comput. J. 19: 360–361.
  3. ^ a b Rolfe, Timothy J. (2002). "One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm". Inroads. 34 (4). ACM SIGCSE: 85–88.
  4. ^ Drozdek, Adam (1996). Data Structures and Algorithms in C++. PWS Publishing Co. pp. 173–175.



Stub icon

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Day–Stout–Warren_algorithm&oldid=627714412"