二叉树
重点
二叉树的用途
二叉树的插入，红黑树的插入。
二叉树的用途
首先二叉树的使用场景基本都是在有序的场景。
比如：在一个大的排序集合里面，查询某个元素是否存在。他的平均查找效率为log2n
相较于有序链表来说，二叉树的插入，查询，删除 效率是相对来说是比较平衡的
一般来说有序二叉树的查询需求是要大于其插入需求。
普通二叉树的插入
首先我们来回顾下顺序二叉树的定义。
1. 所有的左节点的值要小于其右节点的值。
2.所有左子孙节点都要小于其父亲节点。所有右子孙节点都要大于其父亲节点。
2. 有序二叉树不存在相同的值，可以用记录相同的值有几个但不影响其本身数据结构。
3.当N>1时，除根节点以外的其余节点可分为M个互为相交的有限集合T1,T2,...,Tm，其中的每个集合本身又是一棵树，并称其为根的子树（subtree）。（这一点用于我们去插入一个节点，因为子树是不需要关心上层节点的变化）
现在我们来看一下实战环节
现在我们有个一个集合为（9,0,1,3,2,5,4,6,8,7）的一个集合，来看我们一步一步来生成一个普通有序二叉树的过程。
1.
2.
3.
4.
增加的原理很简单先比较根节点，如果根节点大于所要插入的数。则跟其左孩子接口点比较，反正跟其右孩子比较，然后重复以上规则，直到其孩子节点为空，则成为其上层节点的孩子节点。
总结：可以看出我们整颗树 构建下来深度比较仓 比如我们要查7从根结点遍历到7，需要整整比较7次，如果我们可能是一个更大的集合，那么它的查找的最大事件复杂度可能会接近o(n) , 所以为了查找树的查找事件复杂度接近log2（n） ，
红黑树的特性
红黑树(自平衡二叉树)是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3. 每个叶节点（NIL节点，空节点）是黑色的。
性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
性质1 保证了可调整中心， 实际上为了维护性质5 ， 我们不可能完全构建所有叶子节点到根节点的都含有相同数目的节点
所以退而求次，出现了红色节点来调整平衡。 通过一些系列的旋转来达到目的。
性质2. 根节点是黑色 对应的性质4 红色节点是黑色， 红色作为调整节点， 最终我们还是求得黑色节点作为平衡，所以根节点是黑色没毛病。
性质3. 对应的是性质5和性质1，叶节点为黑色的才能保证我们去调整我们的节点趋于平衡。便于我们调整的时候有回旋的余地。
性质4和性质5 联合起来看才能保证我们树的深度是最短路径距离的一倍。
下面来看看 红黑树的通过数学归纳法来证明
红黑树的时间复杂度为: O(lgn)
下面通过“数学归纳法”对红黑树的时间复杂度进行证明。
定理：一棵含有n个节点的红黑树的高度至多为2log(n+1).
证明：
"一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题是 "高度为h的红黑树，它的包含的内节点个数至少为 2h/2-1个"。
我们只需要证明逆否命题，即可证明原命题为真；即只需证明 "高度为h的红黑树，它的包含的内节点个数至少为 2h/2-1个"。
从某个节点x出发（不包括该节点）到达一个叶节点的任意一条路径上，黑色节点的个数称为该节点的黑高度(x's black height)，记为bh(x)。关于bh(x)有两点需要说明：
第1点：根据红黑树的"特性(5) ，即从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点"可知，从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着，bh(x)的值是唯一的！
第2点：根据红黑色的"特性(4)，即如果一个节点是红色的，则它的子节点必须是黑色的"可知，从节点x出发达到叶节点"所经历的黑节点数目">= "所经历的红节点的数目"。假设x是根节点，则可以得出结论"bh(x) >= h/2"。
进而，我们只需证明 "高度为h的红黑树，它的包含的黑节点个数至少为 2bh(x)-1个"即可。
到这里，我们将需要证明的定理已经由
"一棵含有n个节点的红黑树的高度至多为2log(n+1)"
转变成只需要证明
"高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。
下面通过"数学归纳法"开始论证高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。
(01) 当树的高度h=0时，
内节点个数是0，bh(x) 为0，2bh(x)-1 也为 0。显然，原命题成立。
(02) 当h>0，且树的高度为 h-1 时，它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的！
下面，由树的高度为 h-1 的已知条件推出“树的高度为 h 时，它所包含的节点树为 2bh(x)-1”。
当树的高度为 h 时，
对于节点x(x为根节点)，其黑高度为bh(x)。
对于节点x的左右子树，它们黑高度为 bh(x) 或者 bh(x)-1。
根据(02)的已知条件，我们已知 "x的左右子树，即高度为 h-1 的节点，它包含的节点至少为 2bh(x)-1-1 个"；
所以，节点x所包含的节点至少为 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2bh(x)-1。
因此，原命题成立。
由(01)、(02)得出，"高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"。
因此，“一棵含有n个节点的红黑树的高度至多为2log(n+1)”
构建一个红黑树：
1. 每个节点有颜色属性，设置为枚举红色或者黑色，默认为插入红色。
2.根节点是黑色， 只需要定义一个root 节点不管最后结果如何， 我们置为黑色即可
3. 把null 默认为黑色，即孩子节点为空的时候即为黑色同样也是作为叶子节点
4. 每个红色节点的孩子节点都为黑色。那么即不可能存在两个相邻的红色节点。这点也OK
5. 性质五，我们只需要每次插入的节点置为红色，则不改变整个红黑树的平衡即可。
在开始构造前来先看树的旋转
树的旋转分为左旋和右旋
左旋
左旋的合理性 ：
第一Y 能否可以作为父亲节点，这个回顾我们二叉树的定义，如果X 能够作为左节点或者右节点是满足条件A（大于或者小于）
那么其子孙节点同样也是满足其条件(回想插入规则)
Y是X的右子节点，那么意味Y>X.同样X就可以作为Y的左子节点
同样β左Y的左子节点，他也是满足大于X的特性满足作为X的右节点。
理解左旋之后，看看下面一个更鲜明的例子。你可以先不看右边的结果，自己尝试一下。
右旋合理性，同左旋合理性
看完 左旋和右旋我们看下红黑树面临的六种情况首先我们上代码来看看JDK 如何来实现红黑树的插入的
private void fixAfterInsertion(Entry x) {
//新节点着色
x.color = RED;
//循环到新节点 不为空且不是根且根的节点不是红色
while (x !=null && x != root && x.parent.color == RED) {
//如果X的父节点（假设为:P）是其父节点的父节点（假设为:G）的左节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//获取父节点的父节点的右节点y
Entry y = rightOf(parentOf(parentOf(x)));
// G
// / \
// p y
// /
// x
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
// ?????
x = parentOf(parentOf(x));
}else {
//右旋
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
//以X的父节点的父节点（G）为中心左旋转
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
}else {
//如果X的父节点（假设为:P）是其父节点的父节点（假设为:G）的右节点
// G
// / \
// y P
// \
// x
//
Entry y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}else {
//左旋
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
//以X的父节点的父节点（G）为中心右旋转
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
左边图为情况1 ， 右边图为调整后
