计算机工程与应用2017，Vol.53Issue(9)：63-71,102,10.DOI:10.3778/j.issn.1002-8331.1511-0274
一种新型有序数据结构:容量平衡三叉查找树
Capacity balanced trigeminal search tree—new data structure for storing ordered data
徐懿彬 1徐学荣2
作者信息
- 1. 福建省福州第八中学,福州 350004
- 2. 福建农林大学,福州 350002
- 折叠
摘要
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 bal-anced 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分类
信息技术与安全科学引用本文复制引用
徐懿彬,徐学荣..一种新型有序数据结构:容量平衡三叉查找树[J].计算机工程与应用,2017,53(9):63-71,102,10.
