算法學習4

二叉搜尋樹：

非空左子樹的所有鍵值小于其根結點的鍵值

非空右子樹的所有鍵值大于其根結點的鍵值

左，右子樹都是二叉搜尋樹

平衡二叉樹:任意結點的左右子樹高度差的絕對值不超過1

平衡因子：左子樹的高度-右子樹的高度

學到了二叉樹，是以把HashMap的紅黑樹源碼拿出來分析了下：

從put方法開始：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
           

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            /**
             * 這裡執行的就是樹的插入操作
             */
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        /**
                         * 這裡進行的是連結清單轉紅黑樹的操作
                         */
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
           

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
     /**
     * h為要插入的資料的hash值，k為key，v為value
     */
    Class<?> kc = null;
    boolean searched = false;
    /**
     * 這裡拿到根結點
     */
    TreeNode<K,V> root = (parent != null) ? root() : this;
     /**
     * 開始循環尋找插入位置
     */
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            /**
     	     * 如果根結點的hash值大于目前結點的hash，說明目前結點應該插入根結點的左邊
             */
            dir = -1;
        else if (ph < h)
            /**
     	     * 如果根結點的hash值小于目前結點的hash，說明目前結點應該插入根結點的右邊
             */
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            /**
     	     * 這裡插入的key為根結點的key，直接傳回根結點
             */
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            //走到這裡說明hash沖突，
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    //find方法是去找一個key為目前k的結點，如果找到了 直接傳回找到的結點
                    return q;
            }
            //走到這裡說明沒找到key相同的結點，用identityHashCode這個方法進行hash計算，得到辨別dir
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            //如果判斷通過說明找到了該插入的位置，插入，沒進這個判斷繼續往下找
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            //balanceInsertion這個方法和balanceDeletion這個方法分别是插入後重新平衡二叉樹和删除後重新平衡二叉樹
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}
           

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    //X結點預設為紅色
    x.red = true;
    /**
     * xp為 x.parent
     * xpp為 x.parent.parent
     * xppl為 x.parent.parent.left
     * xppr為 x.parent.parent.right
     */
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        if ((xp = x.parent) == null) {
            //這個判斷說明X為根結點，直接置為黑色并傳回
            x.red = false;
            return x;
        }
        else if (!xp.red || (xpp = xp.parent) == null)
            //說明X是根結點的兒子的兒子，（同時x的父結點為黑色，直接傳回）
            return root;
        if (xp == (xppl = xpp.left)) {
            //xp是xpp的左兒子，x在xpp的左子樹下
            if ((xppr = xpp.right) != null && xppr.red) {
                //xpp的右兒子是紅色的，說明xpp是黑色，xppl為紅色，
                //把xpp的右兒子變成黑色
                xppr.red = false;
                //把xp變成黑色
                xp.red = false;
                //把xpp變成紅色
                xpp.red = true;
                //XPP這個分支變色完畢，将xpp指派為x，繼續向上變色
                x = xpp;
            }
            else {
                //x在xpp的右子樹下
                if (x == xp.right) {
                    //x是xp的右兒子，左旋平衡
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        else {
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}
           

其他的方法操作都差不多就不講了，紅黑樹是将每個結點标記為紅色或者黑色，相鄰結點顔色不能相同