TreeMap 红黑树算法实现.docx

通过分析JDK源代码研究TreeMap红黑树算法实现李刚,自由撰稿人简介：TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员， 其中TreeMap是Map接口的常用实现类，而TreeSet是Set接口的常用实现 类。虽然HashMap和HashSet实现的接口规范不同，但TreeSet底层是通过 TreeMap来实现的，因此二者的实现方式完全一样。而TreeMap的实现就是红 黑树算法。发布日期：2010年5月25日级别：初级建议：1 (查看或添加评论)土土芝X彦平均分(共16个评分)TreeMap的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样 就可以保证当需要快速检索指定节点。TreeSet 和 TreeMap 的关系为了让大家了解TreeMap和TreeSet之间的关系，下面先看TreeSet类的部 分源代码：public class TreeSet<E> extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable(/使用NavigableMap的key来保存Set集合的元素private transient NavigableMap<E,Object> m;/使用一个PRESENT作为Map集合的所有value。private static final Object PRESENT = new Object();/包访问权限的构造器，以指定的NavigableMap对象创建Set集合 TreeSet(NavigableMap<E,Object> m)(this.m = m;public TreeSet()/ (/根据该TreeSet创建一个TreeSet,/使用该TreeMap的key来保存Set集合的元素 this(new TreeMap<E,Object>();public TreeSet(Comparator<? super E> comparator) / (/以定制排序方式创建一个新的TreeMap，/根据该TreeSet创建一个TreeSet，/使用该TreeMap的key来保存Set集合的元素this(new TreeMap<E,Object>(comparator);public TreeSet(Collection<? extends E> c)(/调用号构造器创建一个TreeSet，底层以TreeMap保存集合元素 this();/向TreeSet中添加Collection集合c里的所有元素 addAll(c);public TreeSet(SortedSet<E> s)(/调用号构造器创建一个TreeSet，底层以TreeMap保存集合元素 this(parator();/向TreeSet中添加SortedSet集合s里的所有元素addAll(s);/TreeSet的其他方法都只是直接调用TreeMap的方法来提供实现.public boolean addAll(Collection<? extends E> c)(if (m.size() = 0 && c.size() > 0 &&c instanceof SortedSet &&m instanceof TreeMap)(/把c集合强制转换为SortedSet集合SortedSet<? extends E> set = (SortedSet<? extends E>) c;/把m集合强制转换为TreeMap集合TreeMap<E,Object> map = (TreeMap<E, Object>) m;Comparator<? super E> cc = (Comparator<? super E>) parator();Comparator<? super E> mc = parator();/如果cc和mc两个Comparator相等if (cc = mc | (cc != null && cc.equals(mc)(map.addAllForTreeSet(set, PRESENT); return true;/直接调用父类的addAll()方法来实现 return super.addAll(c);.从上面代码可以看出，TreeSet的号、号构造器的都是新建一个TreeMap 作为实际存储Set元素的容器，而另外2个构造器则分别依赖于号和 号构造器，由此可见，TreeSet底层实际使用的存储容器就是TreeMap。与HashSet完全类似的是，TreeSet里绝大部分方法都是直接调用TreeMap的 方法来实现的，这一点读者可以自行参阅TreeSet的源代码，此处就不再给出 了。对于TreeMap而言，它采用一种被称为“红黑树”的排序二叉树来保存Map中 每个Entry 每个Entry都被当成“红黑树”的一个节点对待。例如对于如下程序而言：public class TreeMapTest(public static void main(String args)(TreeMap<String , Double> map =new TreeMap<String , Double>();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中，这个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的添加节点红黑树红黑树是一种自平衡排序二叉树，树中每个节点的值，都大于或等于在它的左子 树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值，这确保 红黑树运行时可以快速地在树中查找和定位的所需节点。对于TreeMap而言，由于它底层采用一棵“红黑树”来保存集合中的Entry， 这意味这TreeMap添加元素、取出元素的性能都比HashMap低：当TreeMap添 加元素时，需要通过循环找到新增Entry的插入位置，因此比较耗性能；当从 TreeMap中取出元素时，需要通过循环才能找到合适的Entry，也比较耗性能。 但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entry总是按key根据指定排序规则保持有序状态，TreeSet中所有元素总是 根据指定排序规则保持有序状态。为了理解TreeMap的底层实现，必须先介绍排序二叉树和红黑树这两种数据结 构。其中红黑树又是一种特殊的排序二叉树。排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序 和检索。排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 它的左、右子树也分别为排序二叉树。图1显示了一棵排序二叉树：图1.排序二叉树对排序二叉树，若按中序遍历就可以得到由小到大的有序序列。如图1所示二 叉树，中序遍历得：2，3，4，8，9，9，10，13，15，18)创建排序二叉树的步骤，也就是不断地向排序二叉树添加节点的过程，向排序二 叉树添加节点的步骤如下：1. 以根节点当前节点开始搜索。2. 拿新节点的值和当前节点的值比较。3. 如果新节点的值更大，则以当前节点的右子节点作为新的当前节点；如果 新节点的值更小，则以当前节点的左子节点作为新的当前节点。4. 重复2、3两个步骤，直到搜索到合适的叶子节点为止。5. 将新节点添加为第4步找到的叶子节点的子节点；如果新节点更大，则 添加为右子节点；否则添加为左子节点。掌握上面理论之后，下面我们来分析TreeMap添加节点(TreeMap中使用Entry 内部类代表节点)的实现，TreeMap集合的put(K key, V value)方法实现了 将Entry放入排序二叉树中，下面是该方法的源代码：public V put(K key, V value)(/先以t保存链表的root节点Entry<K,V> t = root;/如果t=null，表明是一个空链表，即该TreeMap里没有任何Entryif (t = null)(/将新的key-value创建一个Entry，并将该Entry作为rootroot = new Entry<K,V>(key, value, null);/设置该Map集合的size为1，代表包含一个Entrysize = 1;/记录修改次数为1modCount+;return null;int cmp;Entry<K,V> parent;Comparator<? super K> cpr = comparator;/如果比较器cpr不为null，即表明采用定制排序if (cpr != null)(do (/使用parent上次循环后的t所引用的Entryparent = t;/拿新插入key和t的key进行比较cmp = pare(key, t.key);/如果新插入的key小于t的key，t等于t的左边节点if (cmp < 0)t = t.left;/如果新插入的key大于t的key，t等于t的右边节点else if (cmp > 0)t = t.right;/如果两个key相等，新的value覆盖原有的value，/并返回原有的valueelsereturn t.setValue(value); while (t != null);else(if (key = null)throw new NullPointerException();Comparable<? super K> k = (Comparable<? super K>) key;do (/使用parent上次循环后的t所引用的Entry parent = t;/拿新插入key和t的key进行比较cmp = pareTo(t.key);/如果新插入的key小于t的key, t等于t的左边节点if (cmp < 0)t = t.left;/如果新插入的key大于t的key，t等于t的右边节点else if (cmp > 0)t = t.right;/如果两个key相等，新的value覆盖原有的value，/并返回原有的valueelsereturn t.setValue(value); while (t != null);/将新插入的节点作为parent节点的子节点Entry<K,V> e = new Entry<K,V>(key, value, parent);/如果新插入key小于parent的key，则e作为parent的左子节点if (cmp < 0)parent.left = e;/如果新插入key小于parent的key，则e作为parent的右子节点 elseparent.right = e;/修复红黑树fixAfterInsertion(e);/ size+;modCount+;return null;上面程序中粗体字代码就是实现“排序二叉树”的关键算法，每当程序希望添加 新节点时：系统总是从树的根节点开始比较一一即将根节点当成当前节点，如 果新增节点大于当前节点、并且当前节点的右子节点存在，则以右子节点作为当 前节点；如果新增节点小于当前节点、并且当前节点的左子节点存在，则以左子 节点作为当前节点；如果新增节点等于当前节点，则用新增节点覆盖当前节点， 并结束循环一一直到找到某个节点的左、右子节点不存在，将新节点添加该节 点的子节点 如果新节点比该节点大，则添加为右子节点；如果新节点比该 节点小，则添加为左子节点。回页首TreeMap的删除节点当程序从排序二叉树中删除一个节点之后，为了让它依然保持为排序二叉树，程 序必须对该排序二叉树进行维护。维护可分为如下几种情况：（1）被删除的节点是叶子节点，则只需将它从其父节点中删除即可。（2）被删除节点p只有左子树，将p的左子树pL添加成p的父节点的左子 树即可；被删除节点p只有右子树，将p的右子树pR添加成p的父节点的 右子树即可。（3）若被删除节点p的左、右子树均非空，有两种做法：将pL设为p的父节点q的左或右子节点（取决于p是其父节点q的 左、右子节点），将pR设为p节点的中序前趋节点s的右子节点（s是 pL最右下的节点，也就是pL子树中最大的节点）。以p节点的中序前趋或后继替代p所指节点，然后再从原排序二叉树中 删去中序前趋或后继节点即可。（也就是用大于p的最小节点或小于p 的最大节点代替p节点即可）。图2显示了被删除节点只有左子树的示意图：图2.被删除节点只有左子树图3显示了被删除节点只有右子树的示意图:图3.被删除节点只有右子树图4显示了被删除节点既有左子节点，又有右子节点的情形，此时我们米用到 是第一种方式进行维护：图4.被删除节点既有左子树，又有右子树图5显示了被删除节点既有左子树，又有右子树的情形，此时我们采用到是第 二种方式进行维护：图5.被删除节点既有左子树，又有右子树TreeMap删除节点采用图5所示右边的情形进行维护一一也就是用被删除节点 的右子树中最小节点与被删节点交换的方式进行维护。TreeMap删除节点的方法由如下方法实现：private void deleteEntry(Entry<K,V> p)(modCount+;size-;/如果被删除节点的左子树、右子树都不为空if (p.left != null && p.right != null)(/用p节点的中序后继节点代替p节点Entry<K,V> s = successor (p);p.key = s.key;p.value = s.value;p = s;/如果p节点的左节点存在,replacement代表左节点；否则代表右节点。Entry<K,V> replacement = (p.left != null ? p.left : p.right);if (replacement != null)(replacement.parent = p.parent;/如果p没有父节点，则replacemment变成父节点if (p.parent = null)root = replacement;/如果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)/修复红黑树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;回页首红黑树排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是 有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉 树将变成链表：所有节点只有左节点（如果插入节点集本身是大到小排列）；或 所有节点只有右节点（如果插入节点集本身是小到大排列）。在这种情况下，排 序二叉树就变成了普通链表，其检索效率就会很差。为了改变排序二叉树存在的不足，Rudolf Bayer与1972年发明了另一种改进 后的排序二叉树：红黑树，他将这种排序二叉树称为“对称二叉B树”，而红 黑树这个名字则由Leo J. Guibas和Robert Sedgewick于1978年首次提出。红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组。典型地，JDK提 供的集合类TreeMap本身就是一个红黑树的实现。红黑树在原有的排序二叉树增加了如下几个要求：Java实现的红黑树上面的性质3中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是 黑色。但Java实现的红黑树将使用null来代表空节点，因此遍历红黑树时将 看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。性质1：每个节点要么是红色，要么是黑色。性质2：根节点永远是黑色的。性质3：所有的叶节点都是空节点（即null），并且是黑色的。性质4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径 上不会有两个连续的红色节点）性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑 色节点。Java中实现的红黑树可能有如图6所示结构：图6. Java红黑树的示意备注：本文中所有关于红黑树中的示意图采用白色代表红色。黑色节点还是采用 了黑色表示。根据性质5：红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点， 因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度(black-height)”。性质4则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径 的两倍。假如有一棵黑色高度为3的红黑树：从根节点到叶节点的最短路径长 度是2,该路径上全是黑色节点(黑节点-黑节点-黑节点)。最长路径也只 可能为4，在每个黑色节点之间插入一个红色节点(黑节点-红节点-黑节点 -红节点-黑节点)，性质4保证绝不可能插入更多的红色节点。由此可见， 红黑树中最长路径就是一条红黑交替的路径。红黑树和平衡二叉树红黑树并不是真正的平衡二叉树，但在实际应用中，红黑树的统计性能要高于平 衡二叉树，但极端性能略差。由此我们可以得出结论：对于给定的黑色高度为N的红黑树，从根到叶子节点 的最短路径长度为N-1，最长路径长度为2 * (N-1)。提示：排序二叉树的深度直接影响了检索的性能，正如前面指出，当插入节点本 身就是由小到大排列时，排序二叉树将变成一个链表，这种排序二叉树的检索性 能最低：N个节点的二叉树深度就是N-1。红黑树通过上面这种限制来保证它大致是平衡的一一因为红黑树的高度不会无 限增高，这样保证红黑树在最坏情况下都是高效的，不会出现普通排序二叉树的 情况。由于红黑树只是一个特殊的排序二叉树，因此对红黑树上的只读操作与普通排序 二叉树上的只读操作完全相同，只是红黑树保持了大致平衡，因此检索性能比排 序二叉树要好很多。但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征，因此插 入操作和删除操作都需要进行一定的维护，以保证插入节点、删除节点后的树依 然是红黑树。回页首添加节点后的修复上面put(K key, V value)方法中号代码处使用fixAfterlnsertion(e)方 法来修复红黑树一一因此每次插入节点后必须进行简单修复，使该排序二叉树满 足红黑树的要求。插入操作按如下步骤进行:（1）以排序二叉树的方法插入新节点，并将它设为红色。（2）进行颜色调换和树旋转。插入后的修复在插入操作中，红黑树的性质1和性质3两个永远不会发生改变，因此无需考 虑红黑树的这两个特性。这种颜色调用和树旋转就比较复杂了，下面将分情况进行介绍。在介绍中，我们 把新插入的节点定义为N节点，N节点的父节点定义为P节点，P节点的兄弟 节点定义为U节点，P节点父节点定义为G节点。下面分成不同情形来分析插入操作情形1：新节点N是树的根节点，没有父节点在这种情形下，直接将它设置为黑色以满足性质2。情形2：新节点的父节点P是黑色在这种情况下，新插入的节点是红色的，因此依然满足性质4。而且因为新节点 N有两个黑色叶子节点；但是由于新节点N是红色，通过它的每个子节点的路 径依然保持相同的黑色节点数，因此依然满足性质5。情形3：如果父节点P和父节点的兄弟节点U都是红色在这种情况下，程序应该将P节点、U节点都设置为黑色，并将P节点的父节 点设为红色（用来保持性质5）。现在新节点N有了一个黑色的父节点P。由 于从P节点、U节点到根节点的任何路径都必须通过G节点，在这些路径上的 黑节点数目没有改变（原来有叶子和G节点两个黑色节点，现在有叶子和P两 个黑色节点）。经过上面处理后，红色的G节点的父节点也有可能是红色的，这就违反了性质4, 因此还需要对G节点递归地进行整个过程（把G当成是新插入的节点进行处理 即可）。图7显示了这种处理过程：图7.插入节点后进行颜色调换备注：虽然图11.28绘制的是新节点N作为父节点P左子节点的情形，其实 新节点N作为父节点P右子节点的情况与图11.28完全相同。情形4：父节点P是红色、而其兄弟节点U是黑色或缺少；且新节点N是父 节点P的右子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行一次左旋转对新节点和其父节点进行，接着按情形5处 理以前的父节点P （也就是把P当成新插入的节点即可）。这导致某些路径通 过它们以前不通过的新节点N或父节点P的其中之一，但是这两个节点都是红 色的，因此不会影响性质5。图8显示了对情形4的处理:图8.插入节点后的树旋转备注：图11.29中P节点是G节点的左子节点，如果P节点是其父节点G节 点的右子节点，那么上 面的处理情况应该左、右对调一下。情形5：父节点P是红色、而其兄弟节点U是黑色或缺少；且新节点N是其 父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，需要对节点G的一次右旋转，在旋转产生的树中，以前的父节 点P现在是新节点N和节点G的父节点。由于以前的节点G是黑色，否则父 节点P就不可能是红色，我们切换以前的父节点P和节点G的颜色，使之满 足性质4,性质5也仍然保持满足，因为通过这三个节点中任何一个的所有路 径以前都通过节点G，现在它们都通过以前的父节点P。在各自的情形下，这都 是三个节点中唯一的黑色节点。图9显示了情形5的处理过程：图9.插入节点后的颜色调整、树旋转备注：图11.30中P节点是G节点的左子节点，如果P节点是其父节点G节 点的右子节点，那么上面的处理情况应该左、右对调一下。TreeMap为插入节点后的修复操作由fixAfterInsertion(Entry<K,V> x)方法 提供，该方法的源代码如下：/插入节点后修复红黑树private void fixAfterInsertion(Entry<K,V> 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<K,V> y = rightOf(parentOf(parentOf(x);/如果X的父节点的兄弟节点是红色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(parentOf(x), BLACK);/把x的父节点的父节点设为红色setColor(parentOf(parentOf(x), RED);rotateRight(parentOf(parentOf(x);/如果x的父节点是其父节点的右子节点else(/获取x的父节点的兄弟节点Entry<K,V> y = leftOf(parentOf(parentOf(x);/如果x的父节点的兄弟节点是红色if (colorOf(y) = RED)(/将x的父节点设为黑色。setColor(parentOf(x), BLACK);/将x的父节点的兄弟节点设为黑色setColor(y, BLACK);/将x的父节点的父节点设为红色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);/将根节点设为黑色root.color = BLACK;回页首删除节点后的修复与添加节点之后的修复类似的是，TreeMap删除节点之后也需要进行类似的修复 操作，通过这种修复来保证该排序二叉树依然满足红黑树特征。大家可以参考插 入节点之后的修复来分析删除之后的修复。TreeMap在删除之后的修复操作由 fixAfterDeletion(Entry<K,V> x)方法提供，该方法源代码如下：/删除节点后修复红黑树private void fixAfterDeletion(Entry<K,V> x)(/直到x不是根节点，且x的颜色是黑色while (x != root && colorOf(x) = BLACK)(/如果x是其父节点的左子节点if (x = leftOf(parentOf(x)(/获取x节点的兄弟节点Entry<K,V> 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&& colorOf(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);/将x的父节点设为黑色setColor(parentOf(x), BLACK);/将sib的右子节点设为黑色 setColor(rightOf(sib), BLACK);rotateLeft(parentOf(x);x = root;/如果x是其父节点的右子节点else/获取X节点的兄弟节点Entry<K,V> sib = leftOf(parentOf(x);/如果sib的颜色是红色if (colorOf(sib) = RED)(/将sib的颜色设为黑色setColor(sib, BLACK);/将sib的父节点设为红色setColor(parentOf(x), RED);rotateRight(parentOf(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(sib);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取出对应的EntryEntry>K,V< p = getEntry(key);/返回该Entry所包含的value return (p=null ? null : p.value);从上面程序的粗体字代码可以看出，get(Object key)方法实质是由于 getEntry()方法实现的，这个getEntry()方法的代码如下：final Entry<K,V> getEntry(Object key)(/如果comparator不为null，表明程序采用定制排序if (comparator != null)/调用getEntryUsingComparator方法来取出对应的key return getEntryUsingComparator(key);/如果key形参的值为null，抛出NullPointerException异常if (key = null)throw new NullPointerException();/将key强制类型转换为Comparable实例Comparable<? super K> k = (Comparable<? super K>) key;/从树的根节点开始Entry<K,V> p = root;while (p != null)(/拿key与当前节点的key进行比较int cmp = pareTo(p.key);/如果key小于当前节点的key，向“左子树”搜索if (cmp < 0)p = p.left;/如果key大于当前节点的key，向“右子树”搜索else if (cmp > 0)p = p.right;/不大于、不小于，就是找到了目标Entryelsereturn p;return null;上面的getEntry(Object obj)方法也是充分利用排序二叉树的特征来搜索目 标Entry，程序依然从二叉树的根节点开始，如果被搜索节点大于当前节点，程 序向“右子树”