红黑树 - 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方法更复杂。