This HTML5 document contains 21 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dct	http://purl.org/dc/terms/
yago-res	http://yago-knowledge.org/resource/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
n12	http://en.wikipedia.org/wiki/
dbp	http://dbpedia.org/property/
dbc	http://dbpedia.org/resource/Category:
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
gold	http://purl.org/linguistics/gold/
dbr	http://dbpedia.org/resource/

Statements

Subject Item

dbr:Optimal_binary_search_tree

rdf:type

dbo:Plant

rdfs:label

Optimal binary search tree

rdfs:comment

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic.

owl:sameAs

yago-res:Optimal_binary_search_tree freebase:m.0105pbnn

dbp:wikiPageUsesTemplate

dbt:Unsolved dbt:Reflist dbt:Data_structures dbt:CS-Trees dbt:Tmath dbt:Mvar dbt:Main

dct:subject

dbc:Search_trees dbc:Binary_trees

gold:hypernym

dbr:Tree

prov:wasDerivedFrom

n12:Optimal_binary_search_tree?oldid=1068814105&ns=0

dbo:wikiPageID

42382810

dbo:wikiPageLength

18220

dbo:wikiPageRevisionID

1068814105

dbo:abstract

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic. In the static optimality problem, the tree cannot be modified after it has been constructed. In this case, there exists some particular layout of the nodes of the tree which provides the smallest expected search time for the given access probabilities. Various algorithms exist to construct or approximate the statically optimal tree given the information on the access probabilities of the elements. In the dynamic optimality problem, the tree can be modified at any time, typically by permitting tree rotations. The tree is considered to have a cursor starting at the root which it can move or use to perform modifications. In this case, there exists some minimal-cost sequence of these operations which causes the cursor to visit every node in the target access sequence in order. The splay tree is conjectured to have a constant competitive ratio compared to the tree in all cases, though this has not yet been proven.

foaf:isPrimaryTopicOf

n12:Optimal_binary_search_tree