DSW algorithm

DSW algorithm

The DSW algorithm, or in full Day/Stout/Warren 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 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."

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • DSW — may refer to: DSW, the SAME code for a Dust Storm Warning Deep South Wrestling, a professional wrestling promotion that was a developmental territory of World Wrestling Entertainment Diving Salvage Warfare Specialist, a United States Navy… …   Wikipedia

  • Self-balancing binary search tree — In computer science, a self balancing binary search tree or height balanced binary search tree is a binary search tree that attempts to keep its height , or the number of levels of nodes beneath the root, as small as possible at all times,… …   Wikipedia

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • T-tree — In computer science a T tree is a type of binary tree data structure that is used by main memory databases, such as DataBlitz, e X treme DB, MySQL Cluster, Oracle TimesTen and [http://www.kairosdbms.com Kairos] [http://www.emware.co.kr… …   Wikipedia

  • Суффиксное дерево — Суффиксное дерево  бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w|  длина строки w. Содержание 1 Основные определения и описание структуры …   Википедия

  • Красно-чёрное дерево — Тип дерево поиска Изобретено в 1972 году Изобретено Рудольф Байер Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(log n) Вставка O(log n) O(log n) Удаление O(log n) O(log n) Красно чёрное… …   Википедия

  • Октодерево — Слева: Рекурсивное разделение куба на октанты. Справа: Соответствующее октодерево …   Википедия

  • Дерево квадрантов — Разбитая с помощью дерева квадрантов плоскость Дерево квадрантов (также квадродерево, 4 дерево, англ. quadtree) дере …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”