《TreeMap的实现就是红黑树数据结构》由会员分享，可在线阅读，更多相关《TreeMap的实现就是红黑树数据结构（9页珍藏版）》请在金锄头文库上搜索。
1、TreeMap 的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。TreeSet 和 TreeMap 的关系为了让大家了解 TreeMap 和 TreeSet 之间的关系，下面先看 TreeSet 类的部分源代码：public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, java.io.Serializable / 使用 NavigableMap 的 key 来保存 Set 集合的元素private transient NavigableMap m; /
2、 使用一个 PRESENT 作为 Map 集合的所有 value。private static final Object PRESENT = new Object(); / 包访问权限的构造器，以指定的 NavigableMap 对象创建 Set 集合TreeSet(NavigableMap m) this.m = m; public TreeSet() / / 以自然排序方式创建一个新的 TreeMap，/ 根据该 TreeSet 创建一个 TreeSet，/ 使用该 TreeMap 的 key 来保存 Set 集合的元素this(new TreeMap(); public TreeSet(
3、Comparator comparator) / / 以定制排序方式创建一个新的 TreeMap，/ 根据该 TreeSet 创建一个 TreeSet，/ 使用该 TreeMap 的 key 来保存 Set 集合的元素this(new TreeMap(comparator); public TreeSet(Collection c) / 调用 号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素this(); / 向 TreeSet 中添加 Collection 集合 c 里的所有元素addAll(c); public TreeSet(SortedSet s) / 调用 号构
4、造器创建一个 TreeSet，底层以 TreeMap 保存集合元素this(parator(); / 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素addAll(s); /TreeSet 的其他方法都只是直接调用 TreeMap 的方法来提供实现. public boolean addAll(Collection c) if (m.size() = 0 & c.size() 0 & c instanceof SortedSet & m instanceof TreeMap) / 把 c 集合强制转换为 SortedSet 集合SortedSet set = (Sorte
5、dSet) c; / 把 m 集合强制转换为 TreeMap 集合TreeMap map = (TreeMap) m; Comparator cc = (Comparator) parator(); Comparator mc = parator(); / 如果 cc 和 mc 两个 Comparator 相等if (cc = mc | (cc != null & cc.equals(mc) / 把 Collection 中所有元素添加成 TreeMap 集合的 key map.addAllForTreeSet(set, PRESENT); return true; / 直接调用父类的 add
6、All() 方法来实现return super.addAll(c); . 从上面代码可以看出，TreeSet 的 号、 号构造器的都是新建一个 TreeMap 作为实际存储 Set 元素的容器，而另外 2 个构造器则分别依赖于 号和 号构造器，由此可见，TreeSet 底层实际使用的存储容器就是 TreeMap。与 HashSet 完全类似的是，TreeSet 里绝大部分方法都是直接调用 TreeMap 的方法来实现的，这一点读者可以自行参阅 TreeSet 的源代码，此处就不再给出了。对于 TreeMap 而言，它采用一种被称为“红黑树”的排序二叉树来保存 Map 中每个 Entry 每个
7、Entry 都被当成“红黑树” 的一个节点对待。例如对于如下程序而言：public class TreeMapTest public static void main(String args) TreeMap map = new TreeMap(); map.put(ccc , 89.0); map.put(aaa , 80.0); map.put(zzz , 80.0); map.put(bbb , 89.0); System.out.println(map); 当程序执行 map.put(ccc , 89.0); 时，系统将直接把 ccc-89.0 这个 Entry 放入 Map 中，这个
8、 Entry 就是该“红黑树” 的根节点。接着程序执行 map.put(aaa , 80.0); 时，程序会将 aaa-80.0 作为新节点添加到已有的红黑树中。以后每向 TreeMap 中放入一个 key-value 对，系统都需要将该 Entry 当成一个新节点，添加成已有红黑树中，通过这种方式就可保证 TreeMap 中所有 key 总是由小到大地排列。例如我们输出上面程序，将看到如下结果（所有 key 由小到大地排列）：aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0 回页首TreeMap 的添加节点红黑树红黑树是一种自平衡排序二叉树，树中每个节点的值，都大
9、于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值，这确保红黑树运行时可以快速地在树中查找和定位的所需节点。对于 TreeMap 而言，由于它底层采用一棵“红黑树”来保存集合中的 Entry，这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低：当 TreeMap 添加元素时，需要通过循环找到新增 Entry 的插入位置，因此比较耗性能；当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entr
10、y 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态。为了理解 TreeMap 的底层实现，必须先介绍排序二叉树和红黑树这两种数据结构。其中红黑树又是一种特殊的排序二叉树。排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 它的左、右子树也分别为排序二叉树。图 1 显示了一棵排序二叉树：图 1. 排序二叉树对排序二叉树，若按中序
11、遍历就可以得到由小到大的有序序列。如图 1 所示二叉树，中序遍历得：2，3，4，8，9 ，9 ，10 ，13，15，18创建排序二叉树的步骤，也就是不断地向排序二叉树添加节点的过程，向排序二叉树添加节点的步骤如下：1. 以根节点当前节点开始搜索。2. 拿新节点的值和当前节点的值比较。3. 如果新节点的值更大，则以当前节点的右子节点作为新的当前节点；如果新节点的值更小，则以当前节点的左子节点作为新的当前节点。4. 重复 2、3 两个步骤，直到搜索到合适的叶子节点为止。5. 将新节点添加为第 4 步找到的叶子节点的子节点；如果新节点更大，则添加为右子节点；否则添加为左子节点。掌握上面理论之后，下面
12、我们来分析 TreeMap 添加节点（TreeMap 中使用 Entry 内部类代表节点）的实现，TreeMap 集合的 put(K key, V value) 方法实现了将 Entry 放入排序二叉树中，下面是该方法的源代码：public V put(K key, V value) / 先以 t 保存链表的 root 节点Entry t = root; / 如果 t=null，表明是一个空链表，即该 TreeMap 里没有任何 Entry if (t = null) / 将新的 key-value 创建一个 Entry，并将该 Entry 作为 root root = new Entry(k
13、ey, value, null); / 设置该 Map 集合的 size 为 1，代表包含一个 Entry size = 1; / 记录修改次数为 1 modCount+; return null; int cmp; Entry parent; Comparator cpr = comparator; / 如果比较器 cpr 不为 null，即表明采用定制排序if (cpr != null) do / 使用 parent 上次循环后的 t 所引用的 Entry parent = t; / 拿新插入 key 和 t 的 key 进行比较cmp = pare(key, t.key); / 如果新插
14、入的 key 小于 t 的 key，t 等于 t 的左边节点if (cmp 0) t = t.right; / 如果两个 key 相等，新的 value 覆盖原有的 value，/ 并返回原有的 value else return t.setValue(value); while (t != null); else if (key = null) throw new NullPointerException(); Comparable k = (Comparable) key; do / 使用 parent 上次循环后的 t 所引用的 Entry parent = t; / 拿新插入 key
15、和 t 的 key 进行比较cmp = pareTo(t.key); / 如果新插入的 key 小于 t 的 key，t 等于 t 的左边节点if (cmp 0) t = t.right; / 如果两个 key 相等，新的 value 覆盖原有的 value，/ 并返回原有的 value else return t.setValue(value); while (t != null); / 将新插入的节点作为 parent 节点的子节点Entry e = new Entry(key, value, parent); / 如果新插入 key 小于 parent 的 key，则 e 作为 parent 的左子节点if (cmp p) modCount+; size-; / 如果被删除节点的左子树、右子树都不为空if (p.left != null & p.right != null) / 用 p 节点的中序后继节点代替 p 节点Entry s = successor (p); p.key = s.key; p.value = s.value; p = s; / 如果 p 节点的左节点存在，replacem
