数据结构——红黑树

红黑树学习

代码地址

博客地址

动画演示

为什么使用红黑树

红黑树（RBT）：插入/删除很多时候不会破坏“红黑”特性 无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成

平衡二叉树：适用于以查为主、很少插入/删除场景

红黑树：适用于频繁插入、删除的场景，实用性更强

特点

左子树 < 当前节点 < 右子树

1）每个结点或是红色，或是黑色的

2）根结点是黑色的

3）叶结点（外部结点、NULL结点、失败结点）均是黑色的

4）不存在两个相邻的红结点（即红结点的父节点和孩子结点均为黑色）

5）对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

class RBTreeNode<T extends Comparable<T>> {
    private T value;//node value
    private RBTreeNode<T> left;//left child pointer
    private RBTreeNode<T> right;//right child pointer
    private RBTreeNode<T> parent;//parent pointer
    private boolean red;//color is red or not red
}

插入操作

• 先查找，确定插入位置（原理同二叉排序树），插入新结点

• 新结点是根——染为黑色

• 新结点非根——染为红色

  • 若插入新结点后依然满足红黑树定义，则插入结束

  • 若插入新结点后不满足红黑树定义，需要调整，使其重新 满足红黑树定义

    • 黑叔：旋转+染色
      • LL：右单旋，父换爷+染色；
      • RR：左单旋，父换爷+染色；
      • LR：左、右双旋，儿换爷+染色；
      • RL：右、左双旋，儿换爷+染色
    • 红叔：染色+变新
      • 叔父爷染色+爷变新结点

/**
     * add node
     * @param node
     * @return
     */
    public T addNode(RBTreeNode<T> node){
        //init node
        node.setLeft(null);
        setParent(node,null);
        node.setRight(null);
        node.setRed(true);

        //Determine whether the header node is empty
        if (root.getLeft() == null){
            //node become root
            root.setLeft(node);
            //root is black
            node.makeBlack();
        }else {
            //find insert point
            RBTreeNode<T> x = findParentNode(node);
            int cmp = x.getValue().compareTo(node.getValue());

            //value exists,ignore this node
            if(this.overrideMode && cmp==0){
                T v = x.getValue();
                x.setValue(node.getValue());
                return v;
            }else if(cmp==0){
                return x.getValue();
            }

            //x become node's parent
            setParent(node, x);

            if(cmp>0){
                x.setLeft(node);
            }else{
                x.setRight(node);
            }

            //Keep RBTree's identity.
            fixInsert(node);
        }
        size.incrementAndGet();
        return null;
    }

    /**
     * red black tree insert fix.
     * when Red is connected to red, we need fix RBTress。
     * if insert node's uncle is null(black),
     *          case 1: LL type, rotate right, change the color of parent and ancestor
     *          case 2: RR type, rotate left, change the color of parent and ancestor
     *          case 3: LR type, first rotate left and then rotate right, change the color of current and ancestor
     *          case 4: RL type, first rotate Right and then rotate left, change the color of current and ancestor
     * else insert node's uncle is red:
     *          change the color of parent、uncle with ancestor，and look on the ancestor as new insert node
     * @param node is new node
     */
    private void fixInsert(RBTreeNode<T> node) {
        RBTreeNode<T> parent = node.getParent();

        //whether need to fix
        while (parent != null && parent.isRed()) {
            //get uncle
            RBTreeNode<T> uncle = getUncle(node);

            if(uncle == null || uncle.isBlack()) {
                //uncle is black, have 4 cases
                RBTreeNode<T> ancestor = parent.getParent();
                if (ancestor.getLeft() == parent){
                    boolean isRight = node == parent.getRight();
                    if (isRight) {
                        rotateLeft(parent);
                    }
                    rotateRight(ancestor);

                    if (isRight) {
                        //change the color of current and ancestor
                        node.makeBlack();

                        //end loop
                        parent = null;
                    }else{
                        //end loop
                        parent.makeBlack();
                    }

                    ancestor.makeRed();
                }else{
                    boolean isLeft = node == parent.getLeft();
                    if (isLeft) {
                        rotateRight(parent);
                    }
                    rotateLeft(ancestor);

                    if (isLeft) {
                        node.makeBlack();

                        //end loop
                        parent = null;
                    }else {
                        //end loop
                        parent.makeBlack();
                    }

                    ancestor.makeRed();
                }
            }else{
                //change the color of parent、uncle with ancestor
                parent.makeBlack();
                uncle.makeBlack();
                RBTreeNode<T> ancestor = parent.getParent();
                ancestor.makeRed();

                //ancestor as new insert node
                node = parent.getParent();
                parent = node.getParent();
            }
        }

        //make sure root is black
        RBTreeNode<T> root = getRoot();
        root.makeBlack();
        setParent(root, null);
    }

    /**
     * rotate right
     * @param node
     */
    private void rotateRight(RBTreeNode<T> node) {
        //get left
        RBTreeNode<T> left = node.getLeft();
        if(left==null){
            throw new java.lang.IllegalStateException("left node is null");
        }
        //get parent
        RBTreeNode<T> parent = node.getParent();

        //leftRight move to node's left
        RBTreeNode<T> leftRight = left.getRight();
        node.setLeft(leftRight);
        setParent(leftRight, node);

        //node move to leftRight
        left.setRight(node);
        setParent(node, left);

        //change left's parent
        if(parent == null) {
            root.setLeft(left);
        }else {
            if (parent.getLeft() == node){
                parent.setLeft(left);
            }else {
                parent.setRight(left);
            }
        }
        setParent(left, parent);
    }

    /**
     * rotate left
     * @param node
     */
    private void rotateLeft(RBTreeNode<T> node) {
        //get right
        RBTreeNode<T> right = node.getRight();
        if(right==null){
            throw new java.lang.IllegalStateException("right node is null");
        }

        //get parent
        RBTreeNode<T> parent = node.getParent();

        //rightLeft move to node's right
        RBTreeNode<T> rightLeft = right.getLeft();
        node.setRight(rightLeft);
        setParent(rightLeft, node);

        //node move to rightLeft
        right.setLeft(node);
        setParent(node, right);

        //change left's parent
        if (parent == null){
            root.setLeft(right);
        }else{
            if (parent.getLeft() == node){
                parent.setLeft(right);
            }else{
                parent.setRight(right);
            }
        }
        setParent(right, parent);
    }


    /**
     * get uncle node
     * @param node
     * @return
     */
    private RBTreeNode<T> getUncle(RBTreeNode<T> node) {
        RBTreeNode<T> parent = node.getParent();
        RBTreeNode<T> ancestor = parent.getParent();

        if (ancestor == null){
            return null;
        }

        if (parent == ancestor.getLeft()){
            return ancestor.getRight();
        }else {
            return ancestor.getLeft();
        }
    }

    /**
     * find the parent node to hold node ,if parent value equals node.value return parent.
     * be used to find insert position
     * @param node
     * @return
     */
    private RBTreeNode<T> findParentNode(RBTreeNode<T> node) {
        //get root node
        RBTreeNode<T> parent = getRoot();
        RBTreeNode<T> cur = parent;
        while (cur != null){
            int cmp = cur.getValue().compareTo(node.getValue());
            if (cmp == 0){
                //the same value, return it
                return cur;
            }else if (cmp < 0){
                //Greater than, right
                parent = cur;
                cur = cur.getRight();
            }else {
                //Less than, left
                parent = cur;
                cur = cur.getLeft();
            }
        }

        return parent;
    }

删除操作

• ① 删除结点为红色——直接删除
• 删除节点为黑色
  • ② 删除节点的孩子有红色结点，红色结点代替删除结点，并染为黑色
  • 删除结点的孩子都是黑色
    • 删除结点不是根结点
      • 兄弟结点为黑色
        • 兄弟结点的孩子至少有一个是红色
          • ③ LL：右单旋，兄弟的左孩子结点 颜色设置为兄弟节点的颜色，兄弟结点的颜色设置为父结点的颜色
          • ④ RR：左单旋，兄弟的右孩子结点 颜色设置为兄弟节点的颜色，兄弟结点的颜色设置为父结点的颜色
          • ⑤ LR：左、右双旋，兄弟的右孩子结点的颜色设置为父结点的颜色，父结点的颜色设置为黑色
          • ⑥ RL：右、左双旋，兄弟的左孩子结点的颜色设置为父结点的颜色，父结点的颜色设置为黑色
        • ⑦ 兄弟结点的孩子都是黑色，将兄弟结点染为红色，再判断父结点是否红色，是红变黑
      • 兄弟结点为红色
        • ⑧ 删除的兄弟结点是父结点的左孩子 ,对结点父结点进行右旋操作，兄弟的左孩子结点的颜色设置为父结点的颜色，父结点的颜色设置为红色，变为 ⑦
        • ⑨ 删除的兄弟结点是父结点的右孩子 ,对结点父结点进行左旋操作：兄弟的右孩子结点的颜色设置为父结点的颜色，父结点的颜色设置为红色，变为 ⑦
    • ⑩ 删除结点是根结点，将双黑结点变为单黑结点，整颗红黑树的黑高减 1（将左孩子染红，右旋 或者 将右孩子染红，左旋）