尝试手撕红黑树

祖宗根节点必黑，允许黑连黑，不允许红连红；新增红色，爸叔通红就变色，爸红叔黑就旋。

HashMap在1.8以后，底层数据结构由数组+链表变成数组+链表+红黑树，红黑树的节点TreeNode

TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;  左节点
        TreeNode<K,V> right; 右节点
        TreeNode<K,V> prev;   父节点 // needed to unlink next upon deletion
        boolean red;  是否着色为红

红黑树的特点：

1. 节点为红色或黑色
2. 根节点必定为黑色
3. 叶子节点(Null)为黑色
4. 如果一个节点是红色，那么它的子节点必须是黑色的
5. 一个节点到叶子节点的路径上的黑色节点的数量是相同的

#新插入的节点是红色的，根节点除外

情景一：爸叔通红就变色

如图，根节点11为黑色，子节点10.20为红色

当插入9时，父节点10.叔节点20通红变色为黑色

情景二不允许红连红 爸红叔黑就旋

插入，左旋，着色

如图，根节点21黑色，子节点22红色，当插入23红色，爸红叔黑就要旋

黑红红：黑色父节点，左右儿子都是红色子节点

此现象违背特点4，也称之为左旋

情景三:右旋 同上

如图，根节点23黑色，子节点21红色，当插入20红色，触发向右旋转

情景四：先左旋，再右旋

如图，根节点40位黑色，子节点20为红色，新插入节点30为红色，红红不能相连

如图，红黑树除了添加都快，在添加新节点时，比较根节点大小，大跟右节点比较，但极端情况下，可能右边都大，形成伪链表。这样最终’最右’节点有几个，就要比较多少次，红黑树靠颜色维持平衡，再次期间旋转后要重置高度。

初步体会下红黑树，结合插入效果能更加直观的了解整个过程。