About: Interleave lower bound

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In the theory of optimal binary search trees, the interleave lower bound is a lower bound on the number of operations required by a Binary Search Tree (BST) to execute a given sequence of accesses. Several variants of this lower bound have been proven. This article is based on a variation of the first Wilber's bound. This lower bound is used in the design and analysis of Tango tree. Furthermore, this lower bound can be rephrased and proven geometrically, Geometry of binary search trees.

Property Value
dbo:abstract
  • In the theory of optimal binary search trees, the interleave lower bound is a lower bound on the number of operations required by a Binary Search Tree (BST) to execute a given sequence of accesses. Several variants of this lower bound have been proven. This article is based on a variation of the first Wilber's bound. This lower bound is used in the design and analysis of Tango tree. Furthermore, this lower bound can be rephrased and proven geometrically, Geometry of binary search trees. (en)
dbo:wikiPageID
  • 44942451 (xsd:integer)
dbo:wikiPageLength
  • 15481 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1102893861 (xsd:integer)
dbo:wikiPageWikiLink
dbp:mathStatement
  • Given a BST at time , , any node in can be only a transition for at most one node in . (en)
  • Given a node . Suppose is the transition point of at a time . If an access algorithm for a BST does not touch in for , then the transition point of will remain in for . (en)
  • The transition point of a node in at a time exists and it is unique. (en)
dbp:name
  • Lemma 1 (en)
  • Lemma 2 (en)
  • Lemma 3 (en)
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In the theory of optimal binary search trees, the interleave lower bound is a lower bound on the number of operations required by a Binary Search Tree (BST) to execute a given sequence of accesses. Several variants of this lower bound have been proven. This article is based on a variation of the first Wilber's bound. This lower bound is used in the design and analysis of Tango tree. Furthermore, this lower bound can be rephrased and proven geometrically, Geometry of binary search trees. (en)
rdfs:label
  • Interleave lower bound (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License