红黑树的基本概念与结构：
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的兄弟节点为黑色，兄弟节点的右孩子为红色。
左旋，将父节点与兄弟节点颜色互换。
3279916262