DSW algorithm
Encyclopedia
The DSW algorithm, or in full Day/Stout/Warren algorithm, is a method for efficiently balancing binary search tree
s — 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 their 1986 paper Tree Rebalancing in Optimal Time and Space, based on work done by Colin Day in 1976.
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. 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 has recently brought attention back to the DSW algorithm after a long hiatus; the naming is from the section title "6.7.1: The DSW Algorithm" in Adam Drozdek's Data Structures and Algorithms in C++ (PWS Publishing Co., 1996) pp. 173-175. 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."
Binary search tree
In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...
s — 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
Self-balancing binary search tree
In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
, it does not do this incrementally during each operation, but periodically, so that its cost can be amortized
Amortized analysis
In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...
over many operations. The algorithm was designed by Quentin F. 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 (O(n)) time and is in-place
In-place algorithm
In computer science, an in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes...
. 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. 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 has recently brought attention back to the DSW algorithm after a long hiatus; the naming is from the section title "6.7.1: The DSW Algorithm" in Adam Drozdek's Data Structures and Algorithms in C++ (PWS Publishing Co., 1996) pp. 173-175. 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."
External links
- An explanation and some experiments by Timothy J. Rolfe
- The original paper by Stout and Warren
- Prof. Quentin Stout's homepage at University of Michigan