一种新型有序数据结构：容量平衡三叉查找树
来源：计算机工程与应用杂志2017年第9期北京时间：
作者：徐懿彬1，徐学荣2
单位：1.福建省福州第八中学，福州 3500042.福建农林大学，福州 350002
摘要：平衡二叉树是一种用于存储有序数据的经典结构，伴随大数据时代的到来，平衡二叉树调整率高的问题愈发影响其运用于并行计算。有鉴于此，提出一种平衡三叉树，这种三叉树的一个节点存储两个值，维护三棵子树。通过复杂度对比与模拟实验结果表明：（1）相较其他有序数据机构，平衡三叉树具有较低的最坏高度；（2）平衡三叉树可以轻易实施区间操作；（3）平衡三叉树不需要对结构进行经常性的调整，平均内部路径长度远远小于传统平衡二叉树算法，运行速度快，更适合于并发应用。
关键词：有序数据结构,平衡树,并行运算,三叉树
