红黑树的基本概念与结构：

1、红黑树的简介：

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。

红黑树是具备了某些特性的二叉查找树，能解决非平衡树问题，是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。

2、红黑树的特性：

红黑树保证最长路径不超过最短路径的二倍（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。

一颗典型的红黑树如下：

在其中我们可以发现一些明显的特点，比如：

· 节点不是红色就是黑色，根节点为红色

· 红黑树的叶子节点是空节点，而不是传统的叶子节点

· 同一路径不存在连续红节点

以上只是红黑树的部分规则，红黑树规则如下：

（1）根是黑色

（2）节点是红色或黑色

（3）叶子节点都是黑色（最底层的空节点）

（4）从任意节点到叶子节点的所有路径都包含相同数目的黑色节点

（5）红色节点的子节点都是黑色，红色节点的父节点都是黑色，从根节点到叶子节点的路径上不能有2个连续的红色节点

在上述五个规则之中，还有以下特点：

· 规则4与规则5保证了红黑树的大致平衡，根到叶子的所有路径中最长路径不会超过最短路径的2倍。

· 使红黑树在最坏的情况下，也可以有O(log2N)的查找效率。

· 关于叶子节点：NULL代表空节点。

默认新插入的节点为红色，因为父节点黑色的概率较大，这样可以避免颜色冲突。

红黑树操作：

红黑树操作和其他树形结构差不多，一般操作包括基本的查找、插入、删除等。相对于查找，红黑树的插入和删除操作要相对复杂一些。

1、自平衡策略：

在插入或删除后沿着节点到根的路径执行左旋、右旋、变色，就能让树重新满足定义。

旋转操作分为左旋与右旋。左旋是将某个节点旋转为其右子节点的左子节点，右旋是将节点旋转为左子节点的右子节点。

左旋：

右旋：

变色：

对于当前节点而言，若左右子节点均为红色，则执行变色。

2、插入操作：

插入时新节点默认为红色，若插入后依然满足红黑树定义，则插入完成。否则，根据叔叔节点进行调整。

叔叔节点为黑色时：LL型、RR型、LR型、RL型。

叔叔节点为红色时：叔叔节点、父亲节点、爷爷节点全变色，爷爷节点变新节点，然后再进行一轮调整。

3、删除操作：

相对于插入而言，红黑树的删除要稍微复杂一些。

· 若待删除节点为红色节点，则直接删除即可。

· 若待删除节点为黑色节点，且其孩子节点为红色，则将待删除节点替换为孩子节点，并将孩子节点由红转黑即可。

· 若待删除节点为黑色节点，且其孩子节点为黑色，则需要进一步解决。

针对最后一种删除，首先将待删除节点替换为它的孩子节点，并设定为节点N，N沿用原待删除节点（对父子节点）的称呼。但注意，实际删除的是原待删除节点，且删除后通过N的路径长度-1。

具体情况如下：

①．N是新的根。

此时不做任何调整。

②．N的父节点、兄弟节点、以及兄弟节点的孩子节点均为黑色。

将兄弟节点变为红色，然后继续递归向上判定。

③．N的兄弟节点为红色，其余节点均为黑色。

左旋，然后将父节点与兄弟节点的颜色互换。

④．N的父节点为红色，兄弟节点及兄弟节点的孩子节点均为黑色。

将父节点与兄弟节点的颜色互换。

⑤．N的兄弟节点为黑色，兄弟节点的左孩子为红色，右孩子为黑色。

右旋，然后将兄弟节点与兄弟节点左孩子的颜色互换。

⑥．N的兄弟节点为黑色，兄弟节点的右孩子为红色。

左旋，将父节点与兄弟节点颜色互换。