如何深入理解并C语言实现红黑树？

本文共计6042个文字，预计阅读时间需要25分钟。

介绍+红黑树是一种特殊的平衡二叉树（AVL），在极端情况下，基本动态集合操作的时间复杂度为O(logn）。因此，被广泛应用于企业级开发中。+红黑树的性质+在一棵红黑树中，“

介绍

　　红黑树是一种特殊的平衡二叉树（AVL），可以保证在最坏的情况下，基本动态集合操作的时间复杂度为O(logn)。因此，被广泛应用于企业级的开发中。

红黑树的性质

　　在一棵红黑树中，其每个结点上增加了一个存储位（属性color）来表示结点的颜色，且颜色只能是red or black。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。

　　树中每个结点包含5个属性：color、val、lchild、rchild和p（可选）。如果一个结点没有子结点或父结点，则该结点相应指针属性的值为NIL。我们可以把这些NIL视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。

　　一棵红黑树是满足下面红黑性质的二叉搜索树：

• 每个结点或是红色的，或是黑色的。
• 根结点是黑色的。
• 每个叶结点（NIL）是黑色的。
• 如果一个结点是红色的，则它的两个子结点都是黑色的。
• 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

　　为了便于处理红黑树代码中的边界条件，使用一个哨兵来代表NIL。对于一棵红黑树tree，哨兵NIL是与一个与树中普通结点有相同属性的对象。它的color属性为black，其他属性可以为任意值。