| 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. (en) 計算機科學中， 一個最佳二元搜尋樹（Optimal BST），有時也被叫做重量平衡二元樹， 是有可能在已知的一串序列中得到最短搜尋時間的一棵二元搜尋樹（或期望的搜尋時間）。 最佳化二元搜尋樹可分為兩種：靜態的和動態的。 靜態的最佳化問題中，在完全被創建好之前，這棵樹是不能被修改的。在這狀況中，在這棵樹中的每個節點都存在特定的設計，這些設計是依照每個節點被存取的機率去設計出會得到最短的搜尋時間。不同的演算法能依照每筆資料所給的存取機率去創建或逼近地做出一個靜態的最佳化樹。 動態的最佳化問題中，這棵樹可以在任何時間被修改，是允許執行樹旋轉的。 這棵樹有一個從樹的根開始的指標，他可以藉著移動並使用他去修改一棵樹。在這狀況裡，一定會有一連串序列是有著最小的花費，使得這個指標要去走訪整棵樹去找出這個序列。 伸展樹被推測和動態最佳化樹在任何的情況下都有一個常數比率存在，雖然這還沒有被證明出來。 (zh) |
| dbo:wikiPageID |
42382810 (xsd:integer) |
| dbo:wikiPageLength |
18220 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1068814105 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Robert_Tarjan dbr:Binary_search_tree dbr:Interleave_lower_bound dbc:Search_trees dbr:Geometry_of_binary_search_trees dbr:Edward_F._Moore dbr:Entropy_(information_theory) dbr:Optimal_substructure dbr:Tree_data_structure dbr:Computer_science dbr:John_Iacono dbr:Pointer_(computer_programming) dbr:Garsia–Wachs_algorithm dbr:Open_problem dbr:Daniel_Sleator dbr:Dynamic_programming dbr:Edgar_Gilbert dbr:Erik_Demaine dbr:Expected_value dbr:God's_algorithm dbc:Binary_trees dbr:Alan_Tucker dbr:Big_O_notation dbr:Donald_E._Knuth dbr:Splay_tree dbr:Greedy_algorithm dbr:Kurt_Mehlhorn dbr:Brute-force_search dbr:Optimization_problem dbr:Tree_rotation dbr:Tango_tree dbr:Arborally_satisfied dbr:Asymptotically_optimal dbr:Competitive_ratio |
| dbp:wikiPageUsesTemplate |
dbt:CS-Trees dbt:Main dbt:Mvar dbt:Reflist dbt:Tmath dbt:Data_structures dbt:Unsolved |
| dct:subject |
dbc:Search_trees dbc:Binary_trees |
| gold:hypernym |
dbr:Tree |
| rdf:type |
yago:WikicatBinaryTrees yago:LivingThing100004258 yago:Object100002684 yago:Organism100004475 yago:PhysicalEntity100001930 yago:Plant100017222 yago:WoodyPlant113103136 dbo:Plant yago:Tree113104059 yago:VascularPlant113083586 yago:Whole100003553 |
| rdfs:comment |
計算機科學中， 一個最佳二元搜尋樹（Optimal BST），有時也被叫做重量平衡二元樹， 是有可能在已知的一串序列中得到最短搜尋時間的一棵二元搜尋樹（或期望的搜尋時間）。 最佳化二元搜尋樹可分為兩種：靜態的和動態的。 靜態的最佳化問題中，在完全被創建好之前，這棵樹是不能被修改的。在這狀況中，在這棵樹中的每個節點都存在特定的設計，這些設計是依照每個節點被存取的機率去設計出會得到最短的搜尋時間。不同的演算法能依照每筆資料所給的存取機率去創建或逼近地做出一個靜態的最佳化樹。 動態的最佳化問題中，這棵樹可以在任何時間被修改，是允許執行樹旋轉的。 這棵樹有一個從樹的根開始的指標，他可以藉著移動並使用他去修改一棵樹。在這狀況裡，一定會有一連串序列是有著最小的花費，使得這個指標要去走訪整棵樹去找出這個序列。 伸展樹被推測和動態最佳化樹在任何的情況下都有一個常數比率存在，雖然這還沒有被證明出來。 (zh) 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. (en) |
| rdfs:label |
Optimal binary search tree (en) 最佳化二元搜尋樹 (zh) |
| owl:sameAs |
freebase:Optimal binary search tree yago-res:Optimal binary search tree wikidata:Optimal binary search tree dbpedia-fa:Optimal binary search tree dbpedia-zh:Optimal binary search tree https://global.dbpedia.org/id/gJM9 |
| prov:wasDerivedFrom |
wikipedia-en:Optimal_binary_search_tree?oldid=1068814105&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Optimal_binary_search_tree |
| is dbo:wikiPageRedirects of |
dbr:Optimum_binary_search_tree dbr:Dynamic_optimality dbr:Static_optimality |
| is dbo:wikiPageWikiLink of |
dbr:Binary_search_tree dbr:Binary_tree dbr:Interleave_lower_bound dbr:Geometry_of_binary_search_trees dbr:Optimum_binary_search_tree dbr:Key-independent_optimality dbr:Garsia–Wachs_algorithm dbr:Adriano_Garsia dbr:Hash_table dbr:Michelle_L._Wachs dbr:Tango_tree dbr:Dynamic_optimality dbr:Static_optimality |
| is foaf:primaryTopic of |
wikipedia-en:Optimal_binary_search_tree |