数据结构-二叉树-红黑树

一、红黑树的概念

红黑树是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red或者BLACK，通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因为是接近平衡的。

二、红黑树的性质

·1、每个结点不是红色就是黑色

2、根节点是黑色的

3、如果一个节点是红色的，则它的两个孩子节点必须是黑色的。

4、对于每个节点，从该节点到其所有后代节点的简单路径上，均包含相同的黑色节点（每条路径上黑色节点的数量相等）根到空节点算一条路径。

5、NIL节点是黑色的

三、怎么做到最长路径不超过最短路径的二倍？

根是黑色的，NIL是黑色的，如果一个节点是红色的，那么它的左右孩子都是黑色，不同的路径上有相同数量的黑色节点。上面的条件就可以推出最长路径不超过最短路径的两倍。

四、为什么红黑树更优于AVL树。

因为，旋转的次数少了。

五、红黑树的插入

再插入的时候我们插入的是红节点，如果插入黑色节点，就会违背各个路径上的黑色节点是相等的。如果插入红色节点，我们可能会违背一个节点是红色的它的左右孩子都是黑色的条件。当父亲是黑色的时候，插入红色节点没有违背任何的条件，如果当父亲是红色的时候，就违背了一个节点是红色的它的左右孩子都是黑色的条件。对于这个情况我们需要分类讨论。红黑树也是一棵不太平衡的平衡二叉树。

情况一

叔叔存在且为红

情况1，红黑树我们看的是uncle节点，父亲和叔叔变黑，grandfather变红 。那么局部的子树里面红黑节点的数量不变，且连续的红节点问题暂时解决了。

继续向上处理：

1、grandfather没有父亲，就是根，把grandfather变黑即可。

2、grandfather有父亲且为黑，结束。

3、grandfather有父亲且为红，和刚才是类似问题处理，把grandfather当成插入节点，按情况1，进行处理。

情况二：

叔叔不存在

如果叔叔不存在旋转加变色。

情况三：

叔叔存在且为黑

旋转+变色

总结：

红黑树插入关键看叔叔。

1、叔叔存在且为红变色+向上处理

2、叔叔不存在或者叔叔为黑色变色+旋转。旋转需要进行根据位置来判断。grandfather->left == parent ,parent->left == cur

右旋：父亲变黑，祖父为红，不需要再往上一层处理。

先左后右双旋：cur为黑，grandfather为红