【数据结构】红黑树

发布网友发布时间：2022-11-21 00:41

共1个回答

热心网友时间：2023-08-11 21:05

红黑树是一个要求不那么严格的平衡二叉树搜索树（平衡二叉搜索树/AVL树=平衡二叉树+二叉搜索树）
【平衡二叉树要求左右子树高度差值<=1，红黑树放宽了这个要求，只要求任意路径的长度只差不会超过2倍即可。更准确的说是任意路径上的的黑色节点数相同即可】

红黑树可用于数据查找，因为其“相对”平衡，所以其查找效率略低于平衡二叉搜索树，但是也非常高效。

平衡二叉树的要求过于严格（左右子树高度差值<=1），导致几乎每一次插入/删除节点都会破坏平衡二叉树的结构，需要将其重新调整为平衡二叉树。
显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣。而红黑树因为不是严格的平衡，所以可以避免这个问题，同时红黑树又是一个“相对”平衡的二叉搜索树，所以其查找性能也很好。

1、每个节点都有颜色（红或黑）
2、根节点是黑色的
3、叶节点时黑色的（注意：叶节点是空节点，有值的节点都不是叶结点）
4、没有两个相邻的红色节点（或者说红色节点的子节点一定是黑色节点）
5、从根节点到叶结点的每条路径包含的黑色节点相同（又叫：黑节点平衡）

与二叉搜索树查找数据的过程一致

（若插入数据后破坏了红黑树的性质，则需要对红黑树进行“再平衡”，使其满足红黑树的性质。并且新插入的节点最多只会破坏5条性质中的1条）
插入数据分为了3种情况
1、插入的节点，其没有父节点
2、插入的节点，其父节点是黑色节点
3、插入的节点，其父节点是红色节点

第一种情况：插入的节点没有父节点，说明插入的节点是根节点，此时直接将节点的颜色改为黑色即可

第二种情况：插入的节点，其父节点是黑色节点，此时不需要采取措施。新插入的节点并没有破坏红黑树的性质

第三种情况：插入的节点，其父节点是红色节点。如图

可以看到21和22同为红色，破坏了“没有两个相邻的红色节点”性质，需要进行再平衡操作。

分为以下情况（共同前提：插入节点的父节点是红色）：
1、插入节点的父节点的兄弟节点（即插入节点的叔叔节点，就是上图中的27节点）是红色
2、插入节点的父节点的兄弟节点是黑色

第一步：将其父节点颜色变为黑色
因为其父节点颜色变成了黑色，所以包含其父节点的这条路径多了一个黑色节点。破坏了“从根节点到叶结点的每条路径包含的黑色节点相同”性质，如上面的13,17,25，22（变成了黑色）,21路径

第二步：看其叔叔的颜色：

第一种情况：其叔叔节点为红色（其父节点为红色的前提下）
步骤：
1、把叔叔节点变成黑色
2、把其祖父节点（父节点的父节点）变成红色。若其祖父节点为根节点，则不变色
3、把祖父节点当做新插入的节点，重复1,2,3步骤直到其祖父节点为根节点

第二种情况：其叔叔节点为黑色（其父节点为红色的前提下）
这种情况下又分为两种情况：
1、新插入的子节点是父节点的左子节点
2、新插入的子节点是父节点的右子节点

第一种情况：新插入的子节点是父节点的左子节点（其叔叔节点为黑色，并且其父节点为红色的前提下）
步骤：（先变色，在右旋）

1、将其父节点变为黑色
2、将其祖父节点变为红色（其父节点是红色，则其祖父节点必为黑色）
3、以其父节点为支点，进行右旋操作（如何右旋？百度上有很形象的动画演示）

第二种情况：新插入的子节点是父节点的右子节点（其叔叔节点为黑色，并且其父节点为红色的前提下）
步骤：（先左旋将其变为情况一，在按情况一的操作来进行）

以新插入的节点为支点，进行左旋操作，变为情况一，此时将插入节点的父节点（上图的P节点）当做新插入的节点来进行情况一步骤下的：变色，右旋操作

下面我们开始讨论删除操作（下面的叶子节点都是指非NULL的叶子节点）：

A.删除的是叶子节点且该叶子节点是红色的 ---> 无需修复，因为它不会破坏红黑树的5个特性

B.删除的是叶子节点且该叶子节点是黑色的 ---> 很明显会破坏特性5，需要修复。

C.删除的节点（为了便于叙述我们将其称为P）下面有一个子节点 S，对于这种情况我们通过将P和S的值交换的方式，巧妙的将删除P变为删除S，S是叶子节点，这样C这种情况就会转换为A, B这两种情况：

C1:P为黑色，S为红色 ---> 对应 A 这种情况

C2:P为黑色或红色，S为黑色 --- > 对应 B 这种情况

**D. **删除的节点有两个子节点，对于这种情况，我们通过将P和它的后继节点N的值交换的方式，将删除节点P转换为删除后继节点N，而后继节点只可能是以下两种情况：

D1:N是叶子节点 --- > 对应情况 A 或 B

D2:N有一个子节点 ---- > 对应情况 C

所以通过上面的分析我们发现，红黑树节点删除后的修复操作都可以转换为 A 或 B这两种情况，而A不需要修复，所以我们只需要研究B这种情况如何修复就行了。

下面我们讨论如何修复B中情况：(若没有兄弟节点，则其兄弟节点是null节点，根据红黑树的性质，null节点为黑色)