当前位置:首页 > 分类 > JAVA基础 > JDK源码-TreeMap

JDK源码-TreeMap

TreeMap使用的是红黑树结构,它的出现是为了解决二叉树在添加有序集合时导致二叉树变成了线性链表的问题。比如我们期望添加的元素为2,1,3,在使用二叉树时,2为根节点,1为2的左子节点,3为2的右子节点,一边一个,处于平衡状态,但如果我们添加的顺序是1,2,3,将导致1为根节点,2为1的右子节点,3为2的右子节点,如果添加的一直是右子节点,那结果呈现的就是线性链表。并不能凸显二叉树的查找优势,所以出现了红黑树,即在每个节点中添加了颜色属性。

NL}N0ID%VYKWW8`I1@O]~4L.png

红黑树特点如下:

        a,节点是红色或者黑色;

        b,根节点是黑色;

        c,叶子结点是黑色;

        d,每个红色节点的两个子节点都是黑色,即从每个叶子节点到跟的所有路径上不能有两个连续的红色节点。

        e,从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。


1,下面看下TreeMap类注释:

/**
 * A Red-Black tree based {@link NavigableMap} implementation.
 * The map is sorted according to the {@linkplain Comparable natural
 * ordering} of its keys, or by a {@link Comparator} provided at map
 * creation time, depending on which constructor is used.
 *
 * <p>This implementation provides guaranteed log(n) time cost for the
 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
 * operations.  Algorithms are adaptations of those in Cormen, Leiserson, and
 * Rivest's <em>Introduction to Algorithms</em>.

翻译如下:


基于红黑树的NavigableMap实现。

映射是根据其键的可比较的自然顺序排序的,或者根据使用的构造函数在创建映射时提供的比较器进行排序。

此实现为containsKey、get、put和remove操作提供了有保证的log(n)的时间开销。算法是对Cormen,Leiserson和Rivest的算法导论的改编。


这是红黑树被广泛使用的原因,只需要log(n)的时间开销,也就是速度快,效率高。但该类并不是线程安全的。同时也有ConcurrentModificationException和fail-fast实现,具体请参考ArrayList


2,成员变量如下:

    private final Comparator<? super K> comparator;

    private transient Entry<K,V> root;

    /**
     * The number of entries in the tree
     */
    private transient int size = 0;

    /**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;

    a,可自定义比较器comparator;

    b,Entry root为根节点,看下entry类定义

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;
}

节点内包含节点的key-value,left左子节点,right右子节点,parent父节点,颜色默认黑色;


3,构造器

 /**
     * Constructs a new, empty tree map, using the natural ordering of its
     * keys.  All keys inserted into the map must implement the {@link
     * Comparable} interface.  Furthermore, all such keys must be
     * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
     * a {@code ClassCastException} for any keys {@code k1} and
     * {@code k2} in the map.  If the user attempts to put a key into the
     * map that violates this constraint (for example, the user attempts to
     * put a string key into a map whose keys are integers), the
     * {@code put(Object key, Object value)} call will throw a
     * {@code ClassCastException}.
     */
    public TreeMap() {
        comparator = null;
    }
    
     public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

注释说到,key类必须实现Comparable接口。或者使用第二个构造器,参数传入比较器。


4,后面put方法初始化root或找到新节点的位置,难点在于后面调用的fixAfterInsertion方法。这个方法是为了保证上面提到的5点特征,即判断是否需要左旋或右旋。

左旋:把原节点摘下来,用原节点的右子节点替换原节点,原节点变成右子节点的左子节点,如果原右子节点存在左子节点,则把该左子节点当成原节点的右子节点

右旋:把原节点摘下来,用原节点的左子节点替换原节点,原节点变成左子节点的右子节点,如果原左子节点存在右子节点,则把该右子节点当成原节点的左子节点。右旋跟左旋一样,是左旋的逆过程。

LE5C[T6VRQ92I3%K2TP2V6G.png



代码还是很复杂的,简单加点注释。

	
	private void fixAfterInsertion(Node<K,V> x) {
		//默认新节点为红色,以此来调整上层树的平衡
		x.color = RED;
		//因为红色节点的子节点必须为黑色,所以此处只要父节点是红色就要一直调到变成黑色。
        while (x != null && x != root && x.parent.color == RED) {
        	//不管父节点是左子节点还是右子节点,做的事情都是一样。就是把父节点变成黑色,
        	//然后把父节点的父节点(父父节点)变成红色去找违反规则的节点,相当于父父节点是一个新插入的红色节点,循环
            //如果父节点是左子节点
        	if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Node<K,V> y = rightOf(parentOf(parentOf(x)));
                //而且右子节点也是红色,那我同时把两个红色变成黑色,两边黑色节点的数量还是相等的,父节点变成红色,再进循环判断是否需要修改上面节点的颜色。
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                //右子节点是黑色,如果此时我只把左子节点变成黑色,相当于左边新加了一个黑色,那左右两边黑色就不相等了,为了达到第一种情况,
                //这个时候如果新加的节点是左子节点,我们只需要先把他的父节点变成黑色,把父父节点变成红色,然后右旋,
               //结果为新加的黑色放到了父父节点,右子节点新加红色,左子节点为新加的红色节点,变成了第一种情况。ok
                } else {
                	//由于我们整体要向右旋,如果新节点是右子节点,
                	//那么在整体右旋结束后,新节点会变成右子节点的左子节点,而我们预期的结果是第一种情况,也就是左右都是红色,
                	//所以在此之前,我们要先把新加右节点变成加左节点,由于新加节点和它的父节点都是红色,所以直接用父节点左旋就可以了
                    if (x == rightOf(parentOf(x))) {
                        //x取父节点左旋
                    	x = parentOf(x);
                    	//左旋完成后,x变成了左子节点
                    	//左旋就是把原节点摘下来,用原节点的右子节点替换原节点,原节点变成右子节点的左子节点,
                    	//如果原右子节点存在左子节点,则把该左子节点当成原节点的右子节点
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    //右旋完成后,变成了上面左右子节点都是红色的情况。循环
                    //右旋跟上面左旋一样,是左旋的逆过程
                    //把原节点摘下来,用原节点的左子节点替换原节点,原节点变成做左子节点的右子节点
                    //如果原左子节点存在右子节点,则把该右子节点当成原节点的左子节点
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                Node<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;
    }


5,左旋右旋的实现,可对照上图理解。

private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }

    /** From CLR */
    private void rotateRight(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }