数据结构与算法(十,红黑树)

db.jpg

概念:

红黑树或者是一颗空树,或者是一颗具有以下性质的二叉查找树.

1. 结点非红即黑.
2. 根结点为黑.
3. 所有的NULL为叶子结点,且认为颜色为黑
4. 所有红结点的子结点为黑
5. 任一结点到其叶子结点的所有路径,经过的黑结点数量相同

6. 任意一个结点,他的左右子树层次不超过一倍.

   
   image.png

结点插入:

1. 先按照二叉排序树的方式插入一个节点(红色).

2. 插入的是黑结点>直接将结点涂黑.

3. 插入结点的父节点是黑色>不违背任何性质,不用调整.

4. 插入结点的父结点是红色>
   4.1 父结点是祖父结点的左孩子
   4.1.1 祖父节点的另一个子结点(叔叔结点)是红色>
   将当前节点的父结点和叔叔结点涂黑,祖父结点涂红,将当前节点指定为祖父结点,从新的当前节点开始算法.

   
   image.png
   

   4.1.2 叔叔结点是黑色>
   4.1.2.1 当前节点是其父结点的右孩子>当前节点的父结点作为新的当前节点,以新的当前节点为支点进行左旋

   
   image.png
   4.1.2.2 当前节点是其父结点的左孩子>父结点变为黑色,祖父结点变为红色,再以祖父结点为支点进行右旋
   image.png

   4.2 父结点是祖父结点右孩子>和上面一样,只是把左全部换成右.

image.png

删除结点

先进行二叉排序树的删除操作,然后将替换结点作为新的当前节点进行后面的平衡操作.

1. 当前节点是红色>直接把当前节点染黑,结束.

2. 当前节点是黑色>
   2.1 被删除节点是父结点的左孩子>
   2.1.1 当前节点是根结点>什么都不做
   2.1.2 当前节点X的兄弟结点是红色(此时,父结点和兄弟节点的子结点为黑)>把父结点染红,兄弟节点染黑,以父结点为支点进行左旋,重新设置X的兄弟节点.

   
   image.png
   

   2.1.3 当前节点X的兄弟节点是黑色>
   2.1.3.1 兄弟节点的两个孩子都为黑色>将当前节点的兄弟节点染黑,父结点染红,然后以父结点作为新的当前节点,从新开始算法.

   
   image.png
   2.1.3.2 兄弟的右孩子是黑色,左孩子是红色>将X兄弟节点的左孩子置黑,将X节点的兄弟节点置红,将X节点的兄弟节点进行右旋,然后重置x节点的兄弟节点.
   image.png
   2.1.3.3 兄弟节点的右孩子是红色>兄弟节点染成当前节点父结点的颜色,兄弟节点的右孩子染成黑色,父结点染成黑色,以当前节点的父结点为支点,进行左旋,算法结束.
   image.png

   2.2 被删除节点是父结点的右孩子>把上边的左置为右

代码

红黑树的插入删除规则就讲完了,是有点复杂,但其实不难.
那么,我们来看看红黑树的代码吧,jdk1.8之后,为了适用大数据时代,很多数据结构都用到了红黑树
比如:HashTable,TreeSet,TreeMap
我们以TreeMap为例,来看看红黑树的源码,对照上面的插入规则和删除规则来一步步看

1. TreeMap插入操作

public V put(K key, V value) {
        TreeMapEntry<K,V> t = root;
        if (t == null) {//根结点为空
            // BEGIN Android-changed: Work around buggy comparators. http://b/34084348
            // We could just call compare(key, key) for its side effect of checking the type and
            // nullness of the input key. However, several applications seem to have written comparators
            // that only expect to be called on elements that aren't equal to each other (after
            // making assumptions about the domain of the map). Clearly, such comparators are bogus
            // because get() would never work, but TreeSets are frequently used for sorting a set
            // of distinct elements.
            //
            // As a temporary work around, we perform the null & instanceof checks by hand so that
            // we can guarantee that elements are never compared against themselves.
            //
            // **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
            //
            // Upstream code was:
            // compare(key, key); // type (and possibly null) check
            if (comparator != null) {//这个comparator表示传进来的比较器
                if (key == null) {
                    comparator.compare(key, key);
                }
            } else {
                if (key == null) {
                    throw new NullPointerException("key == null");
                } else if (!(key instanceof Comparable)) {
                    throw new ClassCastException(
                            "Cannot cast" + key.getClass().getName() + " to Comparable.");
                }
            }
            // END Android-changed: Work around buggy comparators. http://b/34084348
            root = new TreeMapEntry<>(key, value, null);//插入结点作为根结点
            size = 1;
            modCount++;//表示TreeMap被修改一次
            return null;
        }
        int cmp;
        TreeMapEntry<K,V> parent;
        // split comparator and comparable paths
        //这里是确认插入结点的位置,分为comparator为空和不为空两种情况
        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 {
            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;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        //插入节点,平衡操作
        TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }


    /** From CLR */
    private void fixAfterInsertion(TreeMapEntry<K,V> x) {
        x.color = RED;

        while (x != null && x != root && x.parent.color == RED) {//4
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//4.1
                TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));//x的叔叔结点y
                if (colorOf(y) == RED) {//4.1.1
                    setColor(parentOf(x), BLACK);//父结点置黑
                    setColor(y, BLACK);//叔叔结点置黑
                    setColor(parentOf(parentOf(x)), RED);//祖父结点置红
                    x = parentOf(parentOf(x));//祖父结点作为当前节点
                } else {//4.1.2
                    if (x == rightOf(parentOf(x))) {//4.1.2.1
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    //4.1.2.2
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {//4.2
                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;//2
    }

2. TreeMap删除操作

/**
     * Delete node p, and then rebalance the tree.
     */
    private void deleteEntry(TreeMapEntry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            TreeMapEntry<K,V> s = successor(p);//找到替换结点,并替换
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)//2
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)//2
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

    /** From CLR */
    private void fixAfterDeletion(TreeMapEntry<K,V> x) {
        while (x != root && colorOf(x) == BLACK) {//2
            if (x == leftOf(parentOf(x))) {//2.1
                TreeMapEntry<K,V> sib = rightOf(parentOf(x));//sib,当前节点的兄弟结点

                if (colorOf(sib) == RED) {//2.1.2
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }

                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {//2.1.3.1
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(rightOf(sib)) == BLACK) {//2.1.3.2
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    //2.1.3.3
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } else { // symmetric
                //2.2
                TreeMapEntry<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);//1
    }

      /**
     * Returns the successor of the specified Entry, or null if no such.
     */
    static <K,V> TreeMapEntry<K,V> successor(TreeMapEntry<K,V> t) {
        if (t == null)
            return null;
        else if (t.right != null) {//右子树不为空时,得到删除结点右子树的左子树中最小的结点,替换被删除的结点
            TreeMapEntry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {//右子树为空,从当前节点一直右上找,找到头
            TreeMapEntry<K,V> p = t.parent;
            TreeMapEntry<K,V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

ok,红黑树就介绍到这里了,如果对这些树感兴趣呢,其实在计算科学中还有很多有趣的树
比如:

image.png

大家感兴趣可以自行去学习下.

日拱一卒,贵在坚持.