红黑二叉树

1.引言

HashMap的基本结构是数组，链表和红黑树。以数组为基本形态，数组中的元素先以链表形式储存，当链表的长度超过8时（包含数组上的那个链表头）就会将链表转换为红黑树，以加快修改和查询效率。当然除HashMap还有很多地方都会用到红黑树，理解红黑树的原理还是比较重要的。*

2.概念与由来

红黑树的本质是二叉树，二叉树在插入元素的时候是根据关键字（可以理解为用来识别每个节点的id，一般是hash来判断）的大小来判断插入到哪一个分支的，如下图所示：（备注：大写字母代表每个节点相当于每个节点的名字没有实际意义在本文中方便文字说明，数字代表每个节点的关键字的大小有实际意义

规律是父节点的关键字大于左子节点且小于右子节点，即B<A<C的关系。
举个插入的例子：当新插入一个元素是会判断其关键字大小如果大于A的，则插入到A的右子节点也就是C，但是此
处已经有了节点存在了，然后继续判断是否大于C，如果小于C，则插入到C的左子节点，正好此处为空存在，插入
后形成下图所示：
但是按照这个规则插入就遇到一个问题，如下图所示的情况：

这样的现状导致查询效率非常低，如果要找节点J，这样一串遍历下来就跟链表结构区别不大了，从而失去了树结
构的优势。为了解决这个问题出现了平衡二叉树。而平衡二叉树在原始二叉树基础上加了平衡节点的机制，每插入
一次元素后都会自动去判断是否失衡了，如果失衡了则会自动调整节点的布局结构使其从根节点（最顶端的节点）
到每一个叶节点（最低端的节点）的距离不会相差太多。然而平衡二叉树的要求过于严格，几乎每一次插入都要调
整节点的布局，使得插入操作效率变得很低，于是有了一个这种的办法那就是红黑树。

3.红黑树规则

一共如下四条规则：

1、每个节点不是红色就是黑色的；
2、根节点（顶端节点）总是黑色的；
3、如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
4、从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。

根据该规则，新插入的节点全都是红色，然后再根据具体情况做颜色变换甚至旋转。
原因：如果我们新插入的颜色是黑色的话，那么每插入一个节点都会违背第四条规则，这样就导致每次都做变色甚
至旋转。当插入红色节点时，首先不会违反第四条规则，并且如果其父节点是黑色时也不会违反第三条，至于第二
条规则大部分情况不会违背基本不予以考虑了。这样一来插入红色就不是每次都需要变色或者旋转了，这样就可以
优化计算机的处理过程。