TreeMap,ThreeSet源碼
ThreeSet
ThreeSet的底層就是ThreeMap
public TreeSet() { this(new TreeMap<E,Object>()); }
ThreeMap
1.ThreeMap參數
//比較器 private final Comparator<? super K> comparator; //根節點 private transient Entry<K,V> root; //長度 private transient int size = 0; //對樹進行結構修改的次數 private transient int modCount = 0;
2.Entry參數
K key;//鍵 V value;//值 Entry<K,V> left;//左子節點 Entry<K,V> right;//右子節點 Entry<K,V> parent;//父節點 boolean color = BLACK; //節點顏色
3.構造
public TreeMap() { comparator = null; }
4.put方法
public V put(K key, V value) { //獲取根節點 Entry<K,V> t = root; //第一次進入，根節點為null if (t == null) { //驗證key是否為空 compare(key, key); // type (and possibly null) check //根據鍵值創建根節點 root = new Entry<>(key, value, null); //size加一 size = 1; //操作次數加加 modCount++; return null; } int cmp; //創建父節點 Entry<K,V> parent; //獲得比較器 ，比較器在無參初始化的時候就是null,地下也沒有給比較器賦值的地方 Comparator<? super K> cpr = comparator; //判斷比較器是否為空 if (cpr != null) { do { parent = t; 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 {//比較器為空進入 //key為空拋出異常 if (key == null) throw new NullPointerException(); //這個注解是取消代碼中的警告 @SuppressWarnings("unchecked") //獲取key Comparable<? super K> k = (Comparable<? super K>) key; //循環執行找到當前節點的父節點 do { //根節點給父節點 parent = t; //用當前的k和根節點的key進行比較 前面的小返回 負數 cmp = k.compareTo(t.key); //k小于根節點的key 將根節點的左子節點給根節點 if (cmp < 0) t = t.left; else if (cmp > 0) //k 大于根節點的key 將根節點的右子節點給根節點 t = t.right; else //相等的話證明是一致的key 直接修改根的值，并跳出循環 return t.setValue(value); //根不為空就向下進行循環，一直找到最后的節點為止 } while (t != null); } //根據key value 和父節點 創建一個節點 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; }
驗證key是否為空
final int compare(Object k1, Object k2) { return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2) : comparator.compare((K)k1, (K)k2); }
執行旋轉
//parentOf(x) 找到當前節點的父節點 //leftOf(x) 找到當前節點的左節點 //rightOf(x)找到當前節點的右節點 //colorOf(x)找到當前節點的顏色 //setColor(x,color) 設置當前節點的顏色 //傳入的是當前put的節點 private void fixAfterInsertion(Entry<K,V> x) { //將當前節點設置為紅色 x.color = RED; //判斷當前節點不是null 不是根節點 并且父節點的顏色是紅色 while (x != null && x != root && x.parent.color == RED) { //判斷當前節點的父節點是 當前節點的爺爺節點的左邊 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //得到當前節點的爺爺節點的右節點，也就是叔叔節點 Entry<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 {//當前節點的父節點不在左面 祖父節點不是紅色 //得到叔叔節點 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; }
parentOf(x) 找到當前節點的父節點
private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) { return (p == null ? null: p.parent); }
leftOf(x) 找到當前節點的左節點
private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) { return (p == null) ? null: p.left; }
rightOf(x)找到當前節點的右節點
private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) { return (p == null) ? null: p.right; }
colorOf(x)找到當前節點的顏色
private static <K,V> boolean colorOf(Entry<K,V> p) { return (p == null ? BLACK : p.color); }
setColor(x,color) 設置當前節點的顏色
private static <K,V> void setColor(Entry<K,V> p, boolean c) { if (p != null) p.color = c; }
rotateLeft 進行左旋
/** From CLR */ private void rotateLeft(Entry<K,V> p) { if (p != null) { Entry<K,V> r = p.right; p.right = r.left; if (r.left != null) r.left.parent = p; r.parent = p.parent; if (p.parent == null) root = r; else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; } }
rotateRight 進行右旋
/** From CLR */ private void rotateRight(Entry<K,V> p) { if (p != null) { Entry<K,V> l = p.left; p.left = l.right; if (l.right != null) l.right.parent = p; l.parent = p.parent; if (p.parent == null) root = l; else if (p.parent.right == p) p.parent.right = l; else p.parent.left = l; l.right = p; p.parent = l; } }
浙公網安備 33010602011771號