红黑树算法研究综述

Overviews on Reseach of Red-Black Tree Algorithm

针对内存数据管理中常用的红黑树算法开展研究,在介绍红黑树定义及特性的基础上,对比红黑树与二叉平衡树在插入删除及查找数据时的时间复杂度,对红黑树在各类节点颜色情况下插入删除操作进行了分类。同时,文章在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.