该文档时一篇关于二叉优化搜索的一篇文章
Acta Informatica 1, 14-25 (1971) 9 by Springer-Verlag 1971
Optimum Binary Search Trees* D. E. KNUTH Received June 22, t97o One of the popular methods for retrieving information by its" n a m e" is to store the names in a binary tree. To find if a given name is in the tree, we compare it to the name at the root, and four cases arise: 1. There is no root (the binary tree is empty): The given name is not in the tree, and the search terminates unsuccess/ully. 2. The given name matches the name at the root: The search terminates
suecess/ully. 3. The given name is less than the name at the root: The search continues by examining the left subtree of the root in the same way. 4. The given name is greater than the name at the root: The search continues by examining the right subtree of the root in the same way. Special cases of this method are the binary search and its variants (tmcentered binary search; Fibonacci search) and the search-sort scheme of Wheeler-Berners Lee-Booth-Hibbard-Windley, et al. (see[t, 3, 7, t01). When all names in the tree are equally probable, it is not difficult to see that a best possible binary tree from the standpoint of average search time is one with minimum path length, namely the complete binary tree (see[9, pp. 400-40t]). This is the tree which is implicitly present in one of the variants of the binary search method. But when some names are known to be much more likely to occur than others, the best possible binary tree will not necessarily be balanced. For example, consider the following words and frequencies, a an and by effects for from high in of on the to with 32 7 69 13 6 15 t0 8 64 t 42 22 79 18 9
~, The research reported here was supported by IBM Corporation.

BINARY SEARCH TREES 暂无评价 49页 免费 Random suffix search tre... 暂无评价 44页 免费 Optimum binary search tr... 12页 5财富值 ABSTRACT Exploring ...
Optimum binary search tr... 12页 5财富值 Binary Trees 9页 免费 8_binary_trees 暂无评价 13页 2财富值 ch05--Binary Trees 95页 1财富值 Limiting ...
Binary Search 8页 免费 Binary Search Tree 14页 4下载券 Binary Search Tree 35页 免费 Optimum binary search ... 12页 2下载券 Binary Search Tree 暂无...
BINARY SEARCH TREES 暂无评价 49页 免费 Optimum binary search tr... 12页 5财富值 Abstract Adaptive Search... 暂无评价 43页 免费 THE HEIGHT OF q-...
暂无评价 10页 免费 Concurrent Cache-Oblivio... 暂无评价 6页 免费 BINARY SEARCH TREES 暂无评价 49页 免费 Optimum binary search tr... 12页 5财富值...
BINARY SEARCH TREES 暂无评价 49页 免费 C++ Binary Search Tree 暂无评价 4页 免费 Optimum binary search tr... 12页 5财富值 binary search and list ...
Knuth, D.E., "Optimum Binary Search Trees", Acta Informatica, Vol 1, No 1, p14-25, 1971. n n Knuth, D.E., The Art of Computer Programming,...
BINARY SEARCH TREES Jose Prados Víctor Torres BINARY SEARCH TREES ? What is a Binary Search Tree? ? Binary Search Tree Property ? Basic operations ...
We consider the problem of maintaining a binary search tree (BST) that ... it achieves a cost that approaches the optimum up to a difference of δ...
Binary Trees 9页 免费 8_binary_trees 暂无评价 13页 2财富值 Optimum binary search tr... 12页 5财富值 BINARY SEARCH TREES 暂无评价 49页 免费 Binary...
热门文档