| 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
| |
| dbo:wikiPageLength
|
- 18220 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |