共计 1878 个字符，预计需要花费 5 分钟才能阅读完成。
二叉搜寻树的缺点
二叉搜寻树作为数据存储的构造有重要的劣势：
能够疾速的查找给定关键字的数据项，并且能够疾速的插入和删除数据项，然而，二叉搜寻树有一个很麻烦的问题：如果插入的数据是有序的数据，比方上面的状况有一棵初始化为 9 8 12 的二叉树
插入上面的数据：7 6 5 4 3
非均衡树：
比拟好的二叉搜寻树数据应该是左右均匀分布的
然而插入间断数据后，散布的不平均，咱们称这种树为非均衡树
对于一颗均衡二叉树来说，插入 / 查找等操作的效率是 O(logN)
对于一颗非均衡树，相当于编写了一个链表
树的平衡性
为了能以较快的工夫 O(logN)来操作一棵树，咱们须要保障树总是均衡的：
至多大部分是均衡的，那么工夫复杂度也是靠近 O(logN)的
也就是说树中每个节点的右边的子孙节点的个数，应该尽可能的等于左边的子孙节点的个数
常见的均衡树有哪些？
AVL 树：
AVL 树是较早的一种均衡树，它有些方法保留树的均衡（每个节点多存储了一个额定的数据）
因为 AVL 树是均衡的，所以工夫复杂度也是 O(logN)
然而，每次插入 / 删除操作绝对于红黑树效率不高，所以整体效率不如红黑树
红黑树：
红黑树也是通过一些个性来放弃树的均衡
因为红黑树，所以工夫复杂度也是在 O(logN)
另外插入 / 删除等操作，红黑树的性能要优于 AVL 树，所以当初均衡树的利用根本都是红黑树
红黑树
红黑树规定：
红黑树，除了合乎二叉搜寻树的根本规定外，还增加了以下个性：
【性质 1】. 节点是红色或彩色
【性质 2】. 根节点是彩色
【性质 3】. 每个叶子节点都是彩色的空节点（NIL 节点）
【性质 4】. 每个红色节点的子节点都是彩色（从每个叶子到根的门路上不能有两个间断的红色节点）
【性质 5】. 从任意节点到其每个节点的所有门路都蕴含雷同数目的彩色节点
规定很重要，上面练习会用到，下图就是一个红黑树，下面的五点都合乎
红黑树的绝对均衡
后面的束缚，确保了红黑树的要害个性：
从根到叶子的最长可能门路，不会超过最短可能门路的两倍长
后果就是这个树根本是均衡的
尽管没有做到相对的均衡，然而能够保障在最坏的状况下，仍然是高效的
为什么能够做到最长门路不超过最短门路的两倍呢？
【性质 4】决定了门路不能有两个相连的红色节点
【性质 5】所有门路都有雷同数目的彩色节点
这就表明了没有门路能多余任何其余门路的两倍长
插入新节点遇到状况的解决办法
插入一个新节点时，有可能树不再均衡，能够通过三种形式的变换，让树保持平衡
换色 / 左旋转 / 右旋转
变色
为了从新合乎红黑树的规定，尝试把红色节点变成彩色，或者把彩色节点变成红色
首先须要晓得插入的新节点通常默认为红色节点
因为在插入节点为红色的时候，有可能插入一次是不违反红黑树任何规定的（插入 9）
而插入彩色节点，必然会导致有一条门路上多了彩色节点，这是很难调整的
红色节点有可能导致呈现红红相连的状况，然而这种状况能够通过色彩变换和旋转来调整
左旋转
逆时针旋转红黑树的两个节点，使得父节点被本人的有孩子取代，而本人成为本人的左孩子
图中，身为右孩子的 x 取代了 a 的地位，而 a 变成了 x 的左孩子。此为左旋转
右旋转
顺时针旋转红黑树的两个节点，使得父节点被本人的左孩子取代，而本人成为本人的右孩子
图中，身为左孩子的 x 取代了 a 的地位，而 a 变成 x 的右孩子
插入操作
接下来，讨论一下插入的状况
设要插入的节点为 N, 其父节点为 P
其祖父节点为 G，其父亲的兄弟节点为 U(即 P 和 U 是同一节点的子节点)
状况一：
新节点 N 位于树的根，没有父节点
这种状况下，咱们间接将红色变换成彩色即可，这样满足性质 2
状况二
新节点的父节点 P 是彩色
性质 4 没有生效（新节点是红色的），性质 5 也没有任何问题
只管新节点 N 有两个彩色的叶子节点 nil，然而新节点 N 是红色的，所以通过它的门路中彩色节点的个数仍然雷同，满足性质 5（下图省略了 nil）
状况三
P 为红色，U 也是红色
操作计划：
将 P 和 U 变换为彩色，并且将 G 变换为红色
可能呈现的问题
然而 N 的祖父节点 G 的父节点也可能是红色，这就违反了性质 3，能够递归调整色彩
然而如果递归调整色彩到了根节点，就须要进行旋转了，这个上面遇到了再解说
状况四
N 的叔叔 U 是黑节点，且 N 是左孩子。简写：
父红叔黑祖黑 N 是左儿子
变换：父黑 – 祖红 – 右旋转
状况五
N 的叔叔 U 是彩色节点，且 N 是右孩子。简写：
父红叔黑祖黑，N 是右孩子
变换：
以 P 为根，左旋转
将 P 作为新插入的红色节点思考即可
本人（N）变成彩色
祖变成红色
以祖为根，进行右旋转
实操
上面咱们将 10，9，8，7，6，5，4，3，2，1 顺次插入树中造成红黑树。
多图预警。。。。
红黑树的常识就到这里，至于代码实现看下面的图也晓得是十分难的，临时就先不钻研代码，先捋分明逻辑。
