The Best Binary Sort Tree and the Implementation of Operations on It

摘要：

In this paper, the rationality of the concept of the balanced binary tree and the balanced binary sort tree which is in general use up to now is called in question, and the new concept of strict balance factor, strict balanced binary tree and strict balanced binary sort tree is presented. The recursive algorithm for constructing the strict balanced binary sort tree and the process of strict balancing when inserting and deleting elements in the binary sort tree are simpler and more natural than traditional Adelson-Velskii & Landis algorithm of dynamic construction of the balanced binary sort tree. The conclusions of this paper present that the strict balanced binary sort tree is the best binary sort tree for search.

关键词： strict balance factor (sbf) strict balanced binary tree(sbbt) strict balanced binary sort tree (sbbst), balance factor(bf),balanced binary tree (bbt), balanced binary sort tree (bst)

作者: CEN Gang ZHOU Bingsheng

作者单位: School of Information and Electronic Engineering,Zhejiang University of Science and Technology Hangzhou, Zhejiang 310023, China

会议类型: 国际会议

会议名称: 第二届国际计算机新科技与教育学术会议(Proceedings of the Second International Conference on Computer Science & Education ICCSE2007)

会议地点: 武汉

会议语种:英文

页码: 264-267

在线出版日期: 2007-07-25（万方平台首次上网日期，不代表论文的发表时间）