一种新型有序数据结构：容量平衡三叉查找树

doi:10.3778/j.issn.1002-8331.1511-0274

计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (9): 63-71.DOI: 10.3778/j.issn.1002-8331.1511-0274

一种新型有序数据结构：容量平衡三叉查找树

徐懿彬1，徐学荣2

1.福建省福州第八中学，福州 350004

2.福建农林大学，福州 350002

出版日期:2017-05-01 发布日期:2017-05-15

Capacity balanced trigeminal search tree—new data structure for storing ordered data

XU Yibin1, XU Xuerong2

1.Fuzhou No.8 Secondary School, Fuzhou 350004，China

2.Fujian Agriculture and Forestry University, Fuzhou 350002, China

Online:2017-05-01 Published:2017-05-15

摘要/Abstract

摘要： 平衡二叉树是一种用于存储有序数据的经典结构，伴随大数据时代的到来，平衡二叉树调整率高的问题愈发影响其运用于并行计算。有鉴于此，提出一种平衡三叉树，这种三叉树的一个节点存储两个值，维护三棵子树。通过复杂度对比与模拟实验结果表明：（1）相较其他有序数据机构，平衡三叉树具有较低的最坏高度；（2）平衡三叉树可以轻易实施区间操作；（3）平衡三叉树不需要对结构进行经常性的调整，平均内部路径长度远远小于传统平衡二叉树算法，运行速度快，更适合于并发应用。

关键词: 有序数据结构, 平衡树, 并行运算, 三叉树

Abstract: Balanced binary search tree is a typical structure for storing ordered data. With the coming of big data, high adjusting rate is incrementally affecting balanced binary search tree to be utilized in concurrent computation negatively. In order to resolve this drawback, this paper presents a type of balanced trigeminal search tree named Capacity Balanced Trigeminal search Tree（CBTT）, which stores two keys in each node and owns three sub-trees. Through complexity comparison and simulation experiment, the results show that: （1）compared to other ordered data structure, the worst height of CBTT is much lower; （2）range trading can be easily implemented by CBTT; （3）structure is stable so that few rebalanced operation ensues while inserting or deleting, and average internal path length is far shorter than typical balanced binary search tree. Owing to these advantages, CBTT runs fast and becomes more suitable for concurrent calculating.

Key words: ordered data structure, balanced tree, concurrent computing, trigeminal search tree

徐懿彬1，徐学荣2. 一种新型有序数据结构：容量平衡三叉查找树[J]. 计算机工程与应用, 2017, 53(9): 63-71.

XU Yibin1, XU Xuerong2. Capacity balanced trigeminal search tree—new data structure for storing ordered data[J]. Computer Engineering and Applications, 2017, 53(9): 63-71.

[1]	陈海红1，李军义2. 新的基于身份认证的群密钥协商协议[J]. 计算机工程与应用, 2017, 53(21): 103-109.
[2]	张龙翔. 三叉树结构下的群认证密钥协商协议[J]. 计算机工程与应用, 2013, 49(24): 83-87.
[3]	殷安生. 基于平衡树的应用层多播树构建算法[J]. 计算机工程与应用, 2011, 47(20): 99-101.
[4]	袁军良，熊伟清，江宝钏. 混合二元蚁群算法求解集装箱装载问题[J]. 计算机工程与应用, 2010, 46(36): 222-225.
[5]	毛韶阳^1,2,李肯立². 一种基于密度的并行聚类算法[J]. 计算机工程与应用, 2007, 43(30): 157-161.

一种新型有序数据结构：容量平衡三叉查找树

Capacity balanced trigeminal search tree—new data structure for storing ordered data

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics