算法学习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);
                    }
                }
            }
        }
    }
}
           

其他的方法操作都差不多就不讲了，红黑树是将每个结点标记为红色或者黑色，相邻结点颜色不能相同