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

这里的fixAfterInsertion便是节点插入后对树进行调整的方法，这里不做介绍。

删除操作及对应TreeMap的deleteEntry方法，deleteEntry方法同样也只需按照二叉排序树的操作步骤实现即可，删除指定节点后，再对树进行调整即可。

deleteEntry方法的实现源码如下：

    // 删除“红黑树的节点p”    
private void deleteEntry(Entry<K,V> p) {    
    modCount++;    
    size--;    

    if (p.left != null && p.right != null) {    
        Entry<K,V> s = successor (p);    
        p.key = s.key;    
        p.value = s.value;    
        p = s;    
    }   

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

    if (replacement != null) {    
        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;    

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

        if (p.color == BLACK)    
            fixAfterDeletion(replacement);    
    } else if (p.parent == null) {   
        root = null;    
    } else {  
        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;    
        }    
    }    
} 

后面的fixAfterDeletion方法便是节点删除后对树进行调整的方法，这里不做介绍。

其他很多方法这里不再一一介绍。二叉排序树的删除

几点总结

本文对TreeMap的分析较前几篇文章有些浅尝辄止，TreeMap用的没有HashMap那么多

1、TreeMap是根据key进行排序的，它的排序和定位需要依赖比较器或覆写Comparable接口，也因此不需要key覆写hashCode方法和equals方法，就可以排除掉重复的key，而HashMap的key则需要通过覆写hashCode方法和equals方法来确保没有重复的key。



2、TreeMap的查询、插入、删除效率均没有HashMap高，一般只有要对key排序时才使用TreeMap。



3、TreeMap的key不能为null，而HashMap的key可以为null。

注：对TreeSet和HashSet的源码不再进行剖析，二者分别是基于TreeMap和HashMap实现的，只是对应的节点中只有key，而没有value，因此对TreeMap和HashMap比较了解的话，对TreeSet和HashSet的理解就会非常容易。

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