红黑树（一）性质及插入操作

Posted on 2021-10-25 Edited on 2021-12-14 Views:

为什么要引入红黑树？

因为AVL树的定义太过严格，每次插入或删除都需要维护整体的平衡，产生的额外代价太大。

于是我们想，能不能适当放宽标准，使得二叉树既不至于退化成链表，又不会在维持平衡上产生太多额外开销。

聪明的人们想到了红黑树。

定义及性质

红黑树是一种自平衡二叉查找树。

首先，它是一种二叉查找树（或二叉搜索树，Binary Search Tree），也就是说，对于每一个节点来说，左子树的所有元素都小于该节点的元素，右子树的所有元素都不小于该节点的元素。其次，它是自平衡的，但并不如AVL树那么严格，我们接下来看一下它的性质是如何来保证这一点的。

红黑树有以下性质：

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色结点的两个子结点一定都是黑色。
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

那么这些性质，是怎么保证自平衡的呢？性质4保证了没有连续的两个红色节点，性质5保证了该树所有黑色节点构成的树是完美平衡的。以下面这棵树为例。

它的所有黑色节点构成的树如下（为了方便，NIL节点就用一个圈表示）。

显然，黑色节点构成的树是完美平衡的。从根结点到每个NIL节点的路径长度都是3。那么把红色节点考虑进来，这棵树最“歪”的情况是什么？就是左边数值为3的这个节点保持不动，然后在右边加尽可能多的红色节点。然而，考虑到性质4的约束，在某一条路上能添加的红色节点数量是不超过这条路上黑色节点数量的两倍的。对于这棵树来说，从根节点到NIL节点，一共有3个黑色节点，那么在这条路上我们能添加的红色节点只有2个（每两个黑色节点之间插入一个红色节点）。事实上，这棵树现在就是它能达到的最不平衡的状态（仅从高度而言）。

经过上述分析，我们可以知道，因为性质4和性质5的约束，没有一条从根结点到NIL节点的路径会比其他路径长两倍，所以红黑树是相对平衡的。

插入操作

在插入某节点时，如果破坏了我们约定的性质，那么就需要对各种节点进行调整。对节点的,操作大体分为两类，旋转和变色，其中旋转又分为左旋和右旋。旋转操作如下图：

同样的，以这棵树为例，我们看一下整个插入节点的流程是怎么样的。

插入节点颜色的确定

首先，考虑一下我们插入的这个节点，它应该是红色还是黑色？如果把插入的当前节点当作黑色，那么它就一定会威胁到之前提到的性质5，比如我们在上面那棵树插入数值为2的节点。这个时候，该树所有黑色节点构成的树就变成了：

这样就违反了性质5了。这也就意味着，如果插入黑色节点，调整是必须的。

然而如果我们插入的是红色结点的话，在它的父亲是黑色节点的情况下，我们是不需要对树进行调整的。其实就相当于在一个黑色节点和NIL节点之间插入了一个红色节点而已，按照之前的分析，这确实是允许的。即如果插入红色节点，有可能不需要调整。比如在这棵树里插入2，

然而，当插入节点的父亲节点是红色的时候，就威胁到了性质4，即红色节点的子节点必须是黑色。这个时候我们要怎么调整呢？

调整的思想

全程记住一个思想：只利用旋转和变色的操作，将红色的节点移到根节点上，再把根节点变成黑色。因为根节点是没有父亲节点的，或者说我们默认根节点的父亲节点是黑色。所以对根节点进行变色，是不会威胁到红黑树的性质的。

接着我们具体来看一下，要怎么样完成这种调整。对于上面提到的树，我们现在尝试插入数值为9的结点。按照之前的讨论，它的颜色是红色，我们用\(cur\)来表示当前关注的节点。那么这一步产生的树如下图：

显然，在\(cur\)节点处，红黑树的性质被威胁到了，因为\(cur\)的父亲的颜色是红色。在这个时候，我们去查叔结点的颜色，用\(y\)表示。此时\(y\)为节点11，是红色。于是我们把\(cur\)的父亲和\(y\)都变为黑色，并且把\(cur\)的祖父变为红色。这样做的意义其实就是把“黑色”往下移动，“红色”往上移动，同时又保证了从任意节点到NIL节点的路径中黑色节点数目保持不变。这一步产生的树如下：

此时我们需要关注的节点（即\(cur\)）就从一开始插入的9，变为现在违反红黑树性质的10了。

这个时候\(cur\)的叔节点（节点3）为黑色，如果我们按照上面的方法贸然变色，那就会违反叔节点那边的性质5了，这不是相当于扩大杀伤范围了吗，显然是不可取的。到目前为止，这棵树的性质5依然是得到满足的，即黑色路径相等（为了偷懒就这样写了）。如果只改变\(cur\)或者只改变\(cur\)父亲的颜色，那这个性质就不满足了。宏观上来讲的话，就是右边已经多了一个节点，不管是什么颜色，都违反了性质。换种说法就是，现在这棵树已经不平衡了。平衡的问题就要用平衡的方法解决。把它看作AVL树，简化成如下形式。