红黑树算法研究综述  

Overviews on Reseach of Red-Black Tree Algorithm

作　　者：马博韬 孙鹏[1] 朱小勇[1] MA Botao;SUN Peng;ZHU Xiaoyong(National Network New Media Engineering Research Center,Chinese Academy of Sciences,Beijing,100190,China;University of Chinese Academy of Science,Beijing,100490,China)

机构地区：[1]中国科学院声学研究所国家网络新媒体工程技术研究中心,北京00190 [2]中国科学院大学,北京100049

出　　处：《网络新媒体技术》2018年第4期56-62,共7页Network New Media Technology

摘　　要：针对内存数据管理中常用的红黑树算法开展研究,在介绍红黑树定义及特性的基础上,对比红黑树与二叉平衡树在插入删除及查找数据时的时间复杂度,对红黑树在各类节点颜色情况下插入删除操作进行了分类。同时,文章在Linux非实时任务调度、虚拟内存等应用场景下介绍红黑树的使用,最后基于红黑树存在的潜在不足,介绍了相关研究人员在特定场景下对其做出的改进优化。This paper studies the red-black tree algorithm which commonly used in memory data management. On the basis of introducing the definition and characteristics of red-black tree,it compares the time complexity of the red-black tree and binary balance tree when inserting and searching the data,and classifies the insertion and deletion operation of red-black tree under the circumstances of different nodes color. At the same time,the paper introduces the use of red-black tree in Linux non real-time task scheduling,virtual memory and other applications. Finally,based on the potential shortage of red-black tree,this paper introduces the improvement and optimization in the specific scene.

关 键 词：红黑树 AVL树 插入平衡 删除平衡 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]