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

TreeMap是基于红黑树实现的，这里只对红黑树做个简单的介绍，红黑树是一种特殊的二叉排序树，红黑树通过一些限制，使其不会出现二叉树排序树中极端的一边倒的情况，相对二叉排序树而言，这自然提高了查询的效率。

二叉排序树的基本性质如下：

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

2、根节点是黑色

3、每个叶节点（NIL节点，空节点）是黑色的。

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

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

正是这些性质的限制，使得红黑树中任一节点到其子孙叶子节点的最长路径不会长于最短路径的2倍，因此它是一种接近平衡的二叉树。

红黑树的插入删除操作很简单，就是单纯的二叉排序树的插入删除操作。红黑树被认为比较变态的地方自然在于插入删除后对红黑树的调整操作（旋转和着色），主要是情况分的很多，限于篇幅及博主的熟悉程度优先，这里不打算详细介绍插入删除后调整红黑树的各种情况及其实现，我们有个宏观上的了解即可，如须详细了解，参见算法导论或一些相关的资料。

TreeMap的排序是基于对key的排序实现的，它的每一个Entry代表红黑树的一个节点，Entry的数据结构如下：

static final class Entry<K,V> implements Map.Entry<K,V> {    
     // 键    
     K key;    
     // 值    
     V value;    
     // 左孩子    
     Entry<K,V> left = null;    
     // 右孩子    
     Entry<K,V> right = null;    
     // 父节点    
     Entry<K,V> parent;    
     // 当前节点颜色    
     boolean color = BLACK;    

     // 构造函数    
     Entry(K key, V value, Entry<K,V> parent) {    
         this.key = key;    
         this.value = value;    
         this.parent = parent;    
     }    

。。。。。  
} 

先来看下TreeMap的构造方法。

TreeMap一共有4个构造方法。

1、无参构造方法

public TreeMap() {    
    comparator = null;    
}

采用无参构造方法，不指定比较器，这时候，排序的实现要依赖key.compareTo()方法，因此key必须实现Comparable接口，并覆写其中的compareTo方法。

2、带有比较器的构造方法

public TreeMap(Comparator<? super K> comparator) {    
    this.comparator = comparator;    
} 

采用带比较器的构造方法，这时候，排序依赖该比较器，key可以不用实现Comparable接口。

3、带Map的构造方法

public TreeMap(Map<? extends K, ? extends V> m) {    
    comparator = null;    
    putAll(m);    
}  

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