二叉排序树的删除红黑树简介TreeMap是基于红黑树实现的，(3)

首先将比较器指定为m的比较器，这取决于生成m时调用构造方法是否传入了指定的构造器，而后调用buildFromSorted方法，将SortedMap中的元素插入到TreeMap中，由于SortedMap中的元素师有序的，实际上它是根据SortedMap创建的TreeMap，将SortedMap中对应的元素添加到TreeMap中。

插入操作即对应TreeMap的put方法，put操作实际上只需按照二叉排序树的插入步骤来操作即可，插入到指定位置后，再做调整，使其保持红黑树的特性。二叉排序树的删除

put源码的实现：

public V put(K key, V value) {    
    Entry<K,V> t = root;    
    // 若红黑树为空，则插入根节点    
    if (t == null) {    
    // TBD:    
    // 5045147: (coll) Adding null to an empty TreeSet should    
    // throw NullPointerException    
    //    
    // compare(key, key); // type check    
        root = new Entry<K,V>(key, value, null);    
        size = 1;    
        modCount++;    
        return null;    
    }    
    int cmp;    
    Entry<K,V> parent;    
    // split comparator and comparable paths    
    Comparator<? super K> cpr = comparator;    
    // 找出(key, value)在二叉排序树中的插入位置。    
    // 红黑树是以key来进行排序的，所以这里以key来进行查找。    
    if (cpr != null) {    
        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 {    
        if (key == null)    
            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);    
    }    
    // 为（key-value）新建节点    
    Entry<K,V> e = new Entry<K,V>(key, value, parent);    
    if (cmp < 0)    
        parent.left = e;    
    else   
        parent.right = e;    
    // 插入新的节点后，调用fixAfterInsertion调整红黑树。    
    fixAfterInsertion(e);    
    size++;    
    modCount++;    
    return null;    
}    

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-88601-3.html