java中treemap和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); 
 } 
 ... 
 } 

 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); 
 } 
 } 

 {aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0} 

 public V put(K key, V value) 
 { 
 // 先以 t 保存链表的 root 节点
 Entry<K,V> t = root; 
 // 如果 t==null，表明是一个空链表，即该 TreeMap 里没有任何 Entry 
 if (t == null) 
 { 
 // 将新的 key-value 创建一个 Entry，并将该 Entry 作为 root 
 root = new Entry<K,V>(key, value, null); 
 // 设置该 Map 集合的 size 为 1，代表包含一个 Entry 
 size = 1; 
 // 记录修改次数为 1 
 modCount++; 
 return null; 
 } 
 int cmp; 
 Entry<K,V> parent; 
 Comparator<? super K> cpr = comparator; 
 // 如果比较器 cpr 不为 null，即表明采用定制排序
 if (cpr != null) 
 { 
 do { 
  // 使用 parent 上次循环后的 t 所引用的 Entry 
  parent = t; 
  // 拿新插入 key 和 t 的 key 进行比较
  cmp = cpr.compare(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，
  // 并返回原有的 value 
  else 
  return 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 = k.compareTo(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，
  // 并返回原有的 value 
  else 
  return 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 的右子节点
 else 
 parent.right = e; 
 // 修复红黑树
 fixAfterInsertion(e);    // ①
 size++; 
 modCount++; 
 return null; 
 }

 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 节点是其父节点的右子节点
 else 
 p.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; 
 } 
 } 
 } 

 // 插入节点后修复红黑树
 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 的父节点设为 x 
   x = 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 的父节点设为 x 
   x = parentOf(x); 
   rotateRight(x); 
  } 
  // 把 x 的父节点设为黑色
  setColor(parentOf(x), BLACK); 
  // 把 x 的父节点的父节点设为红色
  setColor(parentOf(parentOf(x)), RED); 
  rotateLeft(parentOf(parentOf(x))); 
  } 
 } 
 } 
 // 将根节点设为黑色
 root.color = BLACK; 
 } 

 // 删除节点后修复红黑树
 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); 
 } 

 public V get(Object key) 
 { 
 // 根据指定 key 取出对应的 Entry 
 Entry>K,V< p = getEntry(key); 
 // 返回该 Entry 所包含的 value 
 return (p==null ? null : p.value); 
 } 

 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 = k.compareTo(p.key); 
 // 如果 key 小于当前节点的 key，向“左子树”搜索
 if (cmp < 0) 
  p = p.left; 
 // 如果 key 大于当前节点的 key，向“右子树”搜索
 else if (cmp > 0) 
  p = p.right; 
 // 不大于、不小于，就是找到了目标 Entry 
 else 
  return p; 
 } 
 return null; 
 } 

 final Entry<K,V> getEntryUsingComparator(Object key) 
 { 
 K k = (K) key; 
 // 获取该 TreeMap 的 comparator 
 Comparator<? super K> cpr = comparator; 
 if (cpr != null) 
 { 
 // 从根节点开始
 Entry<K,V> p = root; 
 while (p != null) 
 { 
  // 拿 key 与当前节点的 key 进行比较
  int cmp = cpr.compare(k, p.key); 
  // 如果 key 小于当前节点的 key，向“左子树”搜索
  if (cmp < 0) 
  p = p.left; 
  // 如果 key 大于当前节点的 key，向“右子树”搜索
  else if (cmp > 0) 
  p = p.right; 
  // 不大于、不小于，就是找到了目标 Entry 
  else 
  return p; 
 } 
 } 
 return null; 
 }