红黑树--在hashMap中的以用

1.红黑树的定义

（1）每个节点只有两种颜色：红色和黑色。

（2）根节点是黑色的。

（3）每个叶子节点（NIL）都是黑色的空节点。

（4）从根节点到叶子节点，不会出现两个连续的红色节点。

（5）从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

1、查询节点

查询节点是最简单的一个，他的查找过程和二叉查找树一样，查找元素比当前节点大，就从右子树继续查找比较，查找元素比当前节点小，就从左子树继续查找比较。查找过程就不再赘述了。

2、插入节点

（1） 没有父节点： 即为根节点，黑色

（2）父节点是黑色：不变

（3）父节点为红色，叔叔节点为空：变色和旋转

（4）父节点红色，叔叔节点为红色：变色

（5）父节点为红色，叔叔节点为黑：变色和旋转

/**
 * 插入平衡
 */
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    //将x节点设为红色（新插入节点一开始为红色）
    x.red = true;
    //一个没有边界的循环(需要内部跳出)
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        //取出x的父节点并判断是否为null
        if ((xp = x.parent) == null) {
            //x没有父节点
            x.red = false;//变色(黑色)
            return x;//x为根节点发那会
        }
        //如果x存在父节点且x的父节点为黑色或x的父父节点不存在
        else if (!xp.red || (xpp = xp.parent) == null)
            //返回root
            return root;
        //如果x的父节点是父父节点的左孩子
        if (xp == (xppl = xpp.left)) {
            //父父节点的右孩子不为null且为红色
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;//变色(黑)
                xp.red = false;//变色(黑)
                xpp.red = true;//变色(红)
                x = xpp;
            }
            else {
                //x是父节点的右孩子
                if (x == xp.right) {
                    //左旋
                    root = rotateLeft(root, x = xp);
                    //处理x的父父节点
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //x的父节点存在
                if (xp != null) {
                    xp.red = false;//变色
                    //x的父父节点存在
                    if (xpp != null) {
                        xpp.red = true;//变色
                        //右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        //如果x的父节点是父父节点的右孩子
        else {
            //x的父父节点的左孩子存在且为红色
            if (xppl != null && xppl.red) {
                xppl.red = false;//变色(黑)
                xp.red = false;//变色(黑)
                xpp.red = true;//变色(红)
                x = xpp;
            }
            else {
                //如果x是父节点的左孩子
                if (x == xp.left) {
                    //右旋
                    root = rotateRight(root, x = xp);
                    //处理x的父父节点
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //如果x的父节点存在
                if (xp != null) {
                    xp.red = false;//变色(黑)
                    //如果x的父父节点存在
                    if (xpp != null) {
                        xpp.red = true;//变色(红)
                        //左旋
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}
           

1、将链表的首节点当做临时的红黑树根节点，左右孩子置为null

2、循环按顺序取出链表的节点，进行红黑树插入，和插入后平衡

2.1、取出链表节点，经过hash比较，插入到红黑树合适的位置(保证平衡性)

2.2、由于插入的节点会破坏红黑树的性质，所以需要进行插入后平衡

2.2.1、新插入的节点置为红色

2.2.2、父节点和父父节点的null判断和颜色判断

2.2.2.1、判断新插入节点的父节点是否存在，不存在则返回

2.2.2.1、如果父节点是黑色的，或者父父节点不存在着，则返回

2.2.3、父节点是父父节点的左孩子还是右孩子判断

2.2.3.1、是左孩子且兄弟节点存在并且是红色，则执行相应的变色，然后进行下一轮判断。

2.2.3.2、是左孩子当兄弟节点不存在（或者是黑色），则执行相应的左旋/右旋。

2.2.3.3、是右孩子且兄弟节点存在并且是红色，则执行相应的变色，然后进行下一轮判断。

2.2.3.4、是右孩子当兄弟节点不存在（或者是黑色），则执行相应的左旋/右旋。

3、链表循环完毕后，确保哈希桶指定位置存储的是红黑树的根节点

参考：

https://blog.lzoro.com/2018/08/31/r_b_tree/

https://baijiahao.baidu.com/s?id=1645429373049393021&wfr=spider&for=pc