图解TreeMap-源码分析

简介: 图解TreeMap-源码分析

转自:www.jianshu.com/p/0ae45f4e8…

一丶概述

上篇TreeMap聊了底层数据结构的红黑树,这篇就直接源码分析。

二丶脑图目录

image.png

image.png

三丶TreeMap源码分析

1.继承关系

image.png

image

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap继承于AbstractMap,实现了Map, Cloneable, NavigableMap, Serializable接口。

说明:

(1)TreeMap 继承于AbstractMap,而AbstractMap实现了Map接口,并实现了Map接口中定义的方法,减少了其子类继承的复杂度;

(2)TreeMap 实现了Map接口,成为Map框架中的一员,可以包含着key--value形式的元素;

(3)TreeMap 实现了NavigableMap接口,意味着拥有了更强的排序和元素搜索能力(平衡二叉树实现基础);

(4)TreeMap 实现了Cloneable接口,实现了clone()方法,可以被克隆;

(5)TreeMap 实现了Java.io.Serializable接口,支持序列化操作,可通过Hessian协议进行传输;

说一下NavigableMap接口

image.png

image

sortedMap主要是多提供比较器及前后元素的查找

image.png

image

NavigableMap接口就做了一个很好地拓展可查找左右元素的值(可以说是平衡二叉树的基础了)

public interface NavigableMap<K,V> extends SortedMap<K,V> {
    //返回小于key的第一个元素:
    Map.Entry<K,V> lowerEntry(K key);
    //返回小于key的第一个键:
    K lowerKey(K key);
    //返回小于等于key的第一个元素:
    Map.Entry<K,V> floorEntry(K key);
    //返回小于等于key的第一个键:
    K floorKey(K key);
    //返回大于或者等于key的第一个元素:
    Map.Entry<K,V> ceilingEntry(K key);
    //返回大于或者等于key的第一个键:
    K ceilingKey(K key);
    //返回大于key的第一个元素:
    Map.Entry<K,V> higherEntry(K key);
    //返回大于key的第一个键:
    K higherKey(K key);
    //返回集合中第一个元素:
    Map.Entry<K,V> firstEntry();
    //返回集合中最后一个元素:
    Map.Entry<K,V> lastEntry();
    //返回集合中第一个元素,并从集合中删除:
    Map.Entry<K,V> pollFirstEntry();
    //返回集合中最后一个元素,并从集合中删除:
    Map.Entry<K,V> pollLastEntry();
    //返回倒序的Map集合:
    java.util.NavigableMap<K,V> descendingMap();
    NavigableSet<K> navigableKeySet();
    //返回Map集合中倒序的Key组成的Set集合:
    NavigableSet<K> descendingKeySet();
    java.util.NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                       K toKey, boolean toInclusive);
    java.util.NavigableMap<K,V> headMap(K toKey, boolean inclusive);
    java.util.NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);
}

2.属性

/**
     * 比较器
     */
    private final Comparator<? super K> comparator;
    /**
     * 红黑树的红黑节点
     */
    private transient Entry<K,V> root;
    /**
     * 容量大小
     */
    private transient int size = 0;
    /**
     * 结构性修改
     */
    private transient int modCount = 0;
/**
 * 红黑树节点类型
 */
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    // 指向左子树
    Entry<K,V> left;
    // 指向右子树
    Entry<K,V> right;
    // 指向父节点
    Entry<K,V> parent;
    boolean color = BLACK;
}
    // 红黑树节点-红颜色
    private static final boolean RED   = false;
    // 红黑树节点-黑颜色
    private static final boolean BLACK = true;

3.构造方法

/**
 * 默认构造器,使用默认排序机制
 */
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);
}
/**
 * 构造SortedMap对象为TreeMap,并使用SortedMap的比较器
 */
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) {
    }
}

4.put方法

/**
 * 红黑树的put操作大体上分为两步:构建二叉排序树,平衡二叉排序树
 * 构建的时候,如果用户自定义了比较器,则会按照用户定义的规则来,否则将按照默认的比较规则来插入数据;
 */
public V put(K key, V value) {
    // 二叉树当前节点
    Entry<K,V> t = root;
    // 如果二叉树为null,直接插入
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    // 使用cmp来表示排序返回的结果
    int cmp;
    // 父节点
    Entry<K,V> parent;
    // 比较器
    Comparator<? super K> cpr = comparator;
    // 如果比较器不为空,按照用户指定比较器进行循环比较,确定元素插入位置
    if (cpr != null) {
        do {
            parent = t;
            // 对key进行比较
            cmp = cpr.compare(key, t.key);
            // 比较结果小于0,表示新增节点的key小于当前节点的key,则以当前节点的左子节点作为新的当前节点
            if (cmp < 0)
                t = t.left;
                // 比较结果大于0,表示新增节点的key大于当前节点的key,则以当前节点的右子节点作为新的当前节点
            else if (cmp > 0)
                t = t.right;
                // 比较结果等于0,说明key相等,覆盖旧值,返回新值
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 如果比较器为null
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        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
        parent.right = e;
    // 插入完成,对二叉树进行平衡操作
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

4.1.put方法流程图

image.png

image

4.2.情况分析

情况1:插入的是根节点,由于原树是空树

策略:直接把此节点涂为黑色

情况2:如果插入的节点的父节点是黑色

策略:由于此不会违反性质2和性质4,红黑树没有被破坏,所以此时什么也不做

情况3:有两个子节点

情况3.1:当前节点的父节点是红色且祖父节点的另一个子节点(叔叔节点)是红色

策略:将父节点和叔叔节点涂黑,祖父节点涂红同时指向当前节点

情况3.2:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子

策略:当前节点的父节点做为新的当前节点,以新当前节点为支点重新旋转

情况3.3:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的左孩子

策略:父节点变为黑色,祖父节点变为红色,以祖父节点为支点重新旋转

4.3.put示例:

/**
 * 对于新节点的插入有如下三个关键地方:
 *      1、插入新节点总是红色节点;
 *      2、如果插入节点的父节点是黑色, 能保持性质(性质4);
 *      3、如果插入节点的父节点是红色, 性质被破坏,通过旋转和重新着色维护红黑树性质。
 *      4、换言之,性质1-3都好实现,复杂的是要实现性质4-5(删除操作一样)
 */
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;//新增元素默认红色,后面根据所在位置重新着色(比较有趣的是Entry构造器默认是BLACK)
    //循环 直到 x不是根节点,且x的父节点不为红色  
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//父节点为祖父节点左子
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));//叔叔节点(右节点)
        /* 
         * 情况3.1:父节点是红色且祖父节点的另一个子节点(叔叔节点)是红色
         * 策略:将父节点和叔叔节点涂黑,祖父节点涂红同时指向当前节点
         */
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
            /* 
            * 情况3.2:父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子
            * 策略:当前节点的父节点做为新的当前节点,以新当前节点为支点左旋
            * 这时情况会转变为3.2(当前节点是其父节点的左子)
            */
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
            /* 
            * 情况3.3:父节点是红色,叔叔节点是黑色,当前节点是其父节点的左子
            * 策略:将父节点和叔叔节点涂黑,祖父节点涂红,以祖父节点右旋
            */
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //父节点为祖父节点右子 操作从左换成右,相当于对称操作
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                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;//红黑树性质(2):根节点是黑色
}

以下图红黑树为例

image.png

image

现在我们要增加一个节点50,放在节点47的右子树上。

image.png

image

新增节点和父节点冲突,叔父节点是红色的,进行变色操作,把父亲节点和叔父节点都变成黑色,祖父节点变成红色,然后再对祖父节点进行调整。

情况3.1:

image.png

image

叔父节点y是黑色的,并且x是右孩子,先进行左旋转,把红色节点转移到左分支。

情况3.2:

image.png

image

再把x的父节点变黑,祖父节点变红,然后把祖父节点右旋转。

情况3.3:

image.png

image

最多两次旋转即可解决冲突。

5.remove方法

/**
 * 这里删除操作其实很微妙,并不是直接删除,而是用被删除节点的后继节点来代替被删掉的节点,然后修复被删除节点的结构来进行操作的
 */
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    // p节点为要删除的节点,如果p节点的左右子节点都不为空
    if (p.left != null && p.right != null) {
        // 找到p节点的后继节点,这里不是直接删除p节点,而是将p的后继节点来代替要删除的节点,然后再进行修复操作
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children
    // 开始修复操作
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;
        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;
        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(p);
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}
/**
 * 获取后继节点,其实这是一个类似中序遍历的方式
 */
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        // 节点的右子树不为空,后继结点就是右子树的最左节点
        // 因为最左子树是右子树的最小节点
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 右子树为空,则寻找当前节点左子树的第一个父节点
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

5.1.remove方法流程图

image.png

image

5.2.fixAfterDeletion删除节点的调整函数(重点)

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {  //节点x不是根节点并且是黑色才进行处理
        if (x == leftOf(parentOf(x))) { //x是其父节点的左孩子
            Entry<K,V> sib = rightOf(parentOf(x));  //sib表示x的兄弟节点
            /**
             * 如果兄弟节点是红色的,那么父节点肯定是黑色的
             * 把兄弟节点变黑,父节点变红,然后对父节点左旋转
             * 兄弟节点变成父节点,并且到右子树的黑色节点数量不变(由1黑1红变成1黑)
             *
             * 即情景1,在x节点上增加一个父节点(红色)。
             */
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x)); //旋转之后重新赋值兄弟节点sib,原sib变成x的祖父节点(见左旋转动图)
            }
            /**
             * 进行上一步的判断处理后,此时兄弟节点肯定是黑色的。
             * 如果兄弟节点的孩子节点都是黑色的,我们就可以把兄弟节点变红。
             * 然后while循环继续调整其父节点,即情景2。
             */
            if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            }
            //兄弟节点不能直接变红的情况下,即情景3
            else {
                /**
                 * 如果兄弟节点的左孩子是红色,右孩子是黑色
                 * 兄弟节点的左孩子变黑,兄弟节点变红,对兄弟节点右旋转,把红色节点转移到右分支
                 */
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    //重新赋值兄弟节点
                    sib = rightOf(parentOf(x));
                }
                /**
                 * 经过上一步判断处理,兄弟节点是黑色,兄弟节点的左孩子是黑色,兄弟节点的右孩子是红色,
                 * 把兄弟节点变成父节点的颜色,兄弟节点的右孩子变成黑色(不破坏右分支的规则),父节点变成黑色,对父亲节点左旋转,
                 * 主要就在x节点的上面增加了一个黑色的父节点,即情景3,调整结束。
                 */
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        }
        // x节点是其父节点的右孩子,调整方法和上面的对称。
        else {
            Entry<K,V> sib = leftOf(parentOf(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);
}

算法思想:我们要删除一个黑色节点,这会破坏规则5,调整有3种情景:

(1)如果兄弟节点是红色的,经过变色旋转,在x节点上面增加一个红色的父亲节点,并且不破坏其他分支的黑色节点数量。

兄弟节点是黑色的,

(2)如果兄弟节点的子节点都是黑色的,直接把黑色节点变红,即减少兄弟分支的黑色节点数量,然后对其父节点进行调整;

兄弟节点是黑色的,但其有红色的孩子节点,不能直接变红。

(3)如果左孩子是红色节点,经过变色和右旋转把红色节点移到右边。此时再经过变色,并对x的父节点进行左旋转,在x节点的上面增加一个黑色节点,并且不破坏其他分支的黑色节点数量,调整结束。

5.3.示例

删除的节点只有一个子节点(删除390),根据上面的引申规则,这个节点肯定是黑色,子节点是红色

image.png

image

删除红色的节点并且没有子节点(删除833)


image.png

image

删除黑色的节点并且没有子节点(删除22)

(1)兄弟节点是红色的情况


image.png

image

变色+旋转,给x节点增加一个红色的父亲节点

image.png

image

此时x的新兄弟节点是黑色,并且孩子节点全是黑色(叶子节点是黑色的),把兄弟节点变色,然后x指向父节点,while循环继续调整。

image.png

image

节点是红色,跳出循环。循环外把该节点变黑。

image.png

image

方法返回后,deleteEntry方法把22节点删除,整个过程结束。

image.png

image

(2)兄弟节点是黑色的情况

上面是旋转变化过程中其实已经遇见了这种情况,并且兄弟节点的孩子节点全是黑色,可以直接变色处理,下面来看一下,兄弟节点是黑色,并且有孩子节点是红色的情况

继续上面的红黑树,下面删除65节点


image.png

image

兄弟节点是黑色,并且有红色的孩子节点,针对x是左孩子的情况下,如果红色节点是左孩子,需要通过旋转操作移到右边


image.png

image

然后再进行变色旋转操作,给x节点增加一个黑色的父节点。x = root结束循环。


image.png

image

方法返回,deleteEntry方法把65节点删除,整个过程结束。

删除节点有两个孩子节点的情况。


image.png

image

删除节点55,该节点有两个孩子节点,deleteEntry方法中会查找继承者节点,即图中的65节点,把65节点的key和value赋值给55节点,然后转化为删除65节点。


image.png

image

因为继承者节点没有左孩子节点,所以这个问题又变成了删除一个孩子节点或者无孩子节点的问题。(参照上面)




目录
相关文章
|
7月前
|
Java
图解HashMap(二)
图解HashMap(二)
58 0
|
7月前
|
存储 算法 Java
图解HashMap(一)
图解HashMap(一)
69 0
|
存储 Java
每日一道面试题之HashSet的实现原理~
每日一道面试题之HashSet的实现原理~
|
7月前
|
设计模式 存储 缓存
LinkedHashMap源码学习
LinkedHashMap源码学习
LinkedHashMap源码学习
|
7月前
|
存储 缓存 算法
图解LinkedHashMap原理
图解LinkedHashMap原理
68 0
|
存储 算法 Java
【Java集合框架 二】HashMap源码分析
【Java集合框架 二】HashMap源码分析
89 0
HashMap源码学习:红黑树原理详解
HashMap源码学习:红黑树原理详解
68 0
|
存储 安全 Java
最通俗易懂的 HashMap 源码分析解读
最通俗易懂的 HashMap 源码分析解读
153 0
最通俗易懂的 HashMap 源码分析解读
|
存储 Java 索引
Java集合干货——LinkedList源码分析
前言 在上篇文章中我们对ArrayList对了详细的分析,今天我们来说一说LinkedList。他们之间有什么区别呢?最大的区别就是底层数据结构的实现不一样,ArrayList是数组实现的(具体看上一篇文章),LinedList是链表实现的。
1163 0
|
Java
TreeMap 源码分析
一、简介 TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 containsKey、get、put 和 remove 操作,效率很高。
1064 0