红黑树之—TreeMap源码分析

HashMap和TreeMap区别:都使用红黑树存储,HashMap不是顺序存储,TreeMap顺序存储

  • 如果需要逆序或者自定义顺序存储:可在创建TreeMap时传入一个自定义Comparator
//带有比较器的构造方法:初始化comparator属性;
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

TreeMap

  • put

首先找到新增节点的位置,其次在判断TreeMap是否处于平衡状态,若不平衡,则对节点进行着色、旋转操作;

//插入key-value:
public V put(K key, V value) {
    //根节点赋值给t:
    java.util.TreeMap.Entry<K,V> t = root;
    //如果根节点为null,则创建第一个节点,根节点
    if (t == null) {
        //对传入的元素进行比较,若TreeMap没定义了Comparator,则验证传入的元素是否实现了Comparable接口;
        compare(key, key);
        //根节点赋值:
        root = new java.util.TreeMap.Entry<>(key, value, null);
        //长度为1:
        size = 1;
        //修改次数+1
        modCount++;
        //直接返回:此时根节点默认为黑色
        return null;
    }

    //如果根节点不为null:
    int cmp;
    java.util.TreeMap.Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;

    //判断TreeMap中自定义比较器comparator是否为null:
    if (cpr != null) {
        // do while循环,查找新插入节点的父节点:
        do {
            // 记录上次循环的节点t,首先将根节点赋值给parent:
            parent = t;
            //利用自定义比较器的比较方法:传入的key跟当前遍历节点比较:
            cmp = cpr.compare(key, t.key);
            //判断结果小于0,处于父节点的左边 
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
            //判断结果大于0,处于父节点的右边 
                t = t.right;
            else
            //判断结果等于0,为当前节点,覆盖原有节点处的value:
                return t.setValue(value);
        // 只有当t为null,也就是找到了新节点的parent了
        } while (t != null);
    } else {
        //没有自定义比较器:
        if (key == null)
            //TreeMap不允许插入key为null,抛异常:
            throw new NullPointerException();
        //将key转换为Comparable对象:若key没有实现Comparable接口,此处会报错
        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);
    }

    //构造新增节点对象:
    java.util.TreeMap.Entry<K,V> e = new java.util.TreeMap.Entry<>(key, value, parent);

    //根据之前的比较结果,判断新增节点是在父节点的左边还是右边
    if (cmp < 0)
        // 如果新节点key的值小于父节点key的值,则插在父节点的左侧
        parent.left = e;
    else
        // 如果新节点key的值大于父节点key的值,则插在父节点的右侧
        parent.right = e;
    //核心方法:插入新的节点后,为了保持红黑树平衡,对红黑树进行调整
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
  • fixAfterInsertion方法

插入新的节点后,为了保持红黑树平衡,对红黑树进行调整


//核心方法:维护TreeMap平衡的处理逻辑;
private void fixAfterInsertion(java.util.TreeMap.Entry<K,V> x) {
    //首先将新插入节点的颜色设置为红色
    x.color = RED;
    //TreeMap是否平衡的重要判断,当不在满足循环条件时,代表树已经平衡;
    //x不为null,不是根节点,父节点是红色(三者均满足才进行维护):
    while (x != null && x != root && x.parent.color == RED) {
        //节点x的父节点 是 x祖父节点的左孩子:
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            //获取x节点的叔叔节点y:
            java.util.TreeMap.Entry<K,V> y = rightOf(parentOf(parentOf(x)));

            //叔叔节点y是红色:
            if (colorOf(y) == RED) {
                //将x的父节点设置黑色:
                setColor(parentOf(x), BLACK);  
                //将x的叔叔节点y设置成黑色:
                setColor(y, BLACK);
                //将x的祖父节点设置成红色:
                setColor(parentOf(parentOf(x)), RED);
                //将x节点的祖父节点设置成x(进入了下一次判断):
                x = parentOf(parentOf(x));
            } else {
                 //叔叔节点y不为红色:
                //x为其父节点的右孩子:
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //右旋:
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //节点x的父节点 是x祖父节点的右孩子:

            //获取x节点的叔叔节点y:
            java.util.TreeMap.Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            //判断叔叔节点y是否为红色:
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);12
                setColor(y, BLACK);5
                setColor(parentOf(parentOf(x)), RED);10
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //左旋:
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}
  • get

TreeMap底层是红黑树结构,而红黑树本质是一颗二叉查找树,所以在获取节点方面,使用二分查找算法性能最高;

//通过key获取对应的value:
public V get(Object key) {
    //获取TreeMap中对应的节点:
    java.util.TreeMap.Entry<K,V> p = getEntry(key);
    //获取节点的值:
    return (p==null ? null : p.value);
}

//通过key获取Entry对象:
final java.util.TreeMap.Entry<K,V> getEntry(Object key) {
    //TreeMap自定义比较器不为空,使用自定义比较器对象来获取节点:
    if (comparator != null)
        //获取节点:
        return getEntryUsingComparator(key);

    //如果key为null,则抛出异常,TreeMap中不允许存在为null的key:
    if (key == null)
        throw new NullPointerException();

    //将传入的key转换成Comparable类型,传入的key必须实现Comparable接口
    Comparable<? super K> k = (Comparable<? super K>) key;
    //获取根节点:
    java.util.TreeMap.Entry<K,V> p = root;

    // 使用二分查找方式,首先判断传入的key与根节点的key哪个大:
    while (p != null) {
        //传入的key与p节点的key进行大小比较:
        int cmp = k.compareTo(p.key);
        //传入的key小于p节点的key,则从根的左子树中搜索:
        if (cmp < 0)
            //左边
            p = p.left;
        else if (cmp > 0)
            //传入的key大于p节点的key,则从根的右边子树中搜索:
            //右边
            p = p.right;
        else
            //传入的key等于p节点的key,则直接返回当前节点:
            return p;
    }
    //以上循环没有找对对应的节点,则返回null:
    return null;
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/treemap.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!