红黑树|Red-Black tree

红黑树是一种自平衡二叉搜索树。树的每个节点都有一个额外的bit,用于标记节点的颜色(红色或黑色)。着色位确保树在插入和删除操作中保持平衡。

红黑树的平衡规则

如果插入二叉树的数值是有序的,二叉树的平衡性就会被打乱,基本跟链表差不多,时间复杂度达到O(N)。红黑树能有效反转这种情况,将树维持在相对平衡的状态,把时间复杂度降到O(logN)

注:N为树的节点数。

红黑树属性

红黑树能保持二叉树的相对平衡,源于它的三个属性:

1、根属性:红黑树的根是黑色。

2、红属性:红色节点的子节点为黑色。

3、黑属性:对于那些至少有一个空子节点的节点,从根节点到空子节点,这个路径上的黑色节点数量是相同。

因为红黑树是二叉搜索树,不改变树结构的操作,不会影响到红黑树的属性,所以,查找操作与二叉搜索树的查找是相同的。红黑树动态演示程序

插入操作

插入操作的目标是,将键值插入到树中,确保红黑树的属性不受影响。空树是一个特殊的情况,如果树为空,用一个包含键值的黑色节点替换它。确保根属性得到满足。如果树不为空,则执行以下操作:

1、使用BST插入算法向树中添加键值。

2、将包含值的节点涂成红色。

3、恢复红黑树属性(如有必要)。

BST插入算法总是添加一个叶节点。因为,处理的是一个非空的红黑树,所以,添加叶节点不会影响树的根属性。此外,添加红色叶节点不会影响树的黑色属性。

然而,添加一个红色的叶子节点,可能会影响树的红色属性,如果受到影响,则使用步骤3修复这种影响。在满足红色属性时,确保最终不会违反根属性或黑色属性。

对于非空树插入操作的第3步,需要做的事情取决于父节点的颜色。分为两种情况:

1、父节点是黑色,则新节点的添加不会导致红色属性受影响,无需处理。

2、父节点是红色,而新节点目前也是红色,则违反了红色属性。

处理这种双重红色,需要到考虑父节点的兄弟节点,这个节点可能存在,也可能为空。分以下两种情况:

1、父节点的兄弟节点为黑色或为空。

需要对父节点到根,这条路径上的节点进行重组,将他们按顺序排列。假如顺序为(A, B, C),让B成为A和C的父结点,B的颜色为黑色,A和C的颜色是红色。需要确保一旦完成重组,父节点和其兄弟节点的任何子树,都处于正确的位置。排序有四种可能性,每种可能性的重组方式如下所示:


父节点的兄弟节点为空,则有以下可能:

一旦完成重组,就处理了双重红色的情况(由以上图表可看出,重组不会让黑色属性受影响)。

2、父节点的兄弟节点为红色

这种情况需要调整节点颜色,如果影响了根属性,则不对根颜色做反转。

重新着色不会影响树的黑色属性:黑色节点数均不变,如果引发了上层的红色节点冲突。那么,就需要从上层节点的冲突处进行递归处理,而不是从新节点和父结点上处理双红色冲突。

时间复杂度

将键值插入到非空树中需要三个步骤。

1、执行BST 插入操作。BST 插入操作是O(树的高度),为O(log N),因为,红黑树是平衡树。

2、将新节点涂成红色。此步骤为O(1),因为,仅需要设置一个节点颜色字段的值。

3、调整所有违反的红黑属性。

重组为O(1),因为,它最多更改五个指向树节点的指针。一旦完成重组,就完成了插入算法,因此,在步骤3中最多进行1次重组。最坏情况,插入过程中完成的重组为O(1)。

重新着色期间更改节点的颜色为O(1)。可能需要处理,从新节点到根路径上的双红色情况。最坏情况,沿着新节点到根的整个路径修复双重红色。

最坏的情况,插入过程中完成的重新着色为O(log N)(一次重新着色的时间*完成的最大重新着色次数=O(1)*O(log N))。第三步(恢复红黑色属性)为O(log N),插入的总时间为O(log N)。

删除操作

删除操作与插入操作相似,但更复杂。

总结

平衡搜索树的高度总是O(log N)。这样做的结果是,在平衡搜索树中查找、插入和删除操作,最坏情况为O(log N)。相比之下,二叉搜索树的最坏情况高度为O(N),最坏情况下查找、插入和删除为O(N)。

红黑树是二叉搜索树,它在每个节点中存储一条额外的信息(节点的颜色),并满足三个属性。这些属性处理节点的着色方式(根属性、红色属性),和从根节点到空子节点路径上的黑节点数量(黑色属性)。但在添加或删除节点之后,恢复这些属性的算法让在树保持平衡。

查找方法对于二叉搜索树和红黑树是相同的,但红黑树插入和删除方法更复杂。插入方法最初执行与二叉搜索树相同的插入算法,然后,执行必要的步骤,通过重组和重新着色恢复红黑树属性。红黑树的delete方法比insert方法更复杂。