Java TreeMap 和 TreeSet 源码解析

A Red-Black tree based {@link NavigableMap} implementation.The map is sorted according to the {@linkplain Comparable naturalordering} of its keys, or by a {@link Comparator} provided at mapcreation time, depending on which constructor is used.

TreeMap 是红黑二叉树。TreeSet 是红黑二叉树，不过他的元素是只有一个Key,而TreeMap key 用来排序，Value 是map 对应的值。

TreeMap 是基于红黑二叉树实现的，而HashMap 是基于数组加链表。

java.util.TreeMap#fixAfterInsertion

/** From CLR */private void fixAfterInsertion(TreeMapEntry<K,V> x) {x.color = RED;while (x != null && x != root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {TreeMapEntry<K,V> y = rightOf(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 == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}} else {TreeMapEntry<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;}

左旋、右旋、

java.util.TreeMap#fixAfterDeletion

/** From CLR */private void fixAfterDeletion(TreeMapEntry<K,V> x) {while (x != root && colorOf(x) == BLACK) {if (x == leftOf(parentOf(x))) {TreeMapEntry<K,V> sib = rightOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateLeft(parentOf(x));sib = rightOf(parentOf(x));}if (colorOf(leftOf(sib)) == BLACK &&colorOf(rightOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} else {if (colorOf(rightOf(sib)) == BLACK) {setColor(leftOf(sib), BLACK);setColor(sib, RED);rotateRight(sib);sib = rightOf(parentOf(x));}setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(rightOf(sib), BLACK);rotateLeft(parentOf(x));x = root;}} else { // symmetricTreeMapEntry<K,V> sib = leftOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateRight(parentOf(x));sib = leftOf(parentOf(x));}if (colorOf(rightOf(sib)) == BLACK &&colorOf(leftOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} else {if (colorOf(leftOf(sib)) == BLACK) {setColor(rightOf(sib), BLACK);setColor(sib, RED);rotateLeft(sib);sib = leftOf(parentOf(x));}setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(leftOf(sib), BLACK);rotateRight(parentOf(x));x = root;}}}setColor(x, BLACK);}

如果觉得《Java TreeMap 和 TreeSet 源码解析》对你有帮助，请点赞、收藏，并留下你的观点哦！