您好,登錄后才能下訂單哦!
這篇文章給大家分享的是有關(guān)如何實(shí)現(xiàn)TreeMap的內(nèi)容。小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,一起跟隨小編過來看看吧。
/**
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;
//根節(jié)點(diǎn)
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;//紅黑樹的根節(jié)點(diǎn)
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);//構(gòu)造根節(jié)點(diǎn),root沒有父節(jié)點(diǎn),傳入null size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; //定義節(jié)點(diǎn) // split comparator and comparable paths Comparator<? super K> cpr = comparator; //獲得比較器 if (cpr != null) {//定義了比較器,采用自定義比較器進(jìn)行比較 do { parent = t;//將紅黑樹根節(jié)點(diǎn)賦值給parent cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left;//指向左子節(jié)點(diǎn) else if (cmp > 0) t = t.right;//指向右子節(jié)點(diǎn) 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;//左子節(jié)點(diǎn) else if (cmp > 0) t = t.right;//右子節(jié)點(diǎn) else return t.setValue(value); } while (t != null); } //創(chuàng)建新節(jié)點(diǎn),并指定父點(diǎn) Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; //新插入節(jié)點(diǎn)后重新調(diào)整紅黑樹 fixAfterInsertion(e); size++; modCount++; return null; } /** From CLR */ private void fixAfterInsertion(Entry<K,V> x) { //加入的節(jié)點(diǎn)默認(rèn)的顏色是紅色 x.color = RED; //情形1:新節(jié)點(diǎn)x是樹的根節(jié)點(diǎn),沒有父節(jié)點(diǎn)不需要任何操作 //情形2:新節(jié)點(diǎn)x的父節(jié)點(diǎn)顏色是黑色的,不需要操作 while (x != null && x != root && x.parent.color == RED) { //情形3:新節(jié)點(diǎn)的父節(jié)點(diǎn)顏色是紅色的 //判斷x的節(jié)點(diǎn)的父節(jié)點(diǎn)位置,是否屬于左子節(jié)點(diǎn) if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //獲取x節(jié)點(diǎn)的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn),上面語句已經(jīng)判斷出x節(jié)點(diǎn)的父節(jié)點(diǎn)為左子節(jié)點(diǎn),所以直接取右子節(jié)點(diǎn) Entry<K,V> y = rightOf(parentOf(parentOf(x))); //判斷是否x節(jié)點(diǎn)的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色 if (colorOf(y) == RED) { setColor(parentOf(x), BLACK);//x節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為黑色 setColor(y, BLACK);//y節(jié)點(diǎn)的顏色設(shè)置為黑色 setColor(parentOf(parentOf(x)), RED);//x的父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為紅色 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; }
感謝各位的閱讀!關(guān)于“如何實(shí)現(xiàn)TreeMap”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,讓大家可以學(xué)到更多知識(shí),如果覺得文章不錯(cuò),可以把它分享出去讓更多的人看到吧!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。