treeMap 基于JDK 1.8的学习

困惑了很久的红黑树========来个了断吧

本文主要是为了描述旋转的原则,所以,至于红黑树的数据结构,红黑树的基本准则,不在强调,,红黑树困惑的就是这旋转的过程.!!!

画红黑树很简单的画图工具: https://sourceforge.net/projects/dia-installer/?source=typ_redirect11

参靠博客: http://www.cnblogs.com/skywang12345/p/3245399.html

https://www.cnblogs.com/xrq730/p/6867924.html

三大原则:前提是红黑树的五个性质(根是黑的,空节点是黑的,红色节点不连续)

1.当前节点的父节点是红色,且叔叔节点也是红色

将父节点设为黑色

将叔叔设置成黑色,

祖父节点变红,

将祖父节点设为"新的当前节点 ”（红色节点），进行操作

2.父节点是红,叔叔是黑,且当前节点是父节点的右孩子

将父节点作为"新的当前节点 ”,

以"新的当前节点 ”为支点进行左旋

3.父节点是红,叔叔是黑,且当前节点是父节点的左孩子

将父节点设为"黑色",

将祖父节点设为红色,

以"祖父节点进行"右旋

比如

这是第三点,右旋

左旋加右旋

左旋,后右旋

对应的java 代码

if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//1.当前节点的父节点 是 祖父节的左节点

    Entry<K,V> y = rightOf(parentOf(parentOf(x)));//叔叔(右)节点
    if (colorOf(y) == RED) {//叔叔(右)节点是红色?
        // 1.1父节点是红色,叔叔节点也是红色,设置父节点和叔叔节点都为黑色
        setColor(parentOf(x), BLACK);//设置父节点为黑色
        setColor(y, BLACK);//
        setColor(parentOf(parentOf(x)), RED);
        x = parentOf(parentOf(x));
    } else {//叔叔(右)节点是黑色
        // 1.2父节点是红色,叔叔节点是黑色
        if (x == rightOf(parentOf(x))) {
            //2.1 当前节点是右节点,则当前节点父节点左转
            x = parentOf(x);//
            rotateLeft(x);//左旋
        }
        setColor(parentOf(x), BLACK);//父节点变黑
        setColor(parentOf(parentOf(x)), RED);//祖父节点变红
        rotateRight(parentOf(parentOf(x)));
    }
}

增加告一段落,,

删除真是过于复杂,遍历的时候采用的是中序遍历,找到最小的,然后左->父->右