红黑树的原理（持续更新）

2019-10-29 本文已影响0人李白开水

红黑树的基本概念

红黑树（英语：Red–black tree）是一种自平衡二叉查找树。
维基百科红黑树：https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

红黑树的性质

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

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

下面是一个具体的红黑树的图例：

image.png

解释说明第五点：从13—8—1—6，不算13自己，该路径包含一个黑色节点。
13—8—11，不算13自己，该路径包含一个黑色节点。
13—17—15，不算13自己，该路径包含一个黑色节点。
13—17—25—22，不算13自己，该路径包含一个黑色节点。
13—17—25—27，不算13自己，该路径包含一个黑色节点。

红黑树的插入

插入的节点有黑色和红色两种，一般我们插入的都是红色节点，因为性质五，从任意节点到其每个叶子的所有简单路径都包含相同数目的黑色节点，所以插入一个黑色节点会使所有把这个插入的节点当作叶子节点的路径，包含的黑色节点数目+1，从而破坏了红黑树，最主要的原因是，不好调整。如果插入的是红色节点，如果出现了违反红黑树性质的情况，可以通过简单的颜色调换（color flips）和树旋转来调整。
颜色调换就是把节点的颜色由黑色变为红色，或是由红色变为黑色。
树旋转分为两种：左旋和右旋
1.左旋(右子为轴,当前结点左旋)
image.png
动图：

1550028201064011935.gif

如图，以当前节点的右节点为轴，pivot，a，Y，b，c，的大小关系是：
a<pivot<b<Y<c。调整前pivot的左子树a比pivot小，右子树Y比pivot大，调整后，Y的左子树pivot比Y小，右子树c比pivot大。相当于在原来的a<pivot<Y关系中，比自己大的Y替代了自己，而pivot在原来b<Y<c的关系中，替代了比Y小的b。最后因为b比pivot大，所以b成为了pivot的右子树。也就是调整后的样子。

2.右旋(左子为轴,当前结点右旋)

image.png

动图：

右旋.gif

如图，以当前节点的左节点为轴，pivot，a，Y，b，c，的大小关系是：
b<Y<c<pivot<a。调整前pivot的左子树Y比pivot小，右子树a比pivot大，调整后，Y的左子树b比Y小，右子树pivot比Y大。相当于在原来的Y<pivot<a关系中，比自己小的Y替代了自己，而pivot在原来b<Y<c的关系中，替代了比Y大的c。最后因为c比pivot小，所以c成为了pivot的左子树。也就是调整后的样子。

接下来讨论一下插入红色节点之后，破坏了红黑树结构的几种情况：
1.情况一，插入的红色节点为根节点，也就是，未插入时的红黑是为空树，这时候只需要把该节点颜色调换为黑色即可。
image.png

2.情况二，插入节点的父节点为黑色，没有违反性质，也没有破坏红黑树的结构，不用做任何调整。
3.情况三，插入的父节点是红色

插入节点的父节点是红色，叔叔节点为黑色：那么插入节点的祖父节点如果是红色，那么祖父节点和父节点为连续的两个红色节点，违反了性质四，在该节点插入之前，红黑树的结构都已经被破坏了。而且无论祖父节点是黑色还是红色，通过父节点或叔叔节点的任何路径都必定通过祖父节点，在这些路径上的黑节点数目没有改变，而父亲节点是红色，叔叔节点为黑色，就违反了性质五，在插入节点之前，该树也不是红黑树。
所以插入节点的父节点如果是红色，那么叔叔节点也必定为红色，如图插入N节点

image.png
解决办法（重新构造成红黑树的解决办法）：