缠藤的二叉搜索树

摘要：

引入了一个基于节点的,利用二叉搜索树以及有序链表特性的数据结构.节点之间的链接分为两种类型,其中一种用来构造一个链表的结构,另一种用来构造一个二叉搜索树的结构.这种字典类的数据结构提供了O(logn)时间的以键为基础的搜索运算,以及当增加和消除元素时的维护过程.另外,此数据结构也以O(logn)的时问来支持容错的搜索,并使得从某个特定元素开始的连续搜索非常有效.双向链表结构和单向链表结构在文章中都分别得到了考虑.

关键词：二叉搜索树、字典、有序链表

所属期刊栏目：35

分类号：O157;TP311.12(代数、数论、组合理论)

资助基金：中国国家自然科学基金项目11071280;This work was partially supported by the National Natural Science Foundation of China under Grant No.11071280

在线出版日期：2013-11-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1-8