文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > Optimum binary search trees
侵权投诉

Optimum binary search trees

该文档时一篇关于二叉优化搜索的一篇文章

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.

Optimum binary search trees

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email