TreeMap 的实现就是红黑树数据结构.docx

《TreeMap 的实现就是红黑树数据结构.docx》由会员分享，可在线阅读，更多相关《TreeMap 的实现就是红黑树数据结构.docx（10页珍藏版）》请在三一办公上搜索。

1、TreeMap的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。TreeSet 和 TreeMap 的关系为了让大家了解TreeMap和TreeSet之间的关系，下面先看TreeSet类的部分源代码：public class TreeSet extends AbstractSetimplements NavigableSet, Cloneable, java.io.Serializable一/使用NavigableMap的key来保存Set集合的元素 private transient NavigableMap m;/使用一个present作为Ma

2、p集合的所有value。private static final Object present = new Object();/包访问权限的构造器，以指定的NavigableMap对象创建Set集合TreeSet(NavigableMap m) this.m = m;public TreeSet()/以自然排序方式创建一个新的TreeMap，/根据该 TreeSet 创I建一个 TreeSet，/使用该TreeMap的key来保存Set集合的元素this(new TreeMap();public TreeSet(Comparator comparator)/以定制排序方式创建一个新的TreeM

3、ap，/根据该 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)/调用号构造器创建一个TreeSet，底层以TreeMap保存集合元素this(parator();/向 TreeSet中添加SortedSet集合s里的

4、所有元素 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 = (SortedSet) c;/把m集合强制转换为TreeMap集合TreeMap map = (TreeMap) m;Comparator cc = (Comparator) parator()

5、;Comparator mc = parator();/如果cc和mc两个Comparator相等 if (cc = mc | (cc != null & cc.equals(mc) 一把/ Collection中所有元素添加成TreeMap集合的key map.addAllForTreeSet(set, present); return true;/直接调用父类的addAll()方法来实现return super.addAll(c);.从上面代码可以看出，TreeSet的号、号构造器的都是新建一个TreeMap作为实际存储Set元素的容器，而另外2个构造器则分别依赖于号和 号构造器，由此可见

6、，TreeSet底层实际使用的存储容器就是TreeMap。与HashSet完全类似的是，TreeSet里绝大部分方法都是直接调用TreeMap的方法来实现的，这一点读者可以自行参阅TreeSet的源代码，此处就不再给 出了。对于TreeMap而言，它采用一种被称为“红黑树”的排序二叉树来保存Map中每个Entry每个Entry都被当成“红黑树”的一个节点对待。例如对于如下程 序而言：public class TreeMapTestpublic static void main(String args)TreeMap map =new TreeMap();map.put(ccc , 89.0);

7、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中，这个Entry就是该“红黑树的根节点。接着程序执行 map.put(aaa, 80.0);时，程序会将aaa-80.0作为新节点添加到已有的红黑树中。以后每向TreeMap中放入一个key-value对，系统都需要将该Entry当成一个新节点，添加成已有红黑树中，通过这种方式就可保证TreeMap中所有key总 是由小到

8、大地排列。例如我们输出上面程序，将看到如下结果(所有key由小到大地排列)：aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0回页首TreeMap的添加节点红黑树红黑树是一种自平衡排序二叉树，树中每个节点的值，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值，这确保 红黑树运行时可以快速地在树中查找和定位的所需节点。对于TreeMap而言，由于它底层采用一棵“红黑树”来保存集合中的Entry，这意味这TreeMap添加元素、取出元素的性能都比HashMap低：当TreeMap添 加元素时，需要通过循环找到新增Entry的插入位置，因

9、此比较耗性能；当从TreeMap中取出元素时，需要通过循环才能找到合适的Entry，也比较耗性能。 但TreeMap、TreeSet比HashMap、HashSet的优势在于：TreeMap中的所有Entry总是按key根据指定排序规则保持有序状态，TreeSet中所有元素总 是根据指定排序规则保持有序状态。为了理解TreeMap的底层实现，必须先介绍排序二叉树和红黑树这两种数据结构。其中红黑树又是一种特殊的排序二叉树。排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有节点的

10、值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 它的左、右子树也分别为排序二叉树。图1显示了一棵排序二叉树：对排序二叉树，若按中序遍历就可以得到由小到大的有序序列。如图1所示二叉树，中序遍历得:2， 3， 4， 8， 9， 9， 10， 13， 15， 18创建排序二叉树的步骤，也就是不断地向排序二叉树添加节点的过程，向排序二叉树添加节点的步骤如下：1. 以根节点当前节点开始搜索。2. 拿新节点的值和当前节点的值比较。3. 如果新节点的值更大，则以当前节点的右子节点作为新的当前节点；如果新节点的值更小，则以当前节点的左子节点作为新的当前节点。4. 重复

11、2、3两个步骤，直到搜索到合适的叶子节点为止。5. 将新节点添加为第4步找到的叶子节点的子节点；如果新节点更大，则添加为右子节点；否则添加为左子节点。掌握上面理论之后，下面我们来分析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里没有任何Entryif (t = null)

12、/将新的key-value创建一个Entry，并将该Entry作为rootroot = new Entry(key, value, null);/设置该Map集合的size为1，代表包含一个Entrysize = 1;/记录修改次数为1modCount+;return null;int cmp;Entry parent;Comparator cpr = comparator;/如果比较器cpr不为null，即表明采用定制排序if (cpr != null)do /使用parent上次循环后的t所引用的Entryparent = t;/拿新插入key和t的key进行比较cmp = pare(ke

13、y, t.key);/如果新插入的key小于t的key，t等于t的左边节点if (cmp 0) t = t.right;/如果两个key相等，新的value覆盖原有的value,/并返回原有的value elsereturn t.setValue(value); while (t != null);elseif (key = null)throw new NullPointerException();Comparable k = (Comparable) key; do /使用parent上次循环后的t所引用的Entry parent = t;/拿新插入key和t的key进行比较cmp = p

14、areTo(t.key);/如果新插入的key小于t的key，t等于t的左边节点if (cmp 0) t = t.right;/如果两个key相等，新的value覆盖原有的value，/并返回原有的value elsereturn t.setValue(value); while (t != null);/将新插入的节点作为parent节点的子节点Entry e = new Entry(key, value, parent);/如果新插入key小于parent的key，则e作为parent的左子节点 if (cmp -图4显示了被删除节点既有左子节点，又有右子节点的情形，此时我们采用到是第一种

15、方式进行维护: 图4.被删除节点既有左子树，又有右子树林P&子节直攻为可的子节点.将e，啊右r节点设为pi. f耐中时大任)节点的石于节点J图5显示了被删除节点既有左子树，又有右子树的情形，此时我们采用到是第二种方式进行维护:TreeMap删除节点采用图5所示右边的情形进行维护一一也就是用被删除节点的右子树中最小节点与被删节点交换的方式进行维护。 TreeMap删除节点的方法由如下方法实现：private void deleteEntry(Entry p)modCount+;size-;/如果被删除节点的左子树、右子树都不为空 if (p.left != null & p.right != n

16、ull)/用 p节点的中序后继节点代替p节点 Entry s = successor (p); p.key = s.key;p.value = s.value; p = s;/如果p节点的左节点存在，replacement代表左节点；否则代表右节点。Entry replacement = (p.left != null ? p.left : p.right); if (replacement != null) replacement.parent = p.parent;/如果p没有父节点，则replacemment变成父节点 if (p.parent = null)root = replace

17、ment;/如果p节点是其父节点的左子节点else if (p = p.parent.left) p.parent.left = replacement;/如果p节点是其父节点的右子节点 elsep.parent.right = replacement; p.left = p.right = p.parent = null;/修复红黑树if (p.color = BLACK) fixAfterDeletion(replacement);/如果p节点没有父节点else if (p.parent = null)root = null; else if (p.color = BLACK)/修复红黑树

18、fixAfterDeletion(p); /if (p.parent != null) /如果p是其父节点的左子节点if (p = p.parent.left) p.parent.left = null;/如果p是其父节点的右子节点else if (p = p.parent.right) p.parent.right = null;p.parent = null; 回页首红黑树排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉 树将变成链表：所有节点只有左节点（如果插入节点集本身是大到小排列）；或所有节点

19、只有右节点（如果插入节点集本身是小到大排列）。在这种情况下，排 序二叉树就变成了普通链表，其检索效率就会很差。为了改变排序二叉树存在的不足，Rudolf Bayer与1972年发明了另一种改进后的排序二叉树：红黑树，他将这种排序二叉树称为对称二叉B树”，而红黑树 这个名字则由Leo J. Guibas和Robert Sedgewick于1978年首次提出。红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组。典型地，JDK提供的集合类TreeMap本身就是一个红黑树的实现。红黑树在原有的排序二叉树增加了如下几个要求：Java实现的红黑树上面的性质3中指定红黑树的每个叶子节点都是空节点，而且

20、并叶子节点都是黑色。但Java实现的红黑树将使用null来代表空节点，因此遍历红黑树时将看 不到黑色的叶子节点，反而看到每个叶子节点都是红色的。 性质1：每个节点要么是红色，要么是黑色。 性质2：根节点永远是黑色的。 性质3：所有的叶节点都是空节点（即null），并且是黑色的。 性质4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点） 性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。Java中实现的红黑树可能有如图6所示结构：图6. Java红黑树的示意备注：本文中所有关于红黑树中的示意图采用白色代表红色。黑色节点还是采用了黑色表示。

21、根据性质5：红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的黑色高度 （black-height）。性质4则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑色高度为3的红黑树：从根节点到叶节点的最短路径长度 是2,该路径上全是黑色节点（黑节点-黑节点-黑节点）。最长路径也只可能为4,在每个黑色节点之间插入一个红色节点（黑节点-红节点-黑节点-红 节点-黑节点），性质4保证绝不可能插入更多的红色节点。由此可见，红黑树中最长路径就是一条红黑交替的路径。红黑树和平衡二叉树红黑树并不是真正的平衡二叉树，

22、但在实际应用中，红黑树的统计性能要高于平衡二叉树，但极端性能略差。由此我们可以得出结论：对于给定的黑色高度为N的红黑树，从根到叶子节点的最短路径长度为N-1，最长路径长度为2 * （N-1）。提示：排序二叉树的深度直接影响了检索的性能，正如前面指出，当插入节点本身就是由小到大排列时，排序二叉树将变成一个链表，这种排序二叉树的检索性 能最低：N个节点的二叉树深度就是N-1。红黑树通过上面这种限制来保证它大致是平衡白一一因为红黑树的高度不会无限增高，这样保证红黑树在最坏情况下都是高效的，不会出现普通排序二叉树的情 况。由于红黑树只是一个特殊的排序二叉树，因此对红黑树上的只读操作与普通排序二叉树上的

23、只读操作完全相同，只是红黑树保持了大致平衡，因此检索性能比排 序二叉树要好很多。但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征，因此插入操作和删除操作都需要进行一定的维护，以保证插入节点、删除节点后的树依 然是红黑树。回页首添加节点后的修复上面put（K key, V value）方法中号代码处使用fixAfterlnsertion（e）方法来修复红黑树一因此每次插入节点后必须进行简单修复，使该排序二叉 树满足红黑树的要求。插入操作按如下步骤进行：（1）以排序二叉树的方法插入新节点，并将它设为红色。（2）进行颜色调换和树旋转。插入后的修复在插入操作中，红黑树的性质1和性质3两个

24、永远不会发生改变，因此无需考虑红黑树的这两个特性。这种颜色调用和树旋转就比较复杂了，下面将分情况进行介绍。在介绍中，我们把新插入的节点定义为N节点，N节点的父节点定义为P节点，P节点的兄 弟节点定义为U节点，P节点父节点定义为G节点。下面分成不同情形来分析插入操作情形1：新节点N是树的根节点，没有父节点在这种情形下，直接将它设置为黑色以满足性质2。情形2：新节点的父节点P是黑色在这种情况下，新插入的节点是红色的，因此依然满足性质4。而且因为新节点N有两个黑色叶子节点；但是由于新节点N是红色，通过它的每个子节点的 路径依然保持相同的黑色节点数，因此依然满足性质5。情形3：如果父节点P和父节点的兄

25、弟节点U都是红色在这种情况下，程序应该将P节点、U节点都设置为黑色，并将P节点的父节点设为红色(用来保持性质5)。现在新节点N有了一个黑色的父节点P。 由于从P节点、U节点到根节点的任何路径都必须通过G节点，在这些路径上的黑节点数目没有改变(原来有叶子和G节点两个黑色节点，现在有叶子和P 两个黑色节点)。经过上面处理后，红色的G节点的父节点也有可能是红色的，这就违反了性质4，因此还需要对G节点递归地进行整个过程(把G当成是新插入的节点进 行处理即可)。图7显示了这种处理过程：备注：虽然图11.28绘制的是新节点N作为父节点P左子节点的情形，其实新节点N作为父节点P右子节点的情况与图11.28完

26、全相同。情形4：父节点P是红色、而其兄弟节点U是黑色或缺少；且新节点N是父节点P的右子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行一次左旋转对新节点和其父节点进行，接着按情形5处理以前的父节点P (也就是把P当成新插入的节点即可)。这导致某些路径 通过它们以前不通过的新节点N或父节点P的其中之一，但是这两个节点都是红色的，因此不会影响性质5。图8显示了对情形4的处理：备注：图11.29中P节点是G节点的左子节点，如果P节点是其父节点G节点的右子节点，那么上面的处理情况应该左、右对调一下。情形5：父节点P是红色、而其兄弟节点U是黑色或缺少；且新节点N是其父节点的左子节点，而父

27、节点P又是其父节点G的左子节点。在这种情形下，需要对节点G的一次右旋转，在旋转产生的树中，以前的父节点P现在是新节点N和节点G的父节点。由于以前的节点G是黑色，否则 父节点P就不可能是红色，我们切换以前的父节点P和节点G的颜色，使之满足性质4,性质5也仍然保持满足，因为通过这三个节点中任何一个的所有 路径以前都通过节点G，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。图9显示了情形5的处理过程：备注：图11.30中P节点是G节点的左子节点，如果P节点是其父节点G节点的右子节点，那么上面的处理情况应该左、右对调一下。TreeMap为插入节点后的修复操作由fixAf

28、terInsertion(Entry x)方法提供，该方法的源代码如下：/插入节点后修复红黑树private void fixAfterlnsertion(Entry x)x.color = RED;/直到x节点的父节点不是根，且x的父节点不是红色while (x != null & x != root& x.parent.color = RED)/如果x的父节点是其父节点的左子节点if (parentOf(x) = leftOf(parentOf(parentOf(x)/获取x的父节点的兄弟节点Entry y = rightOf(parentOf(parentOf(x);/如果x的父节点的兄

29、弟节点是红色if (colorOf(y) = red)将x的父节点设为黑色setColor(parentOf(x), black);、将x的父节点的兄弟节点设为黑色setColor(y, BLACK);、将x的父节点的父节点设为红色setColor(parentOf(parentOf(x), red);x = parentOf(parentOf(x);/如果x的父节点的兄弟节点是黑色else如果 x是其父节点的右子节点if (x = rightOf(parentOf(x)将/x的父节点设为xx = parentOf(x);rotateLeft(x);把/ x的父节点设为黑色setColor(p

30、arentOf(x), black);把/ x的父节点的父节点设为红色setColor(parentOf(parentOf(x), red);rotateRight(parentOf(parentOf(x);/如果x的父节点是其父节点的右子节点else/获取x的父节点的兄弟节点Entry y = leftOf(parentOf(parentOf(x);/如果x的父节点的兄弟节点是红色if (colorOf(y) = red)将x的父节点设为黑色。setColor(parentOf(x), black);将x的父节点的兄弟节点设为黑色setColor(y, BLACK);、将x的父节点的父节点设

31、为红色setColor(parentOf(parentOf(x), red);将x设为x的父节点的节点x = parentOf(parentOf(x);/如果x的父节点的兄弟节点是黑色else/果 x是其父节点的左子节点if (x = leftOf(parentOf(x)将/x的父节点设为xx = parentOf(x);rotateRight(x);把/ x的父节点设为黑色setColor(parentOf(x), black);把/ x的父节点的父节点设为红色setColor(parentOf(parentOf(x), red);rotateLeft(parentOf(parentOf(x

32、);/将根节点设为黑色root.color = BLACK;回页首删除节点后的修复与添加节点之后的修复类似的是，TreeMap删除节点之后也需要进行类似的修复操作，通过这种修复来保证该排序二叉树依然满足红黑树特征。大家可以参考插入节点之后的修复来分析删除之后的修复。TreeMap在删除之后的修复操作由fixAfterDeletion(Entry x)方法提供，该方法源代码如下：/删除节点后修复红黑树private void fixAfterDeletion(Entry x)/直到x不是根节点，且x的颜色是黑色while (x != root & colorOf(x) = BLACK)/如果x是

33、其父节点的左子节点if (x = leftOf(parentOf(x)/获取x节点的兄弟节点Entry sib = rightOf(parentOf(x);/如果sib节点是红色if (colorOf(sib) = red)将sib节点设为黑色setColor(sib, black);、将x的父节点设为红色setColor(parentOf(x), red);rotateLeft(parentOf(x);次将sib设为x的父节点的右子节点sib = rightOf(parentOf(x);/如果sib的两个子节点都是黑色if (colorOf(leftOf(sib) = black& colo

34、rOf(rightOf(sib) = BLACK)将/ sib设为红色setColor(sib, red);让x等于x的父节点x = parentOf(x);else如果 sib的只有右子节点是黑色if (colorOf(rightOf(sib) = BLACK) 将/sib的左子节点也设为黑色setColor(leftOf(sib), black);将/sib设为红色setColor(sib, red);rotateRight(sib);sib = rightOf(parentOf(x);设置sib的颜色与x的父节点的颜色相同setColor(sib, colorOf(parentOf(x)

35、;、将x的父节点设为黑色setColor(parentOf(x), black);、将sib的右子节点设为黑色setColor(rightOf(sib), BLACK);rotateLeft(parentOf(x);x = root;/如果x是其父节点的右子节点else/获取x节点的兄弟节点Entry sib = leftOf(parentOf(x);/如果sib的颜色是红色if (colorOf(sib) = red)将sib的颜色设为黑色setColor(sib, black);将sib的父节点设为红色setColor(parentOf(x), red);rotateRight(paren

36、tOf(x);sib = leftOf(parentOf(x);/如果sib的两个子节点都是黑色if (colorOf(rightOf(sib) = BLACK& colorOf(leftOf(sib) = black)将/ sib设为红色setColor(sib, red);让x等于x的父节点x = parentOf(x);else如果sib只有左子节点是黑色if (colorOf(leftOf(sib) = black)将/sib的右子节点也设为黑色setColor(rightOf(sib), BLACK);将/sib设为红色setColor(sib, red); rotateLeft(s

37、ib);sib = leftOf(parentOf(x);将/ sib的颜色设为与x的父节点颜色相同setColor(sib, colorOf(parentOf(x);将x的父节点设为黑色setColor(parentOf(x), black);将sib的左子节点设为黑色setColor(leftOf(sib), black);rotateRight(parentOf(x);x = root;setColor(x, black);回页首检索节点当TreeMap根据key来取出value时，TreeMap对应的方法如下：public V get(Object key)/根据指定key取出对应的E

38、ntryEntryK,V p = getEntry(key);/返回该Entry所包含的valuereturn (p=null ? null : p.value);从上面程序的粗体字代码可以看出，get(Object key)方法实质是由于getEntry()方法实现的，这个getEntry()方法的代码如下：final Entry getEntry(Object key)/如果comparator不为null，表明程序采用定制排序if (comparator != null)/调用getEntryusingComparator方法来取出对应的keyreturn getEntryUsingCo

39、mparator(key);/如果key形参的值为null，抛出NullPointerException异常if (key = null)throw new NullPointerException();/将key强制类型转换为Comparable实例Comparable k = (Comparable) key;/从树的根节点开始Entry p = root;while (p != null)/拿 key与当前节点的key进行比较int cmp = pareTo(p.key);/如果key小于当前节点的key，向“左子树”搜索if (cmp 0)p = p.right;/不大于、不小于，就是

40、找到了目标Entryelsereturn p;return null;上面的getEntry(Object obj)方法也是充分利用排序二叉树的特征来搜索目标Entry，程序依然从二叉树的根节点开始，如果被搜索节点大于当前节点，程序向“右 子树”搜索；如果被搜索节点小于当前节点，程序向“左子树”搜索；如果相等，那就是找到了指定节点。当TreeMap里的comparator != null即表明该TreeMap采用了定制排序，在采用定制排序的方式下，TreeMap采用getEntryUsingComparator(key)方法 来根据key获取Entry。下面是该方法的代码：final Entry getEntryUsingComparator(Object key)K k = (k) key;/获取该 TreeMap 的 comparatorComparator cpr = comparator;if (cpr != null)/从根节点开始Entry p = root;while (p != null)/拿key与当前节点的key进行比较i