红黑树的简单认识_红黑树根大吗

一、二叉查找树（二叉搜索树/二叉排序树）

学习红黑树之前，先说明什么是二叉查找树：
1、左子树的所有节点的值均小于其根节点的值。
2、右子树的所有节点的值均大于其根节点的值。
3、左右子树同样均为二叉查找树。
如下图例子所示：

这样，在进行数据查找时，就会产生类似二分查找的效果。
如上图，想要查找6，先会与根节点9比较，小于9则进入左子树，接着与5比较，大于5则进入5的右子树，最终查找到6。
但这样有时候会面临一个问题，如下图：

因为选择9作为根节点，能产生下面情况，那么在进行查找时，性能会大大折扣，因为这已经几乎是线性查找了。因此，引入红黑树概念。

二、红黑树

首先，红黑树是一种特殊的二叉查找树，当其满足以下性质，且只有满足以下全部性质的二叉查找树，我们才称之为红黑树：

1、每个结点要么是红的，要么是黑的。
2、根结点是黑的。
3、每个叶子结点，即空结点（NIL）是黑的[注意：这里叶子节点，是指为空(NIL)的叶子节点！]。
4、如果一个结点是红节点，那么它的两个子节点都是黑节点。
5、任意结点，到其子树中每个叶子结点的路径，都有相同数量的黑色结点。

由于特性5的存在，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。下面的图片就是一个典型的红黑树：

在红黑树中插入的节点都是红色的，因为插入一个红色节点比插入一个黑色节点破坏红黑特性的可能性更小。原因是：插入黑色节点总会改变黑色高度（违背规则5），但是插入红色节点只有一半的机会会违背规则4。另外违背规则4比违背规则5要更容易修正。
在对红黑树进行插入、删除的操作的时候会破坏红黑树结构，为了保持红黑树的特质，需要对红黑树进行修正，怎么修正呢？红黑树提供了三种修正的方法：变色、左旋、右旋。

下面分析插入节点的情况：

像原来的红黑树插入14这个新节点，父节点15为黑色，没有破坏红黑树的条件，因此不需任何改变。
而下面这种：

因为插入节点21后，其父节点22为红色，违背了红黑树的规则4，因此需要动用红黑树修正方法。

下面具体描述红黑树的修正方法：
1、变色：

如上图所示，图a中只有一个根节点20，根据性质2，它的颜色是黑色的；图b插入节点11,节点11是红色的，作为20的左子节点，依然没有破坏红黑树的性质；图c插入节点22，新插入的节点仍然是红色的，图c依然是红黑树；图d中插入新的红节点10，如果不变色，那么不满足性质4，所以把红节点11变色为黑色，同时需要把红节点22变色为黑色，因为要满足性质5。
2、左旋/右旋：

在图d中继续插入节点5变成图e，11节点导致树不平衡，需要对11节点进行旋转操作，因为左子树高，那么就右旋，变成图f，f还要进行变色变成图g。