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, based on work done by Colin Day in 1976.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Day–Stout–Warren algorithm (en)
- DSWアルゴリズム (ja)
- Algorytm DSW (pl)
|
| rdfs:comment
| - Algorytm DSW – algorytm równoważący binarne drzewa poszukiwań (BST) tak, że wysokość drzewa jest rzędu (ściśle: ), gdzie to liczba węzłów drzewa. Algorytm działa w czasie proporcjonalnym do liczby węzłów Został stworzony przez Colina Daya (1976), a następnie poprawiony przez Quentina F. Stouta oraz Bette L. Warren (1986). Nazwa to skrótowiec, utworzony od pierwszych liter nazwisk twórców. (pl)
- 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, based on work done by Colin Day in 1976. (en)
- DSWアルゴリズム (Day-Stout-Warren algorithm) は、効率的に二分探索木を平衡化する手法である。つまり、ノード数を n として、その高さを O(log n) に圧縮する。操作のたびに平衡化を行う平衡二分探索木とは異なり、平衡化のコストは累次の操作によって償却される。このアルゴリズムは、1976 年の Colin Day の研究に基づき、1986 年の 論文において Quentin F. Stout と Bette Warren によって設計された。 このアルゴリズムは、線形時間 (O(n)) のIn-placeアルゴリズムである。Day による元々のアルゴリズムでは、可能な限り高さの低い木が生成される。これによって最も下を除くすべての階層は完全に満たされた状態となる。この操作は2つの段階に分けられ、まず（の）木のノードのポインタを利用し、木を通りがけ順 (in-order) に走査して連結リストに変換する。そして一連の左回転操作が第2段階となる。 (ja)
|
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - 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, 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. 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 forms the second phase.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 constant space to operate. Like the original algorithm, Day–Stout–Warren operates in two phases, the first entirely new, the second a modification of Day's rotation phase. A 2002 article by Timothy J. Rolfe brought attention back to the DSW algorithm; the naming is from the section title "6.7.1: The DSW Algorithm" in Adam Drozdek's textbook. 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." (en)
- Algorytm DSW – algorytm równoważący binarne drzewa poszukiwań (BST) tak, że wysokość drzewa jest rzędu (ściśle: ), gdzie to liczba węzłów drzewa. Algorytm działa w czasie proporcjonalnym do liczby węzłów Został stworzony przez Colina Daya (1976), a następnie poprawiony przez Quentina F. Stouta oraz Bette L. Warren (1986). Nazwa to skrótowiec, utworzony od pierwszych liter nazwisk twórców. (pl)
- DSWアルゴリズム (Day-Stout-Warren algorithm) は、効率的に二分探索木を平衡化する手法である。つまり、ノード数を n として、その高さを O(log n) に圧縮する。操作のたびに平衡化を行う平衡二分探索木とは異なり、平衡化のコストは累次の操作によって償却される。このアルゴリズムは、1976 年の Colin Day の研究に基づき、1986 年の 論文において Quentin F. Stout と Bette Warren によって設計された。 このアルゴリズムは、線形時間 (O(n)) のIn-placeアルゴリズムである。Day による元々のアルゴリズムでは、可能な限り高さの低い木が生成される。これによって最も下を除くすべての階層は完全に満たされた状態となる。この操作は2つの段階に分けられ、まず（の）木のノードのポインタを利用し、木を通りがけ順 (in-order) に走査して連結リストに変換する。そして一連の左回転操作が第2段階となる。 Stout-Warren による修正では、完全二分木、すなわち最も下の階層が左から右へ連続的に満たされた木が生成される。この変換は、それ以上の挿入を行わないことが分かっているときに有用である。木が糸付き木である必要はなく、操作も定数空間で行える。元々のアルゴリズムと同様に、Day-Stout-Warren は2段階で動作する。1段階目はまったく新しいものであり、2段階目は Day による回転の段階を修正したものである。 Timothy J. Rolfe による 2002 年の論文が、DSW アルゴリズムが再び注目されるきっかけとなった。その名前は、Adam Drozdek の教科書におけるセクション名 "6.7.1: The DSW Algorithm" に由来する。Rolfe は、このアルゴリズムが適した場面を2つ挙げている。すなわち、「処理の開始時に二分探索木の全体を生成し、残りの処理はノードの探索のみである状況」、また「二分探索木における回転操作に最初に触れられることから、二分探索木から自己調整木 (self-adjusting tree) に進むデータ構造の学習過程」である。 (ja)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)