杨勇

摘要：红黑树是按照一定规则建立起来的平衡二叉查找树。为满足平衡条件，节点元素在插入和删除后，要进行颜色和位置的修正。修正过程相当复杂，给学习研究红黑树带来困难。通过在图元文件上画出红黑树，以图形方式，把插入和删除过程中的变化细节记录下来，使红黑树的操作可视化，从而给红黑树的理解和研究带来极大的便利。

关键词：红黑树;图元文件;平衡二叉树

中图分类号：TP311.11      文献标识码：A

文章编号：1009-3044（2021）35-0166-03

1 背景

二叉查找树（binary search tree）是一种重要的数据结构。其特点是，对于树中的每个节点，它的左子树所有节点值小于它，而右子树中所有节点值大于它。二叉树建立后，如果各节点子树的深度相差不多，则可以实现对节点数据的快速查找，平均运行时间能够达到O（logN）的时间复杂度。实际上，以上述规则建立起来的二叉查找树往往子树深度不能平衡。需要对树的节点位置进行调整，才能满足快速查找的要求。目前主要有两种方法能建立起近似平衡的二叉查找树，一种是AVL树，它保证树中每个节点左子树和右子树高度最多差1。另一种是红黑树（red black tree），它通过设定节点的颜色条件和数量，达到子树的近似平衡。红黑树的平衡程度比AVL树稍微低一点，数据查找时间复杂度相对要大，但是红黑树节点的插入和删除过程不涉及递归运算，比AVL树速度要快[1]。因此在软件工程实践中，红黑树得到了广泛的应用[2-5]，C++标准模板库中的容器类map，set以及Java JDK中的 treemap 等，都是采用红黑树结构实现的。……