黄小华的个人网站
熬过无人问津的日子才有诗和远方!
手撕红黑树

1.红黑树

红黑树其实就是一种数据结构,设计它的目的就是为了高效地进行增删改查,
性能极其之高,仅通过几十次查询就能从百亿级的数据中查找到数据
而链表从百亿数据中找数据它就要查百亿次,百亿次的查找数据库是不能忍受的
它应用的地方很多,比如说java中的HashMap和TreeMap。还有就是linux也经常使用到。由于节点之间地址不连续,所以红黑树只适于存在内存的数据,不适合磁盘
所以该数据结构在面试的时候是一个常问问题
红黑树性质约束:
1.结点是红色或黑色
2.根结点是黑色
3.从根节点到叶子节点,不会出现两个连续的红色节点
4.对于任意一结点,其到叶子结点的每条路径上的黑色结点数相同
5.每个叶子结点是黑色null结点

红黑树底层是自平衡的二叉查找树(左节点小于根节点,右节点大于根结点),
我们在对红黑树进行插入和删除等操作时,对树做了修改,那么可能会违背红黑树的性质。
为了继续保持红黑树的性质约束,可以通过对结点进行重新着色(新插入的结点默认红色 )
以及对树进行相关的旋转操作来达到对红黑树进行插入或删除结点等操作后,继续保持它的性质和相对的平衡。
树的旋转,分为左旋
QQ图片20200329163151.gif
和右旋
QQ图片20200329163141.gif

手撕红黑树相关问题

1.为什么要用红黑树?
使用红黑树能使节点的查找,插入,删除等操作时间复杂度最大为O(logn),极大地提高性能。
如果不使用红黑树,插入一个有序列表,会形成一个链表,完全丧失二叉查找树的优势,以致O(n)的时间复杂度。
2.插入操作实现原理
分为三种情况
(1)要插入的结点没有父结点
这种情况比较简单,直接这个结点为黑色根结点
(2)要插入结点的父节点是黑色
这种情况插入后对照红黑树性质 发现完全符合 所以直接将结点插入到黑色父结点后即可
(3)要插入结点的父结点是红色
很明显出现两个连续红色结点,这种情况相对复杂,此时调整又要分情况说,我们分别举例说明
1.叔叔结点是红色
例如下面要插入结点21
QQ截图20200329155808.png
发现叔叔结点27是红色
第一步 把21结点的父结点22变成黑色
QQ截图20200329160636.png
变色后发现该条路径上黑色节点多余其他路径,继续调整
第二步 把22结点的父结点变为红色
QQ截图20200329161031.png
发现节点25和节点27是两个连续的红色结点,继续调整 但是这是不能往上走,会出现死胡同,因此往下编27的颜色
第三步 把结点27变为黑色
QQ截图20200329161435.png
这时结点17和结点25是两个连续的红色,继续调整
第四步 把结点17和结点8同时变为黑色
QQ截图20200329161704.png
此时再对照一下那5条规则,发现完全符合。
2.叔叔结点是黑色
这时又要分情况 (1)新插入节点为父节点的左孩子
QQ截图20200329162937.png
(2)新插入节点为父节点的右孩子
QQ截图20200329163002.png
按照第一遍的思路,我们对这两种情况执行同样的操作,最终也能保证红黑树的5条特征。
3.删除结点操作实现原理
删除结点分为3种情况
(1) 要删除的结点是叶子结点
这种情况如果是根结点或结点是红色,直接删除即可
如果叶子节点是黑色的,那么就需要进行调整,调整的步骤和插入时调整的步骤一样。
(2) 要删除的结点有一个子结点
先直接让它的子节点接上它的父结点 如果该子结点是红色,就可以不做调整
如果是黑色 调整的步骤和插入时调整的步骤一样。
(3) 要删除的结点有两个子结点
QQ截图20200329165150.png
若节点13之前是叶子节点,那就和第一种情况一样了,如果节点13是红色的,可以直接删除,
如果节点13是黑色的,那么就需要进行调整,此时的节点13就是叶子节点。调整的步骤和插入时调整的步骤一样。
若节点13之前还有子节点,那就和第二种情况一样了。那就继续替换和判断。
以上呢就是删除的情况,最后一种情况是修改,这种情况是查找和插入的结合体,也就是先找到要修改的元素,
修改完值之后,继续进行调整即可

实现的完整Java代码

结点

package RBTree;

import java.util.Objects;

public class RBTreeNode {
    private final boolean RED = false;
    private final boolean BLACK = true;
    private int key;
    private boolean color;
    private RBTreeNode left;
    private RBTreeNode right;
    private RBTreeNode parent;

    public RBTreeNode(int key) {
        this.key = key;
        this.color = RED;
    }

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public boolean getColor() {
        return color;
    }

    public void setColor(boolean color) {
        this.color = color;
    }

    public RBTreeNode getLeft() {
        return left;
    }

    public void setLeft(RBTreeNode left) {
        this.left = left;
    }

    public RBTreeNode getRight() {
        return right;
    }

    public void setRight(RBTreeNode right) {
        this.right = right;
    }

    public RBTreeNode getParent() {
        return parent;
    }

    public void setParent(RBTreeNode parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "RBTreeNode{" +
                ",key=" + key +
                ", color=" + color +
                '}';
    }
}

package RBTree;

public class RBTree {
    RBTreeNode root;
    private final boolean RED = false;
    private final boolean BLACK = true;

    public RBTreeNode query(int key) {
        RBTreeNode tmp = root;
        while (tmp != null) {
            if (tmp.getKey() == key)
                return tmp;
            else if (tmp.getKey() > key)
                tmp = tmp.getLeft();
            else
                tmp = tmp.getRight();
        }
        return null;
    }

    public void insert(int key) {
        RBTreeNode node = new RBTreeNode(key);
        if (root == null) {
            root = node;
            node.setColor(BLACK);
            return;
        }
        RBTreeNode parent = root;
        RBTreeNode son = null;
        if (key <= parent.getKey()) {
            son = parent.getLeft();
        } else {
            son = parent.getRight();
        }
        //find the position
        while (son != null) {
            parent = son;
            if (key <= parent.getKey()) {
                son = parent.getLeft();
            } else {
                son = parent.getRight();
            }
        }
        if (key <= parent.getKey()) {
            parent.setLeft(node);
        } else {
            parent.setRight(node);
        }
        node.setParent(parent);

        //fix up
        insertFix(node);
    }

    private void insertFix(RBTreeNode node) {
        RBTreeNode father, grandFather;
        while ((father = node.getParent()) != null && father.getColor() == RED) {
            grandFather = father.getParent();
            if (grandFather.getLeft() == father) {  //F为G左儿子的情况,如之前的分析
                RBTreeNode uncle = grandFather.getRight();
                if (uncle != null && uncle.getColor() == RED) {
                    setBlack(father);
                    setBlack(uncle);
                    setRed(grandFather);
                    node = grandFather;
                    continue;
                }
                if (node == father.getRight()) {
                    leftRotate(father);
                    RBTreeNode tmp = node;
                    node = father;
                    father = tmp;
                }
                setBlack(father);
                setRed(grandFather);
                rightRotate(grandFather);
            } else {                               //F为G的右儿子的情况,对称操作
                RBTreeNode uncle = grandFather.getLeft();
                if (uncle != null && uncle.getColor() == RED) {
                    setBlack(father);
                    setBlack(uncle);
                    setRed(grandFather);
                    node = grandFather;
                    continue;
                }
                if (node == father.getLeft()) {
                    rightRotate(father);
                    RBTreeNode tmp = node;
                    node = father;
                    father = tmp;
                }
                setBlack(father);
                setRed(grandFather);
                leftRotate(grandFather);
            }
        }
        setBlack(root);
    }

    public void delete(int key) {
        delete(query(key));
    }

    private void delete(RBTreeNode node) {
        if (node == null)
            return;
        if (node.getLeft() != null && node.getRight() != null) {
            RBTreeNode replaceNode = node;
            RBTreeNode tmp = node.getRight();
            while (tmp != null) {
                replaceNode = tmp;
                tmp = tmp.getLeft();
            }
            int t = replaceNode.getKey();
            replaceNode.setKey(node.getKey());
            node.setKey(t);
            delete(replaceNode);
            return;
        }
        RBTreeNode replaceNode = null;
        if (node.getLeft() != null)
            replaceNode = node.getLeft();
        else
            replaceNode = node.getRight();

        RBTreeNode parent = node.getParent();
        if (parent == null) {
            root = replaceNode;
            if (replaceNode != null)
                replaceNode.setParent(null);
        } else {
            if (replaceNode != null)
                replaceNode.setParent(parent);
            if (parent.getLeft() == node)
                parent.setLeft(replaceNode);
            else {
                parent.setRight(replaceNode);
            }
        }
        if (node.getColor() == BLACK)
            removeFix(parent, replaceNode);

    }

    //多余的颜色在node里
    private void removeFix(RBTreeNode father, RBTreeNode node) {
        while ((node == null || node.getColor() == BLACK) && node != root) {
            if (father.getLeft() == node) {  //S为P的左儿子的情况,如之前的分析
                RBTreeNode brother = father.getRight();
                if (brother != null && brother.getColor() == RED) {
                    setRed(father);
                    setBlack(brother);
                    leftRotate(father);
                    brother = father.getRight();
                }
                if (brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))) {
                    setRed(brother);
                    node = father;
                    father = node.getParent();
                    continue;
                }
                if (isRed(brother.getLeft())) {
                    setBlack(brother.getLeft());
                    setRed(brother);
                    rightRotate(brother);
                    brother = brother.getParent();
                }

                brother.setColor(father.getColor());
                setBlack(father);
                setBlack(brother.getRight());
                leftRotate(father);
                node = root;//跳出循环
            } else {                         //S为P的右儿子的情况,对称操作
                RBTreeNode brother = father.getLeft();
                if (brother != null && brother.getColor() == RED) {
                    setRed(father);
                    setBlack(brother);
                    rightRotate(father);
                    brother = father.getLeft();
                }
                if (brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))) {
                    setRed(brother);
                    node = father;
                    father = node.getParent();
                    continue;
                }
                if (isRed(brother.getRight())) {
                    setBlack(brother.getRight());
                    setRed(brother);
                    leftRotate(brother);
                    brother = brother.getParent();
                }

                brother.setColor(father.getColor());
                setBlack(father);
                setBlack(brother.getLeft());
                rightRotate(father);
                node = root;//跳出循环
            }
        }

        if (node != null)
            node.setColor(BLACK);
    }

    private boolean isBlack(RBTreeNode node) {
        if (node == null)
            return true;
        return node.getColor() == BLACK;
    }

    private boolean isRed(RBTreeNode node) {
        if (node == null)
            return false;
        return node.getColor() == RED;
    }

    private void leftRotate(RBTreeNode node) {
        RBTreeNode right = node.getRight();
        RBTreeNode parent = node.getParent();
        if (parent == null) {
            root = right;
            right.setParent(null);
        } else {
            if (parent.getLeft() != null && parent.getLeft() == node) {
                parent.setLeft(right);
            } else {
                parent.setRight(right);
            }
            right.setParent(parent);
        }
        node.setParent(right);
        node.setRight(right.getLeft());
        if (right.getLeft() != null) {
            right.getLeft().setParent(node);
        }
        right.setLeft(node);
    }

    private void rightRotate(RBTreeNode node) {
        RBTreeNode left = node.getLeft();
        RBTreeNode parent = node.getParent();
        if (parent == null) {
            root = left;
            left.setParent(null);
        } else {
            if (parent.getLeft() != null && parent.getLeft() == node) {
                parent.setLeft(left);
            } else {
                parent.setRight(left);
            }
            left.setParent(parent);
        }
        node.setParent(left);
        node.setLeft(left.getRight());
        if (left.getRight() != null) {
            left.getRight().setParent(node);
        }
        left.setRight(node);
    }

    private void setBlack(RBTreeNode node) {
        node.setColor(BLACK);
    }

    private void setRed(RBTreeNode node) {
        node.setColor(RED);
    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(RBTreeNode node) {
        if (node == null)
            return;
        inOrder(node.getLeft());
        System.out.println(node);
        inOrder(node.getRight());
    }
}