一种基于红黑树的快速查找列表结构

A List Structure Capable of Fast Searching Based on Red-Black Tree

设计并实现了一种基于红黑树的列表结构.列表中数据存储在红黑树节点中,红黑树的高效查找性能使列表的查找时间复杂度为O(logn).实验表明,其查找效率比遍历查找快2个数量级以上,与二分查找相当.该列表结构适合于各种频繁添加、删除、查找的应用.

A list structure is designed and implemented based on Red - Black Tree. The list data are stored in nodes of Red - Black Tree. The high performance of effectively searching Red-Black Tree makes the time complexity of searching the list structure become O （logn）. The experiment shows that the efficiency of searching the list structure is above 2 numerical grades faster than that of searching by going all over lists, and as fast as that of binary searching. The list structure is fit for all sorts of applications of frequently adding, removing and searching data.