上面程序中的两个do…while就是实现”排序二叉树”的关键算法。每当程序希望添加新节点时，总是从树的根节点开始比较，即将根节点当成当前节点。
如果新增节点大于当前节点且当前节点的右子节点存在，则以右子节点作为当前节点。并继续循环
如果新增节点小于当前节点且当前节点的左子节点存在，则以左子节点作为当前节点。并继续循环
如果新增节点等于当前节点，则新增节点覆盖当前节点，并结束循环。
当TreeMap根据key来取出value时，TreeMap对应的方法如下:
public V get(Object key) { //根据key取出Entry Entry<K,V> p = getEntry(key); //取出Entry所包含的value return (p==null ? null : p.value); }现在我们可以知道，其实get(Object key)方法实质上是由getEntry()方法实现的。现在我们来看getEntry(Object key)的源码:
final Entry<K,V> getEntry(Object key) { // 如果有比较器，返回getEntryUsingComparator(Object key)的结果 if (comparator != null) 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 = k.compareTo(p.key); // key小于当前节点的key if (cmp < 0) // p “移动”到左节点上 p = p.left; // key大于当前节点的key else if (cmp > 0) // p “移动”到右节点上 p = p.right; // key值相等则当前节点就是要找的节点 else // 返回找到的节点 return p; } // 没找到则返回null return null; }getEntry(Object obj)方法也是充分利用排序二叉树的特性来搜索目标Entry。程序依然从二叉数的根节点开始，如果被搜索节点大于当前节点，程序向”右子树”搜索，如果小于，则向”左子树”搜索。如果相等则说明找到了指定节点。
我们观察到当该TreeMap采用了定制排序。在采用定制排序的方式下，TreeMap采用getEntryUsingComparator(key)方法来根据key获取Entry。
final Entry<K,V> getEntryUsingComparator(Object key) { K k = (K) key; // 获取比较器 Comparator<? super K> cpr = comparator; // 其实在调用此方法的get(Object key)中已经对比较器为null的情况进行判断，这里是防御性的判断 if (cpr != null) { // 获取根节点 Entry<K,V> p = root; // 遍历树 while (p != null) { // 获取key和当前节点的key的比较结果 int cmp = cpr.compare(k, p.key); // 查找的key值较小 if (cmp < 0) // p“移动”到左孩子 p = p.left; // 查找的key值较大 else if (cmp > 0) // p“移动”到右节点 p = p.right; // key值相等 else // 返回找到的节点 return p; } } // 没找到key值对应的节点，返回null return null; }其实getEntry()和getEntryUsingComparator()这两个方法实现思路几乎完全类似。只是前者对自然排序的TreeMap获取有效，后者对定制排序的TreeMap有效。
通过上述源码其实不难看出，TreeMap这个工具类的实现其实很简单。或者说，从本质上来说TreeMap就是一棵”红黑树”，每个Entry就是一个节点。