IT@程序员猿媛Java随笔-生活工作点滴

【Java 笔记】Java 中 TreeMap 相关整理

2019-08-15  本文已影响8人  58bc06151329

文前说明

作为码农中的一员，需要不断的学习，我工作之余将一些分析总结和学习笔记写成博客与大家一起交流，也希望采用这种方式记录自己的学习之旅。

本文仅供学习交流使用，侵权必删。
不用于商业目的，转载请注明出处。

1. 概述

1.1 二叉树

二叉树

二叉树的性质

二叉树的遍历

平衡二叉树

二叉查找树

二叉查找树

统一定义概念

统一定义概念

1.2 红黑树

二叉查找树

红黑树的特性

红黑树 规则被破坏

1.2.1 红黑树的变色操作

变色

1.2.2 红黑树的旋转操作

左旋转 右旋转

1.2.3 红黑树的添加操作

添加结点操作的情况分析

情况 1 情况 2

依据叔叔结点的情况，又可以分为三种情况处理

情况 3 情况 4 情况 5

1.2.4 红黑树的删除操作

删除结点操作的情况分析

情况 1 情况 2 情况 3 情况 4 情况 5 情况 6

2. TreeMap 原理

//比较器：可以通过这个对TreeMap的内部排序进行控制
private final Comparator<? super K> comparator;
//TreeMap的红黑结点，内部类
private transient Entry<K,V> root = null;
//map中元素的个数
private transient int size = 0;
//map中结构变动 的次数
private transient int modCount = 0;
//TreeMap的红黑树结点对应的集合
private transient EntrySet entrySet = null;
//keyset的导航类
private transient KeySet<K> navigableKeySet = null;
//键值对的倒序映射
private transient NavigableMap<K,V> descendingMap = null;

2.1 TreeMap 的构造函数

//使用默认构造函数，按照自然顺序进行排序
public TreeMap() {
    comparator = null;
}

//创建指定排序的比较器
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

//创建包含指定map的treeMap，按照自然顺序进行排序
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}
//将一个指定map中的所有元素复制到新的map中
public void putAll(Map<? extends K, ? extends V> map) {
    int mapSize = map.size();
    if (size==0 && mapSize!=0 && map instanceof SortedMap) {
        Comparator c = ((SortedMap)map).comparator();
        if (c == comparator || (c != null && c.equals(comparator))) {
            ++modCount;
            try {
                buildFromSorted(mapSize, map.entrySet().iterator(),
                                null, null);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
            return;
        }
    }
    super.putAll(map);
}
//创建一个map包含指定的比较器
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

private void buildFromSorted(int size, Iterator it,
        java.io.ObjectInputStream str,
        V defaultVal)
    throws  java.io.IOException, ClassNotFoundException {
    this.size = size;
    root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
      it, str, defaultVal);
}

//根据一个已经排好序的map创建一个TreeMap，将map中的元素逐个添加到TreeMap中，并返回map的中间元素作为根结点
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
                                         int redLevel,
                                         Iterator it,
                                         java.io.ObjectInputStream str,
                                         V defaultVal)
    throws  java.io.IOException, ClassNotFoundException {

    if (hi < lo) return null;
    //获取中间元素
    int mid = (lo + hi) >>> 1;

    Entry<K,V> left  = null;
    //如果lo小于mid，则递归调用获取mid的左子结点
    if (lo < mid)
        left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                               it, str, defaultVal);

    //获取mid结点对应的key和value
    K key;
    V value;
    if (it != null) {
        if (defaultVal==null) {
            Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
            key = entry.getKey();
            value = entry.getValue();
        } else {
            key = (K)it.next();
            value = defaultVal;
        }
    } else { // use stream
        key = (K) str.readObject();
        value = (defaultVal != null ? defaultVal : (V) str.readObject());
    }
    //创建middle结点
    Entry<K,V> middle =  new Entry<>(key, value, null);

    //如果当前结点的深度是红色结点的深度，则将结点设置为红色
    if (level == redLevel)
        middle.color = RED;
    //设置middle为left的父结点，left为middle的左子结点
    if (left != null) {
        middle.left = left;
        left.parent = middle;
    }
    //递归调用获取mid的右子结点
    if (mid < hi) {
        Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
                                           it, str, defaultVal);
        middle.right = right;
        right.parent = middle;
    }

    return middle;
}

2.2 put 操作

public V put(K key, V value) {

    //用t表示二叉树的当前结点
    Entry<K,V> t = root;
    //t为null表示一个空树，即TreeMap中没有任何元素，直接插入
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        //将新的key-value键值对创建为一个Entry结点，并将该结点赋予给root
        root = new Entry<>(key, value, null);
        //容器的size = 1，表示TreeMap集合中存在一个元素
        size = 1;
        modCount++; //修改次数 + 1
        return null;
    }
    int cmp; //cmp表示key排序的返回结果
    Entry<K,V> parent; //父结点
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator; //指定的排序算法
    //如果cpr不为空，则采用既定的排序算法进行创建TreeMap集合
    if (cpr != null) {
        do {
            parent = t; //parent指向上次循环后的t
            cmp = cpr.compare(key, t.key); //比较新增结点的key和当前结点key的大小

            //cmp返回值小于0，表示新增结点的key小于当前结点的key，则以当前结点的左子结点作为新的当前结点
            if (cmp < 0)
                t = t.left;

            //cmp返回值大于0，表示新增结点的key大于当前结点的key，则以当前结点的右子结点作为新的当前结点
            else if (cmp > 0)
                t = t.right;

            //cmp返回值等于0，表示两个key值相等，则新值覆盖旧值，并返回新值
            else
                return t.setValue(value);
        } while (t != null);
    }

    //如果cpr为空，则采用默认的排序算法进行创建TreeMap集合（默认构造方法时cpr为null）
    else {
        if (key == null) //key值为空抛出异常
            throw new NullPointerException();

        /* 下面处理过程用compareTo比较和上面一样 */
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }

    //将新增结点当做parent的子结点
    Entry<K,V> e = new Entry<>(key, value, parent);

    //如果新增结点的key小于parent的key，则当做左子结点
    if (cmp < 0)
        parent.left = e;
    else

        //如果新增结点的key小于parent的key，则当做左子结点
        parent.right = e;

     /*
     *  上面已经完成了排序二叉树的的构建，将新增结点插入该树中的合适位置
     *  下面fixAfterInsertion()方法就是对这棵树进行调整、平衡
     */
    fixAfterInsertion(e);
    size++; //TreeMap元素数量 + 1
    modCount++; //TreeMap容器修改次数 + 1
    return null;
}

private void fixAfterInsertion(Entry<K,V> x) { // Entry<K,V> x表示新增结点
    x.color = RED; //新增结点的颜色为红色
    //循环 直到 x不是根结点，且x的父结点不为红色
    while (x != null && x != root && x.parent.color == RED) {
         //如果X的父结点（P）是其父结点的父结点（G）的左结点
         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
             //获取X的叔结点(U)
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            //如果X的叔结点（U） 为红色（情况三）
            if (colorOf(y) == RED) {
                //将X的父结点（P）设置为黑色
                setColor(parentOf(x), BLACK);
                //将X的叔结点（U）设置为黑色
                setColor(y, BLACK);
                //将X的父结点的父结点（G）设置红色
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
             //如果X的叔结点（U为黑色）；这里会存在两种情况（情况四、情况五）
            } else {
                //如果X结点为其父结点（P）的右子树，则进行左旋转（情况四）
                if (x == rightOf(parentOf(x))) {
                     //将X的父结点作为X
                    x = parentOf(x);
                     //右旋转
                    rotateLeft(x);
                }
               //（情况五）
               //将X的父结点（P）设置为黑色
                setColor(parentOf(x), BLACK);
                //将X的父结点的父结点（G）设置红色
                setColor(parentOf(parentOf(x)), RED);
                //以X的父结点的父结点（G）为中心右旋转
                rotateRight(parentOf(parentOf(x)));
            }
        //如果X的父结点（P）是其父结点的父结点（G）的右结点
        } else {

            //获取X的叔结点（U）
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                //将X的父结点（P）设置为黑色
                setColor(parentOf(x), BLACK);
                //将X的叔结点（U）设置为黑色
                setColor(y, BLACK);
                //将X的父结点的父结点（G）设置红色
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            }

             //如果X的叔结点（U为黑色）；这里会存在两种情况（情况四、情况五）
             else {
                //如果X结点为其父结点（P）的右子树，则进行左旋转（情况四）
                if (x == leftOf(parentOf(x))) {
                    //将X的父结点作为X
                    x = parentOf(x);
                    //右旋转
                    rotateRight(x);
                }
                 //（情况五）
                //将X的父结点（P）设置为黑色
                setColor(parentOf(x), BLACK);
                //将X的父结点的父结点（G）设置红色
                setColor(parentOf(parentOf(x)), RED);
                //以X的父结点的父结点（G）为中心右旋转
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    //将根结点G强制设置为黑色
    root.color = BLACK;
}

左旋（rotateLeft() 方法）

private void rotateLeft(Entry<K,V> p) {

        if (p != null) {
            //获取P的右子结点，其实这里就相当于新增结点N（情况四而言）
            Entry<K,V> r = p.right;
            //将R的左子树设置为P的右子树
            p.right = r.left;
            //若R的左子树不为空，则将P设置为R左子树的父亲
            if (r.left != null)
                r.left.parent = p;
            //将P的父亲设置R的父亲
            r.parent = p.parent;
            //如果P的父亲为空，则将R设置为跟结点
            if (p.parent == null)
                root = r;
            //如果P为其父结点（G）的左子树，则将R设置为P父结点(G)左子树
            else if (p.parent.left == p)
                p.parent.left = r;
            //否则R设置为P的父结点（G）的右子树
            else
                p.parent.right = r;
            //将P设置为R的左子树
            r.left = p;
            //将R设置为P的父结点
            p.parent = r;
        }
}

右旋（rotateRight() 方法）


private void rotateRight(Entry<K,V> p) {
        if (p != null) {
            //将L设置为P的左子树
            Entry<K,V> l = p.left;
            //将L的右子树设置为P的左子树
            p.left = l.right;
            //若L的右子树不为空，则将P设置L的右子树的父结点
            if (l.right != null) 
                l.right.parent = p;
            //将P的父结点设置为L的父结点
            l.parent = p.parent;
            //如果P的父结点为空，则将L设置根结点
            if (p.parent == null)
                root = l;
            //若P为其父结点的右子树，则将L设置为P的父结点的右子树
            else if (p.parent.right == p)
                p.parent.right = l;
            //否则将L设置为P的父结点的左子树
            else 
                p.parent.left = l;
            //将P设置为L的右子树
            l.right = p;
            //将L设置为P的父结点
            p.parent = l;
        }
}

着色（setColor() 方法）

private static <K,V> void setColor(Entry<K,V> p, boolean c) {
    if (p != null)
        p.color = c;
}

2.3 remove 操作

//根据key值删除一个结点，并返回删除的结点
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}
//删除一个结点
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    //如果该结点的左子结点和右子结点均不为空，找到p的后继结点，将后继结点的key和value替代p的key和value,然后将p赋值为s
    //这一步就是将删除p结点的操作改为删除替代结点的操作
    if (p.left != null && p.right != null) {
        //返回p的对应的后继结点，将
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }

    //如果p有左子结点，找到左子结点，否则用右子结点
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    //replacement不为空的话
    if (replacement != null) {
        //将p的父结点设置为replacement的父结点
        replacement.parent = p.parent;
        //如果p就是根结点，那么replacement设置为根结点
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)  //如果p是其父结点的左子结点，将replacement设置为其父结点的左子结点
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;  //否则将replacemnet设置为p的父结点右子结点

        //将p结点置为null，结点删除了
        p.left = p.right = p.parent = null;

        //如果p结点是黑色的，那么需要对树进行调整
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { 
        root = null;   //如果p是空结点，则树是空的
    } else {
        //如果p结点是黑色的，需要对树进行调整
        if (p.color == BLACK)
            fixAfterDeletion(p);
        //如果p的父结点不为空，
        if (p.parent != null) {
            //p为其父结点的左子结点，将其父结点的左子结点置为空
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

//返回结点t的后继结点，返回大于t的最小的结点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    //t为null，返回null
    if (t == null)
        return null;
    else if (t.right != null) {  //t的右子结点不为空
        //设置p为t的右子结点
        Entry<K,V> p = t.right;
        //开始遍历p的左子树，返回左子树中最后一个结点
        while (p.left != null)
            p = p.left;
        return p;
    } else {  //如果t的右子结点为空
        //设置p的t的父结点
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        //循环，如果ch是p的右子结点，一直向上查找
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

//删除结点树调整
private void fixAfterDeletion(Entry<K,V> x) {
    //循环遍历树，x不是根结点，x的颜色是黑色的
    while (x != root && colorOf(x) == BLACK) {
        //x是其父结点的左子结点
        if (x == leftOf(parentOf(x))) {
            //sib为x的的兄弟结点
            Entry<K,V> sib = rightOf(parentOf(x));
            //sib为红色时，将sib设置为黑色、x的父结点设置为红色，左旋转x的父结点，sib设置为x的父结点的右子结点
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
            //如果sib的两子结点都是黑色的，将sib设置为红色，x设置为s的父结点
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {//sib的两个子结点不都是黑色的
                //sib的的右子结点是黑色的，将sib的左子结点设置为黑色，sib结点设置为红色，右旋转sib结点，将sib设置为x的父结点的右子结点
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                //sib结点的颜色设置为x的父结点的颜色
                setColor(sib, colorOf(parentOf(x)));
                //x的父结点的颜色设置为黑色
                setColor(parentOf(x), BLACK);
                //sib的右子结点的颜色设置为黑色
                setColor(rightOf(sib), BLACK);
                //左旋转x的父结点
                rotateLeft(parentOf(x));
                //根结点赋值为x
                x = root;
            }
        } else { //x是其父结点的右子结点
            //sib为x的兄弟结点
            Entry<K,V> sib = leftOf(parentOf(x));
            //sib为红色时，设置sib颜色为黑色，x的父结点为红色，右旋转x的父结点，sib设置为x的父结点的左子结点
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }

            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }
    setColor(x, BLACK);
}

2.4 总结

参考资料

https://blog.csdn.net/zhangyuan19880606/article/details/51234420/
https://blog.csdn.net/qq_41786692/article/details/79940660

上一篇 下一篇

猜你喜欢

热点阅读