如何实现TreeMap

这篇文章给大家分享的是有关如何实现TreeMap的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

/**

• The comparator used to maintain order in this tree map, or

• null if it uses the natural ordering of its keys.

• 
  

• @serial
  */
  //自然排序
  private final Comparator<? super K> comparator;
  //根节点
  private transient Entry<K,V> root;

  /**

• The number of entries in the tree
  */
  //大小
  private transient int size = 0;

public TreeMap() {
comparator = null;
}

public V put(K key, V value) {
Entry<K,V> t = root;//红黑树的根节点
if (t == null) {
compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);//构造根节点，root没有父节点，传入null         size = 1;         modCount++;         return null;     }     int cmp;     Entry<K,V> parent;  //定义节点     // split comparator and comparable paths     Comparator<? super K> cpr = comparator; //获得比较器     if (cpr != null) {//定义了比较器，采用自定义比较器进行比较         do {             parent = t;//将红黑树根节点赋值给parent             cmp = cpr.compare(key, t.key);             if (cmp < 0)                 t = t.left;//指向左子节点             else if (cmp > 0)                 t = t.right;//指向右子节点             else                 return t.setValue(value);         } while (t != null);     }     else {         //自然排序，没有指定比较器         if (key == null)             throw new NullPointerException();         @SuppressWarnings("unchecked")             Comparable<? super K> k = (Comparable<? super K>) key;         do {             parent = t;             cmp = k.compareTo(t.key);             if (cmp < 0)                 t = t.left;//左子节点             else if (cmp > 0)                 t = t.right;//右子节点             else                 return t.setValue(value);         } while (t != null);     }     //创建新节点，并指定父点     Entry<K,V> e = new Entry<>(key, value, parent);     if (cmp < 0)         parent.left = e;     else         parent.right = e;     //新插入节点后重新调整红黑树     fixAfterInsertion(e);     size++;     modCount++;     return null; } /** From CLR */ private void fixAfterInsertion(Entry<K,V> x) {     //加入的节点默认的颜色是红色     x.color = RED;     //情形1：新节点x是树的根节点，没有父节点不需要任何操作     //情形2：新节点x的父节点颜色是黑色的，不需要操作     while (x != null && x != root && x.parent.color == RED) {         //情形3：新节点的父节点颜色是红色的         //判断x的节点的父节点位置，是否属于左子节点         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {             //获取x节点的父节点的兄弟节点，上面语句已经判断出x节点的父节点为左子节点，所以直接取右子节点             Entry<K,V> y = rightOf(parentOf(parentOf(x)));             //判断是否x节点的父节点的兄弟节点为红色             if (colorOf(y) == RED) {                 setColor(parentOf(x), BLACK);//x节点的父节点设置为黑色                 setColor(y, BLACK);//y节点的颜色设置为黑色                 setColor(parentOf(parentOf(x)), RED);//x的父节点的父节点设置为红色                 x = parentOf(parentOf(x));             } else {                 if (x == rightOf(parentOf(x))) {                     x = parentOf(x);                     rotateLeft(x);                 }                 setColor(parentOf(x), BLACK);                 setColor(parentOf(parentOf(x)), RED);                 rotateRight(parentOf(parentOf(x)));             }         } else {             Entry<K,V> y = leftOf(parentOf(parentOf(x)));             if (colorOf(y) == RED) {                 setColor(parentOf(x), BLACK);                 setColor(y, BLACK);                 setColor(parentOf(parentOf(x)), RED);                 x = parentOf(parentOf(x));             } else {                 if (x == leftOf(parentOf(x))) {                     x = parentOf(x);                     rotateRight(x);                 }                 setColor(parentOf(x), BLACK);                 setColor(parentOf(parentOf(x)), RED);                 rotateLeft(parentOf(parentOf(x)));             }         }     }     root.color = BLACK; }

感谢各位的阅读！关于“如何实现TreeMap”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！