java中treemap和treeset实现红黑树

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()     // ① {  // 以自然排序方式创建一个新的 TreeMap， // 根据该 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(s.comparator());  // 向 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>) set.comparator();   Comparator<? super E> mc = map.comparator();   // 如果 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);  }  ...  }