精华内容
下载资源
问答
  • } } 二、TreeMap实现原理 1、TreeMap的基本概念: TreeMap集合是基于红黑树(Red-Black tree)的 NavigableMap实现。TreeMap继承AbstractMap,实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap...

    一、红黑树介绍

    1、R-B Tree概念

    红黑树(Red Black Tree简称R-B Tree 是一种自平衡二叉查找树,它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

    红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值。

    除了具备该特性之外,红黑树还包括许多额外的信息。

    2、红黑树5个特性

    (1) 每个节点或者是黑色,或者是红色。

    (2) 根节点是黑色。

    (3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]

    (4) 如果一个节点是红色的,则它的子节点必须是黑色的。

    (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

    关于它的特性,需要注意的是:

    第一,特性(3)中的叶子节点,是只为空(NILnull)的节点。

    第二,特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

    这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

    要知道为什么这些特性确保了这个结果,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

    3、红黑树的操作

    红黑树的基本操作是添加删除旋转。在对红黑树进行添加或删除后,会用到旋转方法。为什么呢?道理很简单,添加或删除红黑树中的节点之后,红黑树就发生了变化,可能不满足红黑树的5条性质,也就不再是一颗红黑树了,而是一颗普通的树。而通过旋转,可以使这颗树重新成为红黑树。简单点说,旋转的目的是让树保持红黑树的特性。
    旋转包括两种:左旋 右旋

    3.1 左旋

    左旋的过程是将x的右子树绕x逆时针旋转,使得x的右子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

    TreeMap中左旋代码如下:

    //Rotate Left
    private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> r = p.right;
    		//1.将B子树与x(p)链接
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            //2.将y(r)与x(p)的父树链接
            r.parent = p.parent;
            if (p.parent == null) //根节点
                root = r;
            else if (p.parent.left == p)  // x(p)原为左支树
                p.parent.left = r;
            else
                p.parent.right = r;     // x(p)原为左支树
            //3.将y(r)与x(p)链接
            r.left = p;
            p.parent = r;
        }
    }
    

    3.2 右旋

    右旋的过程是将x的左子树绕x顺时针旋转,使得x的左子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

     

    TreeMap中右旋代码如下:

    //Rotate Right
    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;
        }
    }
    

    二、TreeMap实现原理

    1、TreeMap的基本概念:

    TreeMap集合是基于红黑树(Red-Black tree)的 NavigableMap实现。TreeMap继承AbstractMap,实现NavigableMapCloneableSerializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合, NavigableMap(更多)则意味着它支持一系列的导航方法,具备针对给定搜索目标返回最接近匹配项的导航方法 。实现SortedMap,支持遍历时按元素的大小有序遍历。

    该集合最重要的特点就是可排序,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator比较器进行排序,具体取决于使用的构造方法。

    根据上一条,我们要想使用TreeMap存储并排序我们自定义的类(如User类),那么必须自己定义比较机制:一种方式是User类去实现java.lang.Comparable接口,并实现其compareTo()方法。另一种方式是写一个类(如MyCompatator)去实现java.util.Comparator接口,并实现compare()方法,然后将MyCompatator类实例对象作为TreeMap的构造方法参数进行传参(当然也可以使用匿名内部类)。

    TreeMap核心源码的理解,实质上就是对“如何维持红黑树数据结构的特性的理解”。下面的解析,都会以红黑树特性为引子来深入剖析TreeMap源码。

    1、内部成员数据结构

    TreeMap中包含了如下几个重要的属性:

    public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
    	//比较器,因为TreeMap是有序的,通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
            private final Comparator<? super K> comparator;
            //红-黑树根节点
            private transient Entry<K,V> root = null;
            //容器大小
            private transient int size = 0;
            //树结构被修改次数
            private transient int modCount = 0;
            //红黑树的节点颜色--红色
            private static final boolean RED = false;
            //红黑树的节点颜色--黑色
            private static final boolean BLACK = true;
            ...
    
    }
    

    TreeMap采用红黑树的数据结构来实现。树节点Entry实现了Map.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信息,也就是三查。

    2、构造方法

    // 1,无参构造方法
    public TreeMap() {   
            comparator = null; // 默认比较机制(自然比较)
    }
    
    // 2,自定义比较器的构造方法
    public TreeMap(Comparator<? super K> comparator) {
            this.comparator = comparator;
    }
    
    // 3,构造已知Map对象为TreeMap
    public TreeMap(Map<? extends K, ? extends V> m) {  
            comparator = null; // 默认比较机制
            putAll(m);
    }
    
    // 4,构造已知的SortedMap对象为TreeMap
    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) {
            }
    }
    

    3、get()方法

    get(Object key)方法根据指定的key值返回对应的value,该方法调用了getEntry(Object key)得到相应的entry,然后返回entry.value。因此getEntry()是方法的核心。方法思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找,直到找到满足k.compareTo(p.key) == 0entry

    public V get(Object key) {//根据key值查找value
    
            Entry<K,V> p = getEntry(key);
            return (p==null ? null : p.value);
    }
    
    //根据key值查找元素方法;final方法不允许被子类重写  
    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance        
        if (comparator != null)//存在比较器,按比较器进行比较查找            
            return getEntryUsingComparator(key);        
        if (key == null)//key值为null抛空指针异常            
            throw new NullPointerException();
        
        //没有比较强,自然排序比较        
        Comparable<? super K> k = (Comparable<? super K>) key;        
        Entry<K,V> p = root;        
        while (p != null) {
            //从root开始循环查找,一直到叶子节点            
            int cmp = k.compareTo(p.key); //采用key的compareTo方法进行比较            
            if (cmp < 0) //小于继续查找左边                
                p = p.left;            
            else if (cmp > 0) //大于继续查找右边                
                p = p.right;            
            else                
                return p;//等于返回当前元素        
        }        
        return null;    
    }
    

    前面只是集合通用的简单知识,下面才是重点,了解红黑树增加、删除节点的核心算法


    4、put方法

    红黑树在新增节点过程中比较复杂,一般经历三个步骤。第一步: 将红黑树当作一颗二叉查找树,将节点插入。第二步:将插入的节点着色为"红色"。第三步: 通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。下面会以红黑树特性为基础解析put方法源码,以帮助理解代码的设计。

    4.1 红黑树增加节点的特性

    对于新节点的插入有如下四个关键地方:

    1、插入新节点会对map做一次查找。

    2、插入新节点总是红色节点 。      

    3、如果插入节点的父节点是黑色, 能维持性质 。      

    4、如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质 。      

    红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一颗二叉查找树的事实。

    为什么着色成红色,而不是黑色呢?将插入的节点着色为红色,不会违背"特性(5)"!少违背一条特性,就意味着我们需要处理的情况越少。接下来,就要努力的让这棵树满足其它性质即可;满足了的话,它就又是一颗红黑树了。

    第二步中,将插入节点着色为"红色"之后,不会违背"特性(5)"。那它到底会违背哪些特性呢?

    对于"特性(1)",显然不会违背了。因为我们已经将它涂成红色了。

    对于"特性(2)",显然也不会违背。在第一步中,我们是将红黑树当作二叉查找树,然后执行的插入操作。而根据二叉查找数的特点,插入操作不会改变根节点。所以,根节点仍然是黑色。

    对于"特性(3)",显然不会违背了。这里的叶子节点是指的空叶子节点,插入非空节点并不会对它们造成影响。

    对于"特性(4)",是有可能违背的!

    那接下来,想办法使之"满足特性(4)",就可以将树重新构造成红黑树了。

    这里将红黑树的五点规定再贴一遍:

    (1)每个节点都只能是红色或者黑色

    (2)根节点是黑色

    (3)每个叶节点(NIL节点,空节点)是黑色的。

    (4)如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

    (5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

    4.2 红黑树增加节点的情况

    假设我们这里有一棵最简单的树,我们规定新增的节点为新、它的父节点为父、父的兄弟节点为叔、父的父节点为祖父。

    1)情况1:无父

    若新插入的节点N没有父节点,则直接当做根据节点插入即可,同时将颜色设置为黑色。

    2)情况2 :黑父

    插入节点后可维持红黑树性质。红黑树插入的新节点肯定为原来的某支的末尾,时颜色为红色,由于根据规则四它会存在两个黑色的叶子节点,值为null,满足规则3和4。同时新增节点为红色,所以通过它的子节点的路径依然会保存着相同的黑色节点数,同样满足规则5。

    3)情况3 红父、红叔

    插入节点后不能维持红黑树性质4,故可能需要进行着色或旋转操作。

    下面假设父亲为左节点进行分析(右节点的情况类似,只是旋转方向相反)。

    根据红黑树的性质5可推得,红叔肯定没有孩子,因为既然可以插入,那父原本也没孩子。插入新节点只破坏了颜色的性质,所以将父、叔节点变黑、祖节点变红。这时由于经过节点父、叔的路径都必须经过G所以在这些路径上面的黑节点数目还是相同的。但是经过上面的处理,可能G节点的父节点也是红色,这个时候我们需要将G节点当做新增节点迭代处理。也就是:进行重新着色再按祖向上继续判断即可。

    4)情况4:红父、黑叔(Null)或缺失、插入左节点

    由于红父没有孩子,根据红黑树的性质5可推得,该情况的黑叔实际只可能为空的NIL节点。插入新节点不仅破坏了颜色的性质,还破坏了平衡,故需要进行重新着色和旋转。此时新节点的左右位置影响具体的旋转方式。

    插入左节点这种情况有可能是由于情况五而产生的,也有可能不是。对于这种情况它违反了规则4,所以我们先将父P、组G节点的颜色进行交换,但这样并不平衡,违反了规则5(黑色节点数相同),所以还需要以祖G节点为中心进行右旋转,在旋转后产生的树中,节点父P是新节点N、祖G的父节点,这样就满足开始时所有的路径经过祖G节点到他们叶子的黑色节点数一样,满足规范5,同时由于颜色相同,也不用再向上迭代。即重新着色并按祖右旋

    5)情况4:红父、黑叔(Null)或缺失、插入右节点

    对于插入位置为右节点这种情况,我们对新增节点N、父节点P进行一次左旋转。这里所产生的结果其实并没有完成,还不是平衡的(违反了规则四),这是我们需要进行情况4的操作。即按父左旋,并指向父继续判断(即接着按情况3处理)

    4.3 put方法源码解析

    put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于getEntry()方法;如果没有找到则会在红黑树中插入新的entry,如果插入之后破坏了红黑树的约束,还需要进行调整(旋转,改变某些节点的颜色)。put算法时间复杂度约为O(log2N),并且其与普通查找二叉树比较,插入的旋转次数很少。

    注意看注释

    public V put(K key, V value) {
        //用t表示二叉树的查找入口,即根节点
        Entry<K,V> t = root;
        //t为null表示一个空树,即TreeMap中没有任何元素,直接插入
        if (t == null) {
            //检查key的类型
      	compare(key, key); // type (and possibly null) check
      	//将新的key-value键值对创建为一个Entry节点,并将该节点赋予给root
     	root = new Entry<>(key, value, null);
      	size = 1;
      	//修改次数 + 1
      	modCount++;
     	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
      	    //比较新增节点的key和当前节点key的大小
      	    cmp = cpr.compare(key, t.key);
      	    //新增节点的key小于当前节点的key,则以当前节点的左子节点作为新的当前节点
      	    if (cmp < 0)
      	        t = t.left;
      		//新增节点的key大于当前节点的key,则以当前节点的右子节点作为新的当前节点
     	    else if (cmp > 0)
     		t = t.right;
     		//两个key值相等,则新值覆盖旧值,并返回新值
      	    else
      		return t.setValue(value);
     	} while (t != null);
        }
        //如果cpr为空,则采用默认的排序算法进行创建TreeMap集合
        else {
            if (key == null) //key值为空抛出异常
      	    throw new NullPointerException();
     	    /* 下面处理过程和上面一样 */
      	    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;
      	//如果新增节点的key大于parent的key,则当做右子节点
      	else
      		parent.right = e;
      	/*
     	*上面已经完成了排序二叉树的的构建,将新增节点插入该树中的合适位置
            *下面fixAfterInsertion()方法就是对这棵树进行调整、平衡,具体过程参考上面的4种情况
            */
            fixAfterInsertion(e);
      	//TreeMap元素数量 + 1
            size++;
            //TreeMap容器修改次数 + 1
            modCount++;
            return null;
        }
    }
    
       

    fixAfterInsertion(e),调整的过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作。代码如下:

    /**
    * 新增节点后的修复操作
    * x 表示新增节点
    */
    private void fixAfterInsertion(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)));
        	    //如果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 == 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;
    }
    

    5、remove()方法

    对于红黑树的增加节点而言,删除显得更加复杂,使原本就复杂的红黑树变得更加复杂。同时删除节点和增加节点一样,同样是找到删除的节点,删除之后调整红黑树。

    5.1 红黑树删除节点的特性

    真正删除的节点并不一定是指定的节点,当其有两个孩子时,会查找下一个节点作为真正的删除点,这里先称为后继节点,由迭代循环方法可知,该节点一定是没有孩子或只有一个孩子。

    ①该节点如果为红色,必然为叶子节点

    ②该节点如果为黑色,只可能有一个红色孩子或无孩子

    这是因为删除节点并不是直接删除,而是被其后继(树种比大于D的最小的那个元素)替代。这是通过走了“弯路”的方式来删除的:找到被删除的节点D的子节点F,用F来替代D,不是直接删除D,因为D被F替代了,直接删除F即可,若F还有子节点就迭代。所以这里就将删除父节点D的事情转变为了删除子节点F的事情,这样处理就将复杂的删除事件简单化了。子节点F的规则是:右分支最左支树,或者 左分支最右边祖树。

    那被删除节点有没有后继节点就会出现不同的删除方式:

    ① 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。

    ② 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。

    ③ 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。在这里,后继节点相当于替身,在将后继节点的内容复制给"被删除节点"之后,再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了,下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然"后继节点"不可能双子都非空,就意味着"该节点的后继节点"要么没有儿子,要么只有一个儿子” (如下图)。若没有儿子,则按"情况① "进行处理;若只有一个儿子,则按"情况② "进行处理。

    并且,该节点如果为红色,必然为叶子节点,即无儿子,因为如果该节点的子节点为黑,则必然存在令一个子节点(两个儿子不符合迭代查询的结果),否则违反黑节点数原则(规定5),为红,则违反“颜色”原则(规定4)。上下图对比理解。

    红-黑二叉树删除节点,最大的麻烦是要保持各分支黑色节点数目相等。 因为是删除,所以不用担心存在颜色冲突问题(值的替换)——插入才会引起颜色冲突。

    5.2 红黑树删除节点的情况

    红黑树删除节点同样会分成几种情况,这里是按照待删除节点有几个儿子的情况来进行分类:

    1)情况1:无子节点(红色节点)

    这种情况对该节点直接删除即可,不会影响树的结构。因为该节点为叶子节点它不可能存在子节点-----如子节点为黑,则违反黑节点数原则(规定5),为红,则违反“颜色”原则(规定4)。

    2)情况2:有一个子节点

    这种情况处理也是非常简单的,用子节点替代待删除节点,然后删除子节点即可。

    3)情况3:有两个子节点

    这种情况可能会稍微有点儿复杂。它需要找到一个后继节点N来替代本来该被删除的节点(覆盖值),然后真正删除N(N的删除方法上面已讲到),再完善红黑树的约束,这就牵扯到N的父与兄了。它主要分为四种情况。

    • N的兄弟节点W为红色
    • N的兄弟w是黑色的,且w的俩个孩子都是黑色的。
    • N的兄弟w是黑色的,w的左孩子是红色,w的右孩子是黑色。
    • N的兄弟w是黑色的,且w的右孩子是红色的。

    4)情况3.1:N的兄弟节点W为红色

    此情况红兄必然有两个孩子,删除后同时影响平衡及颜色性质,故需要重新着色及旋转操作。策略改变兄节点W、父节点P的颜色,然后进行一次左旋转。这样处理就可以使得红黑性质得以继续保持。N的新兄弟是旋转之前w的某个孩子,为黑色。这样处理后将情况3.1、转变为3.2、3.3、3.4中的一种。如下:

    5)情况3.2:N的兄弟节点w是黑色的,且w只有一个右孩子

    该情况需要重新着色及旋转

    6)情况3.3:N的兄弟节点w是黑色的,且w只有一个左孩子

    该情况需要重新着色,然后以兄为中心右旋转得出3.2的情况

    5.3 remove()方法源码分析

    remove(Object key)的作用是删除key值对应的entry,该方法首先通过上文中提到的getEntry(Object key)方法找到key值对应的entry,然后调用deleteEntry(Entry<K,V> entry)删除对应的entry。由于删除操作会改变红黑树的结构,有可能破坏红黑树的约束条件,因此有可能要进行调整。

    public V remove(Object key) {
       Entry<K,V> p = getEntry(key);//先找到需要删除的元素
       if (p == null)
       	return null;
       V oldValue = p.value;
       deleteEntry(p);
       return oldValue;
    }

    这里重点放deleteEntry()上,该函数删除指定的entry并在红黑树的约束被破坏时进行调用fixAfterDeletion(Entry<K,V> x)进行调整。

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

      modCount++; //修改次数 +1

      size--; //元素个数 -1

      /*

      * 被删除节点的左子树和右子树都不为空,那么就用 p节点的中序后继节点代替 p 节点

      * successor(P)方法为寻找P的替代节点。规则是右分支最左边,或者 左分支最右边的节点

      * ---------------------(1)

      */

      if (p.left != null && p.right != null) {

             Entry<K,V> s = successor(p);

                  //仅仅是Key-Value键值对的替换

             p.key = s.key;

             p.value = s.value;
                         //p指向后继节点,后续都是对后继节点s进行操作

             p = s;

      }

     

      //先删除后继节点,replacement为替代节点(后继节点孩子),如果P的左子树存在那么就用左子树替代,否则用右子树替代

      Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        /*

      * 删除节点,分为上面提到的三种情况

      * -----------------------(2)

      */

      //如果替代节点不为空

      if (replacement != null) {

             replacement.parent = p.parent;

             /*

             *replacement来替代P节点

             */

             //若P没有父节点,则跟节点直接变成replacement

             if (p.parent == null)

                    root = replacement;

             //如果P为左节点,则用replacement来替代为左节点

             else if (p == p.parent.left)

                    p.parent.left = replacement;

             //如果P为右节点,则用replacement来替代为右节点

             else

                    p.parent.right = replacement;

        //同时将P节点从这棵树中剔除掉

             p.left = p.right = p.parent = null;

        /*

             * 若P为红色直接删除,红黑树保持平衡

             * 但是若P为黑色,则需要调整红黑树使其保持平衡

              */

             if (p.color == BLACK)

             fixAfterDeletion(replacement);

    } else if (p.parent == null) { //p没有父节点,表示为P根节点,直接删除即可

             root = null;

    } else { //P节点不存在子节点,直接删除即可

             if (p.color == BLACK) //如果P节点的颜色为黑色,对红黑树进行调整

                    fixAfterDeletion(p);

        //删除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;

             }

      }

    }

    (2)处是删除该节点过程。它主要分为上面提到的三种情况,它与上面的if…else if… else一一对应 。如下:      

    1、有两个儿子。这种情况比较复杂,但还是比较简单。上面提到过用子节点C替代代替待删除节点D,然后删除子节点C即可。      

    2、没有儿子,即为叶结点。直接把父结点的对应儿子指针设为NULL,删除儿子结点就OK了。      

    3、只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子,删除儿子结点也OK了。

    删除完节点后,就要根据情况来对红黑树进行复杂的调整:fixAfterDeletion()。

    private void fixAfterDeletion(Entry<K,V> x) {

      // 删除节点需要一直迭代,直到 x 不是根节点,且 x 的颜色是黑色

      while (x != root && colorOf(x) == BLACK) {

             if (x == leftOf(parentOf(x))) { //若X节点为左节点

                    //获取其兄弟节点

                    Entry<K,V> sib = rightOf(parentOf(x));

               /*

                    * 如果兄弟节点为红色----(情况3.1)

                    * 策略:改变W、P的颜色,然后进行一次左旋转

                    */

                    if (colorOf(sib) == RED) {

                           setColor(sib, BLACK);

                           setColor(parentOf(x), RED);

                           rotateLeft(parentOf(x));

                           sib = rightOf(parentOf(x));

                    }

               /*

                    * 若兄弟节点的两个子节点都为黑色----(情况3.4)

                    * 策略:将兄弟节点变成红色

                    */

                    if (colorOf(leftOf(sib)) == BLACK &&

                           colorOf(rightOf(sib)) == BLACK) {

                           setColor(sib, RED);

                           x = parentOf(x);

                    }

                    else {

                           /*

                           * 如果兄弟节点只有右子树为黑色----(情况3.2)

                           * 策略:将兄弟节点与其左子树进行颜色互换然后进行右转

                           * 这时情况会转变为3.3

                           */

                           if (colorOf(rightOf(sib)) == BLACK) {

                                  setColor(leftOf(sib), BLACK);

                                  setColor(sib, RED);

                                  rotateRight(sib);

                                  sib = rightOf(parentOf(x));

                           }

                           /*

                           *----情况3.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);

      }

    展开全文
  • TreeMap实现原理

    2019-08-10 15:04:10
    实现了SortedMap接口,是一个有序的集合,是一个红黑树接口,每个key-vlaue作为红黑树的节点,没有指定顺序则是根据key执行自然排序。 1、继承了AbstractMap类,实现了接口 implements NavigableMap<K,V>, ...

    实现了SortedMap接口,是一个有序的集合,是一个红黑树接口,每个key-vlaue作为红黑树的节点,没有指定顺序则是根据key执行自然排序。

    1、继承了AbstractMap类,实现了接口

    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

    可以自然排序,可以定制排序,Entry root = null  红黑树的根节点;size存放键值对的数量。

    1)自然排序:所有的key必须实现Comparable接口,所有的key都是同一类的对象;

    2)定制排序:创建TreeMap对象传入一个Comparator对象,改对象负责key进行排序,采用定制排序不要去key实现comparable接口。

    2、其方法

    put():
    get():根据不同的排序比较方法定位需要的数据,检索速度时间复杂度为O(log(n));

    remove():

    3)红黑树

    是一个更高效检索二叉树,每个节点只能是红色或者黑色;根节点永远是黑色;所有叶子的子节点都是空节点,并且都是黑色;每个红色节点的两个子节点都是黑色,没有连续的红色节点;从人一个节点到其子树中的每个叶子节点的路径中所包含相同数量的黑色节点。

    1)插入节点

    默认为红色的节点插入到树中

    情形1:新插入的节点是红黑树的根节点,没有父节点,无需任何操作,如果上层有,直接改变为黑色;

    情形2:新节点的父节点颜色是黑色,则直接插入;

    情形3:新节点的父节点(左孩子节点)颜色是红色的,而父节点的兄弟节点颜色是红色的。

     

    展开全文
  • TreeMap是一个线程不安全,有序的键值对集合,因为TreeMap实现了SotredMap接口。底层是一个红黑树的数据结构,每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器,则根据key执行...

    一、简介

    TreeMap是一个线程不安全,有序的键值对集合,因为TreeMap实现了SotredMap接口。底层是一个红黑树的数据结构,每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器,则根据key执行自然排序。这点会在接下来的代码中做说明,如果指定了比较器则按照比较器来进行排序。
    此外,TreeMap的Key是不能为null的,因为要实现排序。而Value是允许为null的。

    二、数据结构

    /**
    * TreeMap
    */
    public class TreeMap<K,V>
        extends AbstractMap<K,V>
        implements NavigableMap<K,V>, Cloneable, java.io.Serializable
    {
        // 创建Map传进去的比较器,不传为null
        private final Comparator<? super K> comparator;
    	// 存储根节点
        private transient TreeMapEntry<K,V> root;
        // 大小
        private transient int size = 0;
        // 修改次数
        private transient int modCount = 0;
    }
    

    接下来看看TreeMapEntry的数据结构,形成红黑树和存储最重要的实体类

    /**
    * TreeMap的静态内部类TreeMapEntry
    */
    static final class TreeMapEntry<K,V> implements Map.Entry<K,V> {
    		// 保存我们存储的Key
            K key; 
            // 保存我们存储的Value
            V value; 
            // 当前节点的左子节点
            TreeMapEntry<K,V> left; 
            // 当前节点右子节点
            TreeMapEntry<K,V> right; 
            // 当前节点父节点
            TreeMapEntry<K,V> parent; 
            // 红黑树的节点颜色
            boolean color = BLACK; 
     		// 构造方法,KV及父节点
            TreeMapEntry(K key, V value, TreeMapEntry<K,V> parent) {
                this.key = key;
                this.value = value;
                this.parent = parent;
            }
    }
    

    TreeMap构造方法如下:

    /**
    * TreeMap构造方法
    */
    // 无参构造方法,
    public TreeMap() {
        comparator = null;
    }
    
    // 带有比较器comparator的构造方法
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    
    // 原集合需要添加到新集合的构造方法
    public TreeMap(Map<? extends K, ? extends V> m) {
         comparator = null;
         putAll(m);
    }
    
    // 参数为SortedMap的构造方法
    // 采用m的比较器排序
    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) {
         }
    }
    

    TreeMap提供了四个构造方法,实现了方法的重载。无参构造方法中比较器的值为null,采用自然排序的方法,如果指定了比较器则称之为定制排序。

    • 自然排序:TreeMap的所有key必须实现Comparable接口,所有的key都是同一个类的对象。
    • 定制排序:创建TreeMap对象传入了一个Comparator对象,该对象负责对TreeMap中所有的key进行排序,采用定制排序不要求Map的key实现Comparable接口。

    三、put方法

    /**
    * TreeMap类的put方法
    */
    public V put(K key, V value) {
    	 // 获取成员变量保存的根节点,赋值给t
         TreeMapEntry<K,V> t = root;
         // 根节点还没有
         if (t == null) {
             compare(key, key); // type (and possibly null) check
    		 // 创建一个根节点,赋值给成员变量root,根节点的parent必然是null啦
             root = new TreeMapEntry<>(key, value, null);
             size = 1;
             modCount++;
             return null;
         }
         int cmp;
         TreeMapEntry<K,V> parent;
         // 获取创建TreeMap时设置的比较器
         Comparator<? super K> cpr = comparator;
         if (cpr != null) {
         	 // 有定制的比较器
         	 // 通过do-while循环的方式,借助定制的比较器,来找出需要插入的这个key的parent是谁
             do {
                 parent = t;
                 cmp = cpr.compare(key, t.key);
                 if (cmp < 0)
                     t = t.left;
                 else if (cmp > 0)
                     t = t.right;
                 else
                     return t.setValue(value);
             } while (t != null);
         }
         else {
         	 // 没有定制的比较器,自然排序的情况
         	 // 这种情况是不允许我们插入null的key
             if (key == null)
                 throw new NullPointerException();
             @SuppressWarnings("unchecked")
             // 获取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);
         }
         // 找到要插入的KV的parent后,创建一个TreeMapEntry对象存储这些数据信息
         TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
         // 根据和父节点的比较结果,是放在父节点的左边还是右边
         if (cmp < 0)
             parent.left = e;
         else
             parent.right = e;
         // 这个方法就比较复杂了,新插入节点后重新调整红黑树
         fixAfterInsertion(e);
         size++;
         modCount++;
         return null;
    }
    

    在树的基本结构那一篇博客里,我们分析过红黑树的插入,提前了解有助于更好理解下面的代码。
    红黑树插入过程

    /**
    * TreeMap插入数据后,红黑树重新调整的方法
    */
    private void fixAfterInsertion(TreeMapEntry<K,V> x) {
    	 // 插入的节点默认是红色的
         x.color = RED;
    	 //(1)新添加节点N为根:涂黑完事(因为根节点必须为黑)
    	 //(2)新添加的节点的父节点是黑的:啥事不用管,添加进来就行
         while (x != null && x != root && x.parent.color == RED) {
         	 // 这里面就是处理我那篇博客里的(3)和(4.a)(4.b)的情况
         	 // 判断x的节点的父节点位置,是否属于左孩子
             if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
             	 // 获取叔叔节点
                 TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));
                 if (colorOf(y) == RED) {
                 	 // 属于情况(3)
                 	 // (3)新添加节点的父红和叔红:父/叔涂黑,祖父涂红,然后把祖父当成新的平衡节点递归处理
                     setColor(parentOf(x), BLACK);
                     setColor(y, BLACK);
                     setColor(parentOf(parentOf(x)), RED);
                     x = parentOf(parentOf(x));
                 } else {
                  	 // 父红,叔黑	
                     if (x == rightOf(parentOf(x))) {
                     	 // (4.a)的情况,不在同一边,先旋转扭转
                         x = parentOf(x);
                         rotateLeft(x);
                     }
                     // (4.b)的情况,在同一边,然后以祖父为中心旋转
                     setColor(parentOf(x), BLACK);
                     setColor(parentOf(parentOf(x)), RED);
                     // 右旋
                     rotateRight(parentOf(parentOf(x)));
                 }
             } else {
             	 // 父节点是属于右孩子的情况
             	 // 获取叔叔
                 TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x)));
                 if (colorOf(y) == RED) {
                 	 // 叔叔是红的
                 	 // 情况(3)
                 	 // (3)新添加节点的父红和叔红:父/叔涂黑,祖父涂红,然后把祖父当成新的平衡节点递归处理
                     setColor(parentOf(x), BLACK);
                     setColor(y, BLACK);
                     setColor(parentOf(parentOf(x)), RED);
                     x = parentOf(parentOf(x));
                 } else {
                 	 // 父红,叔黑
                     if (x == leftOf(parentOf(x))) {
                     	 // (4.a)的情况,不在同一边,先旋转扭转
                         x = parentOf(x);
                         rotateRight(x);
                     }
                     // (4.b)的情况,在同一边,然后以祖父为中心旋转
                     setColor(parentOf(x), BLACK);
                     setColor(parentOf(parentOf(x)), RED);
                     // 左旋
                     rotateLeft(parentOf(parentOf(x)));
                 }
             }
         }
         root.color = BLACK;
    }
    
    展开全文
  • TreeMap实现原理 红黑树

    万次阅读 2016-09-19 15:10:31
    TreeMap实现是红黑树算法的实现,所以要了解TreeMap就必须对红黑树有一定的了解,其实这篇博文的名字叫做:根据红黑树的算法来分析TreeMap实现,但是为了与Java提高篇系列博文保持一致还是叫做TreeMap比较好。...

    TreeMap的实现是红黑树算法的实现,所以要了解TreeMap就必须对红黑树有一定的了解,其实这篇博文的名字叫做:根据红黑树的算法来分析TreeMap的实现,但是为了与Java提高篇系列博文保持一致还是叫做TreeMap比较好。通过这篇博文你可以获得如下知识点:

           1、红黑树的基本概念。

           2、红黑树增加节点、删除节点的实现过程。

           3、红黑树左旋转、右旋转的复杂过程。

           4、Java 中TreeMap是如何通过put、deleteEntry两个来实现红黑树增加、删除节点的。

    我想通过这篇博文你对TreeMap一定有了更深的认识。好了,下面先简单普及红黑树知识。


           一、红黑树简介

           红黑树又称红-黑二叉树,它首先是一颗二叉树,它具体二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树。

           我们知道一颗基本的二叉树他们都需要满足一个基本性质--即树中的任何节点的值大于它的左子节点,且小于它的右子节点。按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树的过程是非常容易失衡的,最坏的情况就是一边倒(只有右/左子树),这样势必会导致二叉树的检索效率大大降低(O(n)),所以为了维持二叉树的平衡,大牛们提出了各种实现的算法,如:AVLSBT伸展树TREAP ,红黑树等等。

           平衡二叉树必须具备如下特性:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点,其左右子树的高度都相近。


           红黑树顾名思义就是节点是红色或者黑色的平衡二叉树,它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则:

           1、每个节点都只能是红色或者黑色

           2、根节点是黑色

           3、每个叶节点(NIL节点,空节点)是黑色的。

           4、如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

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

           这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。所以红黑树它是复杂而高效的,其检索效率O(log n)。下图为一颗典型的红黑二叉树。


           对于红黑二叉树而言它主要包括三大基本操作:左旋、右旋、着色。


    左旋                                   右旋

    (图片来自:http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html


           本节参考文献:http://baike.baidu.com/view/133754.htm?fr=aladdin-----百度百科

           注:由于本文主要是讲解Java中TreeMap,所以并没有对红黑树进行非常深入的了解和研究,如果诸位想对其进行更加深入的研究Lz提供几篇较好的博文:

           1、红黑树系列集锦

           2、红黑树数据结构剖析

           3、红黑树 


           二、TreeMap数据结构

           >>>>>>回归主角:TreeMap<<<<<<

           TreeMap的定义如下:

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

           TreeMap继承AbstractMap,实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合, NavigableMap(更多)则意味着它支持一系列的导航方法,具备针对给定搜索目标返回最接近匹配项的导航方法 。

           TreeMap中同时也包含了如下几个重要的属性:

    //比较器,因为TreeMap是有序的,通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
            private final Comparator<? super K> comparator;
            //TreeMap红-黑节点,为TreeMap的内部类
            private transient Entry<K,V> root = null;
            //容器大小
            private transient int size = 0;
            //TreeMap修改次数
            private transient int modCount = 0;
            //红黑树的节点颜色--红色
            private static final boolean RED = false;
            //红黑树的节点颜色--黑色
            private static final boolean BLACK = true;

           对于叶子节点Entry是TreeMap的内部类,它有几个重要的属性:

    //
            K key;
            //值
            V value;
            //左孩子
            Entry<K,V> left = null;
            //右孩子
            Entry<K,V> right = null;
            //父亲
            Entry<K,V> parent;
            //颜色
            boolean color = BLACK;

           注:前面只是开胃菜,下面是本篇博文的重中之重,在下面两节我将重点讲解treeMap的put()、delete()方法。通过这两个方法我们会了解红黑树增加、删除节点的核心算法。


           三、TreeMap put()方法

           在了解TreeMap的put()方法之前,我们先了解红黑树增加节点的算法。

           红黑树增加节点

           红黑树在新增节点过程中比较复杂,复杂归复杂它同样必须要依据上面提到的五点规范,同时由于规则1、2、3基本都会满足,下面我们主要讨论规则4、5。假设我们这里有一棵最简单的树,我们规定新增的节点为N、它的父节点为P、P的兄弟节点为U、P的父节点为G。


           对于新节点的插入有如下三个关键地方:

           1、插入新节点总是红色节点 。

           2、如果插入节点的父节点是黑色, 能维持性质 。

           3、如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质 。

           为了保证下面的阐述更加清晰和根据便于参考,我这里将红黑树的五点规定再贴一遍:

    1、每个节点都只能是红色或者黑色

    2、根节点是黑色

    3、每个叶节点(NIL节点,空节点)是黑色的。

    4、如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

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



    •        一、为跟节点
    •        若新插入的节点N没有父节点,则直接当做根据节点插入即可,同时将颜色设置为黑色。(如图一(1))

             二、父节点为黑色

             这种情况新节点N同样是直接插入,同时颜色为红色,由于根据规则四它会存在两个黑色的叶子节点,值为null。同时由于新增节点N为红色,所以通过它的子节点的路径依然会保存着相同的黑色节点数,同样满足规则5。(如图一(2))


      (图一)

             三、若父节点P和P的兄弟节点U都为红色

             对于这种情况若直接插入肯定会出现不平衡现象。怎么处理?P、U节点变黑、G节点变红。这时由于经过节点P、U的路径都必须经过G所以在这些路径上面的黑节点数目还是相同的。但是经过上面的处理,可能G节点的父节点也是红色,这个时候我们需要将G节点当做新增节点递归处理。


             四、若父节点P为红色,叔父节点U为黑色或者缺少,且新增节点N为P节点的右孩子

             对于这种情况我们对新增节点N、P进行一次左旋转。这里所产生的结果其实并没有完成,还不是平衡的(违反了规则四),这是我们需要进行情况5的操作。


    •        五、父节点P为红色,叔父节点U为黑色或者缺少,新增节点N为父节点P左孩子


    •        这种情况有可能是由于情况四而产生的,也有可能不是。对于这种情况先已P节点为中心进行右旋转,在旋转后产生的树中,节点P是节点N、G的父节点。但是这棵树并不规范,它违反了规则4,所以我们将P、G节点的颜色进行交换,使之其满足规范。开始时所有的路径都需要经过G其他们的黑色节点数一样,但是现在所有的路径改为经过P,且P为整棵树的唯一黑色节点,所以调整后的树同样满足规范5。


    •        上面展示了红黑树新增节点的五种情况,这五种情况涵盖了所有的新增可能,不管这棵红黑树多么复杂,都可以根据这五种情况来进行生成。下面就来分析Java中的TreeMap是如何来实现红黑树的。


    •        TreeMap put()方法实现分析

             在TreeMap的put()的实现方法中主要分为两个步骤,第一:构建排序二叉树,第二:平衡二叉树。

             对于排序二叉树的创建,其添加节点的过程如下:

    •        1、以根节点为初始节点进行检索。

    •        2、与当前节点进行比对,若新增节点值较大,则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。

    •        3、循环递归2步骤知道检索出合适的叶子节点为止。

    •        4、将新增节点与3步骤中找到的节点进行比对,如果新增节点较大,则添加为右子节点;否则添加为左子节点。

    •        按照这个步骤我们就可以将一个新增节点添加到排序二叉树中合适的位置。如下:


    • [html]  view plain  copy
       print ? 在CODE上查看代码片 派生到我的代码片
      1. public V put(K key, V value) {  
      2.            //用t表示二叉树的当前节点  
      3.             Entry<K,V> t = root;  
      4.             //t为null表示一个空树,即TreeMap中没有任何元素,直接插入  
      5.             if (t == null) {  
      6.                 //比较key值,个人觉得这句代码没有任何意义,空树还需要比较、排序?  
      7.                 compare(key, key); // type (and possibly null) check  
      8.                 //将新的key-value键值对创建为一个Entry节点,并将该节点赋予给root  
      9.                 root = new Entry<>(key, value, null);  
      10.                 //容器的size = 1,表示TreeMap集合中存在一个元素  
      11.                 size = 1;  
      12.                 //修改次数 + 1  
      13.                 modCount++;  
      14.                 return null;  
      15.             }  
      16.             int cmp;     //cmp表示key排序的返回结果  
      17.             Entry<K,V> parent;   //父节点  
      18.             // split comparator and comparable paths  
      19.             Comparator<? super K> cpr = comparator;    //指定的排序算法  
      20.             //如果cpr不为空,则采用既定的排序算法进行创建TreeMap集合  
      21.             if (cpr != null) {  
      22.                 do {  
      23.                     parent = t;      //parent指向上次循环后的t  
      24.                     //比较新增节点的key和当前节点key的大小  
      25.                     cmp = cpr.compare(key, t.key);  
      26.                     //cmp返回值小于0,表示新增节点的key小于当前节点的key,则以当前节点的左子节点作为新的当前节点  
      27.                     if (cmp < 0)  
      28.                         t = t.left;  
      29.                     //cmp返回值大于0,表示新增节点的key大于当前节点的key,则以当前节点的右子节点作为新的当前节点  
      30.                     else if (cmp > 0)  
      31.                         t = t.right;  
      32.                     //cmp返回值等于0,表示两个key值相等,则新值覆盖旧值,并返回新值  
      33.                     else  
      34.                         return t.setValue(value);  
      35.                 } while (t != null);  
      36.             }  
      37.             //如果cpr为空,则采用默认的排序算法进行创建TreeMap集合  
      38.             else {  
      39.                 if (key == null)     //key值为空抛出异常  
      40.                     throw new NullPointerException();  
      41.                 /* 下面处理过程和上面一样 */  
      42.                 Comparable<? super K> k = (Comparable<? super K>) key;  
      43.                 do {  
      44.                     parent = t;  
      45.                     cmp = k.compareTo(t.key);  
      46.                     if (cmp < 0)  
      47.                         t = t.left;  
      48.                     else if (cmp > 0)  
      49.                         t = t.right;  
      50.                     else  
      51.                         return t.setValue(value);  
      52.                 } while (t != null);  
      53.             }  
      54.             //将新增节点当做parent的子节点  
      55.             Entry<K,V> e = new Entry<>(key, value, parent);  
      56.             //如果新增节点的key小于parent的key,则当做左子节点  
      57.             if (cmp < 0)  
      58.                 parent.left = e;  
      59.           //如果新增节点的key大于parent的key,则当做右子节点  
      60.             else  
      61.                 parent.right = e;  
      62.             /*  
      63.              *  上面已经完成了排序二叉树的的构建,将新增节点插入该树中的合适位置  
      64.              *  下面fixAfterInsertion()方法就是对这棵树进行调整、平衡,具体过程参考上面的五种情况  
      65.              */  
      66.             fixAfterInsertion(e);  
      67.             //TreeMap元素数量 + 1  
      68.             size++;  
      69.             //TreeMap容器修改次数 + 1  
      70.             modCount++;  
      71.             return null;  
      72.         }  

    • 上面代码中do{}代码块是实现排序二叉树的核心算法,通过该算法我们可以确认新增节点在该树的正确位置。找到正确位置后将插入即可,这样做了其实还没有完成,因为我知道TreeMap的底层实现是红黑树,红黑树是一棵平衡排序二叉树,普通的排序二叉树可能会出现失衡的情况,所以下一步就是要进行调整。fixAfterInsertion(e); 调整的过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作。代码如下:
    • [java]  view plain  copy
       print ? 在CODE上查看代码片 派生到我的代码片
      1. /** 
      2.      * 新增节点后的修复操作 
      3.      * x 表示新增节点 
      4.      */  
      5.      private void fixAfterInsertion(Entry<K,V> x) {  
      6.             x.color = RED;    //新增节点的颜色为红色  
      7.   
      8.             //循环 直到 x不是根节点,且x的父节点不为红色  
      9.             while (x != null && x != root && x.parent.color == RED) {  
      10.                 //如果X的父节点(P)是其父节点的父节点(G)的左节点  
      11.                 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {  
      12.                     //获取X的叔节点(U)  
      13.                     Entry<K,V> y = rightOf(parentOf(parentOf(x)));  
      14.                     //如果X的叔节点(U) 为红色(情况三)  
      15.                     if (colorOf(y) == RED) {       
      16.                         //将X的父节点(P)设置为黑色  
      17.                         setColor(parentOf(x), BLACK);  
      18.                         //将X的叔节点(U)设置为黑色  
      19.                         setColor(y, BLACK);  
      20.                         //将X的父节点的父节点(G)设置红色  
      21.                         setColor(parentOf(parentOf(x)), RED);  
      22.                         x = parentOf(parentOf(x));  
      23.                     }  
      24.                     //如果X的叔节点(U为黑色);这里会存在两种情况(情况四、情况五)  
      25.                     else {     
      26.                         //如果X节点为其父节点(P)的右子树,则进行左旋转(情况四)  
      27.                         if (x == rightOf(parentOf(x))) {  
      28.                             //将X的父节点作为X  
      29.                             x = parentOf(x);  
      30.                             //右旋转  
      31.                             rotateLeft(x);  
      32.                         }  
      33.                         //(情况五)  
      34.                         //将X的父节点(P)设置为黑色  
      35.                         setColor(parentOf(x), BLACK);  
      36.                         //将X的父节点的父节点(G)设置红色  
      37.                         setColor(parentOf(parentOf(x)), RED);  
      38.                         //以X的父节点的父节点(G)为中心右旋转  
      39.                         rotateRight(parentOf(parentOf(x)));  
      40.                     }  
      41.                 }  
      42.                 //如果X的父节点(P)是其父节点的父节点(G)的右节点  
      43.                 else {  
      44.                     //获取X的叔节点(U)  
      45.                     Entry<K,V> y = leftOf(parentOf(parentOf(x)));  
      46.                   //如果X的叔节点(U) 为红色(情况三)  
      47.                     if (colorOf(y) == RED) {  
      48.                         //将X的父节点(P)设置为黑色  
      49.                         setColor(parentOf(x), BLACK);  
      50.                         //将X的叔节点(U)设置为黑色  
      51.                         setColor(y, BLACK);  
      52.                         //将X的父节点的父节点(G)设置红色  
      53.                         setColor(parentOf(parentOf(x)), RED);  
      54.                         x = parentOf(parentOf(x));  
      55.                     }  
      56.                   //如果X的叔节点(U为黑色);这里会存在两种情况(情况四、情况五)  
      57.                     else {  
      58.                         //如果X节点为其父节点(P)的右子树,则进行左旋转(情况四)  
      59.                         if (x == leftOf(parentOf(x))) {  
      60.                             //将X的父节点作为X  
      61.                             x = parentOf(x);  
      62.                            //右旋转  
      63.                             rotateRight(x);  
      64.                         }  
      65.                         //(情况五)  
      66.                         //将X的父节点(P)设置为黑色  
      67.                         setColor(parentOf(x), BLACK);  
      68.                         //将X的父节点的父节点(G)设置红色  
      69.                         setColor(parentOf(parentOf(x)), RED);  
      70.                         //以X的父节点的父节点(G)为中心右旋转  
      71.                         rotateLeft(parentOf(parentOf(x)));  
      72.                     }  
      73.                 }  
      74.             }  
      75.             //将根节点G强制设置为黑色  
      76.             root.color = BLACK;  
      77.         }  


    •        对这段代码的研究我们发现,其处理过程完全符合红黑树新增节点的处理过程。所以在看这段代码的过程一定要对红黑树的新增节点过程有了解。在这个代码中还包含几个重要的操作。左旋(rotateLeft())、右旋(rotateRight())、着色(setColor())。

      左旋:rotateLeft()

    •        所谓左旋转,就是将新增节点(N)当做其父节点(P),将其父节点P当做新增节点(N)的左子节点。即:G.left ---> N ,N.left ---> P。

    •    右旋:rotateRight()

      [java]  view plain  copy
       print ? 在CODE上查看代码片 派生到我的代码片
      1. private void rotateLeft(Entry<K,V> p) {  
      2.         if (p != null) {  
      3.             //获取P的右子节点,其实这里就相当于新增节点N(情况四而言)  
      4.             Entry<K,V> r = p.right;  
      5.             //将R的左子树设置为P的右子树  
      6.             p.right = r.left;  
      7.             //若R的左子树不为空,则将P设置为R左子树的父亲  
      8.             if (r.left != null)  
      9.                 r.left.parent = p;  
      10.             //将P的父亲设置R的父亲  
      11.             r.parent = p.parent;  
      12.             //如果P的父亲为空,则将R设置为跟节点  
      13.             if (p.parent == null)  
      14.                 root = r;  
      15.             //如果P为其父节点(G)的左子树,则将R设置为P父节点(G)左子树  
      16.             else if (p.parent.left == p)  
      17.                 p.parent.left = r;  
      18.             //否则R设置为P的父节点(G)的右子树  
      19.             else  
      20.                 p.parent.right = r;  
      21.             //将P设置为R的左子树  
      22.             r.left = p;  
      23.             //将R设置为P的父节点  
      24.             p.parent = r;  
      25.         }  
      26.     }  
    •        所谓右旋转即,P.right ---> G、G.parent ---> P。

    • [java]  view plain  copy
       print ? 在CODE上查看代码片 派生到我的代码片
      1. private void rotateRight(Entry<K,V> p) {  
      2.         if (p != null) {  
      3.             //将L设置为P的左子树  
      4.             Entry<K,V> l = p.left;  
      5.             //将L的右子树设置为P的左子树  
      6.             p.left = l.right;  
      7.             //若L的右子树不为空,则将P设置L的右子树的父节点  
      8.             if (l.right != null)   
      9.                 l.right.parent = p;  
      10.             //将P的父节点设置为L的父节点  
      11.             l.parent = p.parent;  
      12.             //如果P的父节点为空,则将L设置根节点  
      13.             if (p.parent == null)  
      14.                 root = l;  
      15.             //若P为其父节点的右子树,则将L设置为P的父节点的右子树  
      16.             else if (p.parent.right == p)  
      17.                 p.parent.right = l;  
      18.             //否则将L设置为P的父节点的左子树  
      19.             else   
      20.                 p.parent.left = l;  
      21.             //将P设置为L的右子树  
      22.             l.right = p;  
      23.             //将L设置为P的父节点  
      24.             p.parent = l;  
      25.         }  
      26.     }  
    •        左旋、右旋的示意图如下:


    • (左旋)                                         (右旋)

      (图片来自:http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html

             着色:setColor()

             着色就是改变该节点的颜色,在红黑树中,它是依靠节点的颜色来维持平衡的。

    • [java]  view plain  copy
       print ? 在CODE上查看代码片 派生到我的代码片
      1. private static <K,V> void setColor(Entry<K,V> p, boolean c) {  
      2.         if (p != null)  
      3.             p.color = c;  
      4.     }  

    •        四、TreeMap delete()方法

             红黑树删除节点

             针对于红黑树的增加节点而言,删除显得更加复杂,使原本就复杂的红黑树变得更加复杂。同时删除节点和增加节点一样,同样是找到删除的节点,删除之后调整红黑树。但是这里的删除节点并不是直接删除,而是通过走了“弯路”通过一种捷径来删除的:找到被删除的节点D的子节点C,用C来替代D,不是直接删除D,因为D被C替代了,直接删除C即可。所以这里就将删除父节点D的事情转变为了删除子节点C的事情,这样处理就将复杂的删除事件简单化了。子节点C的规则是:右分支最左边,或者 左分支最右边的。


    •        红-黑二叉树删除节点,最大的麻烦是要保持 各分支黑色节点数目相等。 因为是删除,所以不用担心存在颜色冲突问题——插入才会引起颜色冲突。

             红黑树删除节点同样会分成几种情况,这里是按照待删除节点有几个儿子的情况来进行分类:

             1、没有儿子,即为叶结点。直接把父结点的对应儿子指针设为NULL,删除儿子结点就OK了。

             2、只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子,删除儿子结点也OK了。

             3、有两个儿子。这种情况比较复杂,但还是比较简单。上面提到过用子节点C替代代替待删除节点D,然后删除子节点C即可。

             下面就论各种删除情况来进行图例讲解,但是在讲解之前请允许我再次啰嗦一句,请时刻牢记红黑树的5点规定:

             1、每个节点都只能是红色或者黑色

             2、根节点是黑色

             3、每个叶节点(NIL节点,空节点)是黑色的。

             4、如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

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

             (注:已经讲三遍了,再不记住我就怀疑你是否适合搞IT了 O(∩_∩)O~)

             诚然,既然删除节点比较复杂,那么在这里我们就约定一下规则:

             1、下面要讲解的删除节点一定是实际要删除节点的后继节点(N),如前面提到的C。

             2、下面提到的删除节点的树都是如下结构,该结构所选取的节点是待删除节点的右树的最左边子节点。这里我们规定真实删除节点为N、父节点为P、兄弟节点为W兄弟节点的两个子节点为X1、X2。如下图(2.1)。


    •        现在我们就上面提到的三种情况进行分析、处理。

             情况一、无子节点(红色节点)

             这种情况对该节点直接删除即可,不会影响树的结构。因为该节点为叶子节点它不可能存在子节点-----如子节点为黑,则违反黑节点数原则(规定5),为红,则违反“颜色”原则(规定4)。 如上图(2.2)。

             情况二、有一个子节点

             这种情况处理也是非常简单的,用子节点替代待删除节点,然后删除子节点即可。如上图(2.3)

             情况三、有两个子节点

             这种情况可能会稍微有点儿复杂。它需要找到一个替代待删除节点(N)来替代它,然后删除N即可。它主要分为四种情况。

             1、N的兄弟节点W为红色

             2、N的兄弟w是黑色的,且w的俩个孩子都是黑色的。

             3、N的兄弟w是黑色的,w的左孩子是红色,w的右孩子是黑色。

             4、N的兄弟w是黑色的,且w的右孩子时红色的。

             情况3.1、N的兄弟节点W为红色

             W为红色,那么其子节点X1、X2必定全部为黑色,父节点P也为黑色。处理策略是:改变W、P的颜色,然后进行一次左旋转。这样处理就可以使得红黑性质得以继续保持。N的新兄弟new w是旋转之前w的某个孩子,为黑色。这样处理后将情况3.1、转变为3.2、3.3、3.4中的一种。如下:


    •        情况3.2、N的兄弟w是黑色的,且w的俩个孩子都是黑色的。

    •        这种情况其父节点可红可黑,由于W为黑色,这样导致N子树相对于其兄弟W子树少一个黑色节点,这时我们可以将W置为红色。这样,N子树与W子树黑色节点一致,保持了平衡。如下


    •        将W由黑转变为红,这样就会导致新节点new N相对于它的兄弟节点会少一个黑色节点。但是如果new x为红色,我们直接将new x转变为黑色,保持整棵树的平衡。否则情况3.2 会转变为情况3.1、3.3、3.4中的一种。

    •        情况3.3、N的兄弟w是黑色的,w的左孩子是红色,w的右孩子是黑色。

    •        针对这种情况是将节点W和其左子节点进行颜色交换,然后对W进行右旋转处理。


    •        此时N的新兄弟X1(new w)是一个有红色右孩子的黑结点,于是将情况3转化为情况4.

    •        情况3.4、N的兄弟w是黑色的,且w的右孩子时红色的。

    •        交换W和父节点P的颜色,同时对P进行左旋转操作。这样就把左边缺失的黑色节点给补回来了。同时将W的右子节点X2置黑。这样左右都达到了平衡。



    •        总结

    •        个人认为这四种情况比较难理解,首先他们都不是单一的某种情况,他们之间是可以进行互转的。相对于其他的几种情况,情况3.2比较好理解,仅仅只是一个颜色的转变,通过减少右子树的一个黑色节点使之保持平衡,同时将不平衡点上移至N与W的父节点,然后进行下一轮迭代。情况3.1,是将W旋转将其转成情况2、3、4情况进行处理。而情况3.3通过转变后可以化成情况3.4来进行处理,从这里可以看出情况3.4应该最终结。情况3.4、右子节点为红色节点,那么将缺失的黑色节点交由给右子节点,通过旋转达到平衡。

    •        通过上面的分析,我们已经初步了解了红黑树的删除节点情况,相对于增加节点而言它确实是选的较为复杂。下面我将看到在Java TreeMap中是如何实现红黑树删除的。

    •        TreeMap deleteEntry()方法实现分析

    •        通过上面的分析我们确认删除节点的步骤是:找到一个替代子节点C来替代P,然后直接删除C,最后调整这棵红黑树。下面代码是寻找替代节点、删除替代节点。

    • [java]  view plain  copy
       print ? 在CODE上查看代码片 派生到我的代码片
      1. private void deleteEntry(Entry<K,V> p) {  
      2.         modCount++;      //修改次数 +1  
      3.         size--;          //元素个数 -1  
      4.   
      5.         /* 
      6.          * 被删除节点的左子树和右子树都不为空,那么就用 p节点的中序后继节点代替 p 节点 
      7.          * successor(P)方法为寻找P的替代节点。规则是右分支最左边,或者 左分支最右边的节点 
      8.          * ---------------------(1) 
      9.          */  
      10.         if (p.left != null && p.right != null) {    
      11.             Entry<K,V> s = successor(p);  
      12.             p.key = s.key;  
      13.             p.value = s.value;  
      14.             p = s;  
      15.         }  
      16.   
      17.         //replacement为替代节点,如果P的左子树存在那么就用左子树替代,否则用右子树替代  
      18.         Entry<K,V> replacement = (p.left != null ? p.left : p.right);  
      19.   
      20.         /* 
      21.          * 删除节点,分为上面提到的三种情况 
      22.          * -----------------------(2) 
      23.          */  
      24.         //如果替代节点不为空  
      25.         if (replacement != null) {  
      26.             replacement.parent = p.parent;  
      27.             /* 
      28.              *replacement来替代P节点 
      29.              */  
      30.             //若P没有父节点,则跟节点直接变成replacement  
      31.             if (p.parent == null)  
      32.                 root = replacement;  
      33.             //如果P为左节点,则用replacement来替代为左节点  
      34.             else if (p == p.parent.left)  
      35.                 p.parent.left  = replacement;  
      36.           //如果P为右节点,则用replacement来替代为右节点  
      37.             else  
      38.                 p.parent.right = replacement;  
      39.   
      40.             //同时将P节点从这棵树中剔除掉  
      41.             p.left = p.right = p.parent = null;  
      42.   
      43.             /* 
      44.              * 若P为红色直接删除,红黑树保持平衡 
      45.              * 但是若P为黑色,则需要调整红黑树使其保持平衡 
      46.              */  
      47.             if (p.color == BLACK)  
      48.                 fixAfterDeletion(replacement);  
      49.         } else if (p.parent == null) {     //p没有父节点,表示为P根节点,直接删除即可  
      50.             root = null;  
      51.         } else {      //P节点不存在子节点,直接删除即可  
      52.             if (p.color == BLACK)         //如果P节点的颜色为黑色,对红黑树进行调整  
      53.                 fixAfterDeletion(p);  
      54.   
      55.             //删除P节点  
      56.             if (p.parent != null) {  
      57.                 if (p == p.parent.left)  
      58.                     p.parent.left = null;  
      59.                 else if (p == p.parent.right)  
      60.                     p.parent.right = null;  
      61.                 p.parent = null;  
      62.             }  
      63.         }  
      64.     }  


             (1)除是寻找替代节点replacement,其实现方法为successor()。如下:

      [java]  view plain  copy
       print ? 在CODE上查看代码片 派生到我的代码片
      1. static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {  
      2.         if (t == null)  
      3.             return null;  
      4.         /* 
      5.          * 寻找右子树的最左子树 
      6.          */  
      7.         else if (t.right != null) {  
      8.             Entry<K,V> p = t.right;  
      9.             while (p.left != null)  
      10.                 p = p.left;  
      11.             return p;  
      12.         }   
      13.         /* 
      14.          * 选择左子树的最右子树 
      15.          */  
      16.         else {  
      17.             Entry<K,V> p = t.parent;  
      18.             Entry<K,V> ch = t;  
      19.             while (p != null && ch == p.right) {  
      20.                 ch = p;  
      21.                 p = p.parent;  
      22.             }  
      23.             return p;  
      24.         }  
      25.     }  

             (2)处是删除该节点过程。它主要分为上面提到的三种情况,它与上面的if…else if… else一一对应 。如下:

             1、有两个儿子。这种情况比较复杂,但还是比较简单。上面提到过用子节点C替代代替待删除节点D,然后删除子节点C即可。

             2、没有儿子,即为叶结点。直接把父结点的对应儿子指针设为NULL,删除儿子结点就OK了。

             3、只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子,删除儿子结点也OK了。

             删除完节点后,就要根据情况来对红黑树进行复杂的调整:fixAfterDeletion()。

      [java]  view plain  copy
       print ? 在CODE上查看代码片 派生到我的代码片
      1. private void fixAfterDeletion(Entry<K,V> x) {  
      2.         // 删除节点需要一直迭代,知道 直到 x 不是根节点,且 x 的颜色是黑色  
      3.         while (x != root && colorOf(x) == BLACK) {  
      4.             if (x == leftOf(parentOf(x))) {      //若X节点为左节点  
      5.                 //获取其兄弟节点  
      6.                 Entry<K,V> sib = rightOf(parentOf(x));  
      7.   
      8.                 /* 
      9.                  * 如果兄弟节点为红色----(情况3.1) 
      10.                  * 策略:改变W、P的颜色,然后进行一次左旋转 
      11.                  */  
      12.                 if (colorOf(sib) == RED) {       
      13.                     setColor(sib, BLACK);       
      14.                     setColor(parentOf(x), RED);    
      15.                     rotateLeft(parentOf(x));  
      16.                     sib = rightOf(parentOf(x));  
      17.                 }  
      18.   
      19.                 /* 
      20.                  * 若兄弟节点的两个子节点都为黑色----(情况3.2) 
      21.                  * 策略:将兄弟节点编程红色 
      22.                  */  
      23.                 if (colorOf(leftOf(sib))  == BLACK &&  
      24.                     colorOf(rightOf(sib)) == BLACK) {  
      25.                     setColor(sib, RED);  
      26.                     x = parentOf(x);  
      27.                 }   
      28.                 else {  
      29.                     /* 
      30.                      * 如果兄弟节点只有右子树为黑色----(情况3.3) 
      31.                      * 策略:将兄弟节点与其左子树进行颜色互换然后进行右转 
      32.                      * 这时情况会转变为3.4 
      33.                      */  
      34.                     if (colorOf(rightOf(sib)) == BLACK) {  
      35.                         setColor(leftOf(sib), BLACK);  
      36.                         setColor(sib, RED);  
      37.                         rotateRight(sib);  
      38.                         sib = rightOf(parentOf(x));  
      39.                     }  
      40.                     /* 
      41.                      *----情况3.4 
      42.                      *策略:交换兄弟节点和父节点的颜色, 
      43.                      *同时将兄弟节点右子树设置为黑色,最后左旋转 
      44.                      */  
      45.                     setColor(sib, colorOf(parentOf(x)));  
      46.                     setColor(parentOf(x), BLACK);  
      47.                     setColor(rightOf(sib), BLACK);  
      48.                     rotateLeft(parentOf(x));  
      49.                     x = root;  
      50.                 }  
      51.             }   
      52.               
      53.             /** 
      54.              * X节点为右节点与其为做节点处理过程差不多,这里就不在累述了 
      55.              */  
      56.             else {  
      57.                 Entry<K,V> sib = leftOf(parentOf(x));  
      58.   
      59.                 if (colorOf(sib) == RED) {  
      60.                     setColor(sib, BLACK);  
      61.                     setColor(parentOf(x), RED);  
      62.                     rotateRight(parentOf(x));  
      63.                     sib = leftOf(parentOf(x));  
      64.                 }  
      65.   
      66.                 if (colorOf(rightOf(sib)) == BLACK &&  
      67.                     colorOf(leftOf(sib)) == BLACK) {  
      68.                     setColor(sib, RED);  
      69.                     x = parentOf(x);  
      70.                 } else {  
      71.                     if (colorOf(leftOf(sib)) == BLACK) {  
      72.                         setColor(rightOf(sib), BLACK);  
      73.                         setColor(sib, RED);  
      74.                         rotateLeft(sib);  
      75.                         sib = leftOf(parentOf(x));  
      76.                     }  
      77.                     setColor(sib, colorOf(parentOf(x)));  
      78.                     setColor(parentOf(x), BLACK);  
      79.                     setColor(leftOf(sib), BLACK);  
      80.                     rotateRight(parentOf(x));  
      81.                     x = root;  
      82.                 }  
      83.             }  
      84.         }  
      85.   
      86.         setColor(x, BLACK);  
      87.     }  
             这是红黑树在删除节点后,对树的平衡性进行调整的过程,其实现过程与上面四种复杂的情况一一对应,所以在这个源码的时候一定要对着上面提到的四种情况看。

    •        五、写在最后

             这篇博文确实是有点儿长,在这里非常感谢各位看客能够静下心来读完,我想你通过读完这篇博文一定收获不小。同时这篇博文很大篇幅都在阐述红黑树的实现过程,对Java 的TreeMap聊的比较少,但是我认为如果理解了红黑树的实现过程,对TreeMap那是手到擒来,小菜一碟。

             同时这篇博文我写了四天,看了、参考了大量的博文。同时不免会有些地方存在借鉴之处,在这里对其表示感谢。LZ大二开始学习数据结构,自认为学的不错,现在发现数据结构我还有太多的地方需要学习了,同时也再一次体味了算法的魅力!!!!


      参考资料:

      1、红黑树数据结构剖析:http://www.cnblogs.com/fanzhidongyzby/p/3187912.html

      2、红黑二叉树详解及理论分析 :http://blog.csdn.net/kartorz/article/details/8865997

      3、教你透彻了解红黑树 blog.csdn.net/v_july_v/article/details/6105630

      4、经典算法研究系列:五、红黑树算法的实现与剖析 :http://blog.csdn.net/v_JULY_v/article/details/6109153

      5、示例,红黑树插入和删除过程:http://saturnman.blog.163.com/blog/static/557611201097221570/

      6、红黑二叉树详解及理论分析 :http://blog.csdn.net/kartorz/article/details/8865997

      ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    展开全文
  • TreeMap实现原理及源码分析

    千次阅读 2017-08-01 09:12:34
    TreeMap是一个有序的key-value集合,基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建时提供的Comparator进行排序、 对于TreeMap而言,每个Entry都被当成“红黑树”的一个节点对待...
  • 在介绍TreeMap之前,我们来了解一种数据结构:二叉树。相信学过数据结构的同学知道,这种结构的数据存储形式在查找的时候效率非常高。 二叉树结构又可再细分为二叉查找树和二叉平衡树 二叉查找树是一种有序...
  • 先贴几篇博客: Java HashMap如何实现Key 的唯一性 Java TreeMap 红黑树介绍 HashMap,LinkedHashMap,TreeMap的有序性
  • TreeMap工作原理

    千次阅读 2018-06-12 09:43:45
    一、红黑树简介TreeMap是通过红黑树实现的,增删改查的操作底层都是对红黑树的相关操作,因此先介绍红黑树的相关性质。红黑树顾名思义就是节点是红色或者黑色的平衡二叉树,它通过颜色的约束来维持着二叉树的平衡。...
  • java--TreeMap实现原理

    2021-05-11 16:46:10
    TreeMap是红黑二叉树的典型实现 TreeMap和HashMap实现了同样的接口Map,HashMap效率高于TreeMap,在需要排序Map时才选用TreeMap; private transient Entry<K,V> root;
  • TreeMap原理实现及常用方法

    千次阅读 多人点赞 2020-08-04 11:59:37
    前面我们分别讲了Map接口的两个实现类HashMap和LinkedHashMap,本章我们讲一下Map接口另一个重要的实现TreeMapTreeMap或许不如HashMap那么常用,但存在即合理,它也有自己的应用场景,TreeMap可以实现元素的自动...
  • 深度解各类Map的内部实现结构 1、创建实例 2、查看源码 ...每个Map里面都有若干个Node的类对象,Node...插入时,通过下图来确定索引值,同时每个node都有一个next的属性,需要注意的是HashMap可以加入TreeMap...
  • TreeMap的数据结构是红黑树,建议在分析源码前对红黑树有一定了解; 关于树型结构可以参考:http://www.cnblogs.com/xrq730/p/5187032.html
  • 一、HashSet底层实现 HashSet实现了Set接口,不允许有重复元素,因为HashSet是基于HashMap实现的,HashSet中的元素都存放在HashMap的key上面,而value中的值都是统一的一个private static final Object PRESENT = ...
  • 转载Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例 一、TreeMap 简单介绍 什么是Map?  在数组中我们通过数组下标来对数组内容进行索引的,而在Map中我们通过对象来对 对象进行索引,用来索引的对象...
  • TreeMap实现是红黑树算法的实现,所以要了解TreeMap就必须对红黑树有一定的了解,通过这篇博文你可以获得如下知识点: 1. 红黑树的基本概念。 2. 红黑树增加节点、删除节点的实现过程。 3. 红黑树左旋转、右...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,326
精华内容 10,930
关键字:

treemap的实现原理