Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Day–Stout–Warren_algorithm> ?p ?o }
Showing triples 1 to 39 of
39
with 100 triples per page.
- Day–Stout–Warren_algorithm 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.\"".
- Day–Stout–Warren_algorithm wikiPageID "1699060".
- Day–Stout–Warren_algorithm wikiPageLength "5212".
- Day–Stout–Warren_algorithm wikiPageOutDegree "14".
- Day–Stout–Warren_algorithm wikiPageRevisionID "706627502".
- Day–Stout–Warren_algorithm wikiPageWikiLink Amortized_analysis.
- Day–Stout–Warren_algorithm wikiPageWikiLink Big_O_notation.
- Day–Stout–Warren_algorithm wikiPageWikiLink Binary_search_tree.
- Day–Stout–Warren_algorithm wikiPageWikiLink Category:Search_trees.
- Day–Stout–Warren_algorithm wikiPageWikiLink Communications_of_the_ACM.
- Day–Stout–Warren_algorithm wikiPageWikiLink DSPACE.
- Day–Stout–Warren_algorithm wikiPageWikiLink In-place_algorithm.
- Day–Stout–Warren_algorithm wikiPageWikiLink Linked_list.
- Day–Stout–Warren_algorithm wikiPageWikiLink Pseudocode.
- Day–Stout–Warren_algorithm wikiPageWikiLink Self-balancing_binary_search_tree.
- Day–Stout–Warren_algorithm wikiPageWikiLink Subroutine.
- Day–Stout–Warren_algorithm wikiPageWikiLink Threaded_binary_tree.
- Day–Stout–Warren_algorithm wikiPageWikiLink Tree_rotation.
- Day–Stout–Warren_algorithm wikiPageWikiLink Tree_traversal.
- Day–Stout–Warren_algorithm wikiPageWikiLinkText "Day–Stout–Warren algorithm".
- Day–Stout–Warren_algorithm wikiPageUsesTemplate Template:Datastructure-stub.
- Day–Stout–Warren_algorithm wikiPageUsesTemplate Template:Reflist.
- Day–Stout–Warren_algorithm subject Category:Search_trees.
- Day–Stout–Warren_algorithm hypernym Method.
- Day–Stout–Warren_algorithm type Software.
- Day–Stout–Warren_algorithm type Algorithm.
- Day–Stout–Warren_algorithm type Redirect.
- Day–Stout–Warren_algorithm type Structure.
- Day–Stout–Warren_algorithm type Technique.
- Day–Stout–Warren_algorithm comment "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.".
- Day–Stout–Warren_algorithm label "Day–Stout–Warren algorithm".
- Day–Stout–Warren_algorithm sameAs Q5243649.
- Day–Stout–Warren_algorithm sameAs الگوریتم_دی-استوت-وارن.
- Day–Stout–Warren_algorithm sameAs Algorytm_DSW.
- Day–Stout–Warren_algorithm sameAs m.05pbjt.
- Day–Stout–Warren_algorithm sameAs Dej-Stout-Varen_algoritam.
- Day–Stout–Warren_algorithm sameAs Q5243649.
- Day–Stout–Warren_algorithm wasDerivedFrom Day–Stout–Warren_algorithm?oldid=706627502.
- Day–Stout–Warren_algorithm isPrimaryTopicOf Day–Stout–Warren_algorithm.