数据结构08-红黑树

作者: 最爱的火 | 来源:发表于2018-05-11 08:53 被阅读42次

    数据结构08-红黑树

    一、红黑树的介绍

    红黑树(RBT)是每个节点都带有颜色属性的自平衡二叉查找树,颜色或红色或黑色。具备以下性质:

    性质1:节点是红色或黑色;
    性质2:根节点是黑色。
    性质3:所有的NULL节点都为叶子节点,且颜色为空。
    性质4:每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    性质5:从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
    

    由于AVL的树增删效率很低,所以出现了红黑树。红黑树的查找效率比一般的二叉查找树高,比AVL树低,但是增删效率比AVL树高,比一般的二叉查找树低。

    红黑树的应用:TreeMap、TreeSet

    二、红黑树的插入

    红黑树的插入分为两步:添加、修正平衡。

    这里把新增节点记作A,把A的父节点记作B,把找到的最小不平衡子树记作C。

    1.添加

    第一步的添加跟二叉搜索树的插入一样。

    2.修正平衡

    将当前节点记作A,将A的父节点记作B,将B的兄弟节点记作C,将B的父结点记作D。

    修正过程如下:

    1. 将A设为红色,这样对整颗树的平衡影响较小;
    2. 如果A为根节点,则将根节点改成黑色即可,修正结束;
    3. 如果B是黑色,那么树就是平衡的,修正结束;
    4. 如果B是红色,并且B是D的左孩子,则判断C的颜色:
      • 如果C是红色,则将B和C涂黑,D涂红,把当前节点(A)指向D,然后继续比较A;
      • 如果C是黑色,并且A是B的左孩子,则把B涂黑,D涂红,然后对D右旋,然后继续比较A;
      • 如果C是黑色,并且A是B的右孩子,则把当前节点(A)指向B,然后对新的A左旋。然后把B指向新A的父亲,把D指向新B的父亲,然后把B涂黑,D涂红,对D右旋,然后继续比较A。
    5. 如果B是红色,并且B是D的右孩子,则判断C的颜色:
      • 如果C是红色,则将B和C涂黑,D涂红,把当前节点(A)指向D,然后继续比较A;
      • 如果C是黑色,并且A是B的右孩子,则把B涂黑,D涂红,然后对D左旋,然后继续比较A;
      • 如果C是黑色,并且A是B的左孩子,则把当前节点(A)指向B,然后对新的A右旋。然后把B指向新A的父亲,把D指向新B的父亲,然后把B涂黑,D涂红,对D左旋,然后继续比较A。

    添加元素:

    public void put(E data) {
        Node<E> now = new Node<E>(data);
        if (root == null) {
            root = now;
            return;
        }
    
        Node<E> parent = root;
        // 像二叉查找树一样添加
        while (parent != null) {
            if (data.compareTo(parent.data) < 0) {
                if (parent.left == null) {
                    parent.left = now;
                    now.parent = parent;
                    break;
                } else {
                    parent = parent.left;
                }
            } else if (data.compareTo(parent.data) > 0) {
                if (parent.right == null) {
                    parent.right = now;
                    now.parent = parent;
                    break;
                } else {
                    parent = parent.right;
                }
            } else {
                return;
            }
        }
        //修正位置
        fixAfterInsertion(now);
    }
    

    修正位置:

    private void fixAfterInsertion(Node<E> node) {
        node.color = RED;
    
        Node<E> parent = null;
        Node<E> brother = null;
        while (node != null && node != root && node.parent.color == RED) {
            parent = node.parent;
            if (parent.parent != null && parent.parent.left == parent) {
                brother = parent.parent.right;
                if (getColor(brother) == RED) {
                    setColor(parent, BLACK);
                    setColor(brother, BLACK);
                    setColor(parent.parent, RED);
                    node = parent.parent;
                } else {
                    if (parent.right == node) {
                        node = parent;
                        leftRoate(node);
                    }
                    parent = node.parent;
                    setColor(parent, BLACK);
                    setColor(parent.parent, RED);
                    rightRoate(parent.parent);
                }
            } else {
                brother = parent.parent == null ? null : parent.parent.left;
                if (getColor(brother) == RED) {
                    setColor(parent, BLACK);
                    setColor(brother, BLACK);
                    setColor(parent.parent, RED);
                    node = parent.parent;
                } else {
                    if (parent.left == node) {
                        node = parent;
                        rightRoate(node);
                    }
                    parent = node.parent;
                    setColor(parent, BLACK);
                    setColor(parent.parent, RED);
                    leftRoate(parent.parent);
                }
            }
        }
    
        root.color = BLACK;
    }
    

    三、红黑树的删除

    红黑树的插入分为两步:删除、修正平衡。

    这里把需要修正的节点记作A,把A的父节点记作B,把找到的最小不平衡子树记作C。

    1.删除

    第一步的删除跟二叉搜索树的插入一样,只是要将被删除节点的替代节点当作需要修正的结点。

    注意:如果被删结点是红色,那么不影响树的平衡,不需要修正;

    2.修正平衡

    将当前节点记作A,将A的父节点记作B,将A的兄弟节点记作C,将B的父结点记作D。

    修正过程如下:

    1. 如果A为根节点,则将A设为黑色,修正结束;

    2. 如果A为红色,则将A设为黑色,修正结束;

    3. 如果A为B的左子节点,则

      • 先判断C的颜色,如果C为红色,则将C设为黑色,将B设为红色,然后对B左旋,然后将B指向新A的父亲,将C指向新B的兄弟
      • 然后判断C的左右子节点是否都为黑色,如果都为黑色,则将C设为红色,将A指向B,然后继续判断A;
      • 如果C的右子节点是黑色,C的左子节点是红色或黑色,则先将C的左子节点设为黑色,将C设为红色,对B右旋,将B指向新A的父亲,将C指向新B的兄弟;然后将C设为B的颜色,将B设为黑色,将B的右子节点设为黑色,再将B左旋,将A指向root节点。
      • 如果C的右子节点是红色,C的左子节点是红色或黑色,则将C设为B的颜色,将B设为黑色,将B的右子节点设为黑色,再将B左旋,将A指向root节点。
    4. 如果A为B的右子节点,则

      • 先判断C的颜色,如果C为红色,则将C设为黑色,将B设为红色,然后对B右旋,然后将B指向新A的父亲,将C指向新B的兄弟
      • 然后判断C的左右子节点是否都为黑色,如果都为黑色,则将C设为红色,将A指向B,然后继续判断A;
      • 如果C的左子节点是黑色,C的右子节点是红色,则先将C的右子节点设为黑色,将C设为红色,对B左旋,将B指向新A的父亲,将C指向新B的兄弟;然后将C设为B的颜色,将B设为黑色,将B的左子节点设为黑色,再将B右旋,将A指向root节点。
      • 如果C的左子节点是红色,C的右子节点是红色或黑色,则将C设为B的颜色,将B设为黑色,将B的左子节点设为黑色,再将B右旋,将A指向root节点。

    删除:

    public Node<E> remove(E data) {
        Node<E> now = get(data);
        if (now == null) {
            throw new NoSuchElementException();
        }
    
        Node<E> p = get(data);
        if (p == null) {
            throw new NoSuchElementException();
        }
        //p的右子树的最左子节点r
        Node<E> r = nodeLeft(p.right);
        //p的左子树的最右子节点l
        Node<E> l = nodeRight(p.left);
        if (r != null) {
            p.data = r.data;
            //如果p的右子结点有左节点
            if (r != p.right) {
                r.parent.left = r.right;
            } else {
                p.right = p.right.right;
            }
            //如果被删节点是黑色,就对替换的节点进行修正,即从平衡破坏的地方开始向上修正
            if (now.color == BLACK) {
                fixAfterDelete(r.right);
            }
            r.left = r.right = r.parent = null;
    
        } else if (l != null) {
            p.data = l.data;
            //如果p的左子结点有右节点
            if (l != p.left) {
                l.parent.right = l.left;
            } else {
                p.left = p.left.left;
            }
            //如果被删节点是黑色,就对替换的节点进行修正,即从平衡破坏的地方开始向上修正
            if (now.color == BLACK) {
                fixAfterDelete(l.left);
            }
            l.left = l.right = l.parent = null;
    
            //如果p是叶子节点
        } else {
            //如果p是叶子节点,但不是根节点,且颜色为黑色就需要对其修正
            if (p.parent != null && p.color == BLACK) {
                fixAfterDelete(p);
            }
    
            if (p.parent == null) {
                root = null;
            } else if (p.parent.left == p) {
                p.parent.left = null;
            } else {
                p.parent.right = null;
            }
            p.parent = null;
        }
        return now;
    }
    

    修正位置:

    private void fixAfterDelete(Node<E> node) {
        if (node == null) {
            return;
        }
    
        Node<E> parent = null;
        Node<E> brother = null;
        while (node != root && getColor(node) == BLACK) {
            parent = node.parent;
            if (node == parent.left) {
                brother = parent.right;
    
                if (getColor(brother) == RED) {
                    setColor(brother, BLACK);
                    setColor(parent, RED);
                    leftRoate(parent);
                    parent = node.parent;
                    brother = parent.right;
                }
    
                if (getColor(brother.left) == BLACK && getColor(brother.right) == BLACK) {
                    setColor(brother, RED);
                    node = node.parent;
                } else {
                    if (getColor(brother.right) == BLACK) {
                        setColor(brother.left, BLACK);
                        setColor(brother, RED);
                        rightRoate(brother);
                        parent = node.parent;
                        brother = parent.right;
                    }
                    setColor(brother, getColor(parent));
                    setColor(parent, BLACK);
                    setColor(brother.right, BLACK);
                    leftRoate(parent);
                    node = root;
                }
            } else { // symmetric
                brother = parent.left;
    
                if (getColor(brother) == RED) {
                    setColor(brother, BLACK);
                    setColor(parent, RED);
                    rightRoate(parent);
                    parent = node.parent;
                    brother = parent.left;
                }
    
                if (getColor(brother.left) == BLACK && getColor(brother.right) == BLACK) {
                    setColor(brother, RED);
                    node = node.parent;
                } else {
                    if (getColor(brother.left) == BLACK) {
                        setColor(brother.right, BLACK);
                        setColor(brother, RED);
                        leftRoate(brother);
                        parent = node.parent;
                        brother = parent.left;
                    }
                    setColor(brother, getColor(parent));
                    setColor(parent, BLACK);
                    setColor(brother.left, BLACK);
                    rightRoate(parent);
                    node = root;
                }
            }
        }
    
        setColor(node, BLACK);
    }
    

    最后

    代码地址:https://gitee.com/yanhuo2008/Common/blob/master/Tool/src/main/java/gsw/tool/datastructure/tree/TreeRedBlack.java

    数据结构与算法专题:https://www.jianshu.com/nb/25128590

    喜欢请点赞,谢谢!

    相关文章

      网友评论

        本文标题:数据结构08-红黑树

        本文链接:https://www.haomeiwen.com/subject/cobxdftx.html