树-2-3-4树->红黑树

变换是局部的，只会影响到关联连接，且每次变换都是很小的常量

2-3-4树

http://www.cnblogs.com/nullzx/p/6111175.html
https://blog.csdn.net/u014634338/article/details/78007490
https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/5-TreeSet%20and%20TreeMap.md # 红黑树超级详细
https://www.w3xue.com/exp/article/201811/6428.html # 详细红黑树平衡过程
https://www.w3xue.com/exp/article/201811/6431.html # 详细红黑树旋转原理
https://blog.csdn.net/weixin_42340670/article/details/80550932 # 旋转案例

插入

image.png
image.png

删除

向父亲节点寻找是否需要合并

image.png
image.png
删除过程中，我们同样可以采取预合并的操作，即我们在删除的搜索路径中（除根节点，因为根节点没有兄弟节点和父节点），遇到当前节点是2节点，如果兄弟节点也是2节点就合并（该节点的父节点中的key下移，与自身和兄弟节点合并）；如果兄弟节点不是2节点，则父节点的key下移，兄弟节点中的key上移。
image.png

红黑二叉查找数

红黑树可以用2-3-4树表示，但是要保持“各节点”的"黑平衡"二叉树

插入是至底插入（红节点），如果父节点是（黑节点），结束。否则然后逐级往上平衡树，每次调整的是cur -> cur.parent -> cur.parent.parent

删除节点如果是(红节点)，与中序后继节点替换后，否则需要逐级向下平衡树

红黑树就是用红链接表示3-4-结点的2-3-4树
红链接将两个2-结点连接起来构成一个3-4-结点，黑链接则是2-3树中的普通链接 2-节点，同时全部取红链接的左/右节点作为红节点
***若插入的值导致4-节点分裂，分裂出的父节点的父节点为2-节点，立即进行合并

1. 红链接均为左链接
2. 没有任何一个结点同时和两条红链接相连
3. 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同

2-3树的深度很小，平衡性好，效率高，但是其有两种不同的结点，实际代码实现比较复杂
红黑树用红链接表示2-3树中另类的3-4-结点，统一了树中的结点类型，使代码实现简单化，又不破坏其高效性

使用 2-3-4 树进行插入红黑树

转换一.png

   20     -     40     -     100
    /      \                /    \
5-10     25             50   120-160-200

转换二.png

          40     -     100
    /      \                \
10-20    45-48-50       120-160-200

2-3-4树.png
红黑树.png

旋转原理(左倾红黑树)

左/右旋转发生的前提，一定是向上进行调整的过程中遇到的情况，也就是说cur节点肯定不是新插入的节点
一次旋转是不够的，还需要一次旋转后的调色

1. 若插入节点的父亲是其祖先的左节点，先左旋，后续就是右旋
2. 若插入节点的父亲是其祖先的右节点，先右旋，后续就是左旋
   双旋.png

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            TreeNode<K,V> r, pp, rl;
            if (p != null && (r = p.right) != null) {
                // 左旋转，若cur节点存在左节点rl，需要将rl转义给parent.right
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                // 如果p.parent是null说明时根节点，r成为新的根节点，根节点为black
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                // 将 原parent的父节点指向cur
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                // cur作节点指向原parent
                r.left = p;
                p.parent = r;
            }
            return root;
        }

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                 // 右旋转，若cur节点存在右节点lr，需要将lr转义给parent.left
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                // 如果p.parent是null说明时根节点，l成为新的根节点，根节点为black
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                // 将 原parent的父节点指向cur
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                // cur作节点指向原parent
                l.right = p;
                p.parent = l;
            }
            return root;
        }