玩转红黑树 (第五部分)红黑树的概念与插入

玩转红黑树 (第五部分)红黑树的概念与插入

什么是红黑树?

红黑树本质上是一种二叉查找树,但它在二叉查找树的基础上额外添加了一个标记(颜色),同时具有一定的规则。这些规则使红黑树保证了一种平衡,插入、删除、查找的最坏时间复杂度都为 O(logn)。

五大特征

1 每个节点要么是红色,要么是黑色

2 根节点永远是黑色的

3 所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点)

4 每个红色节点的两个子节点一定都是黑色

5 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点

体验下插入过程~~

插入规则。

1 和普通二叉树一致,小的放左边,大的放右边

2 新插入的节点默认为红色

3 不能连续出现2个红色节点

一步一步开始插入节点

基本插入,不考虑红黑树特性,按照二叉树特性插入节点

遍历时根据值的大小对比,判断放入左子树还是右子树,直到null节点,则进行插入

检查节点颜色,是否需要变色和旋转

情况一:parent和uncle都为红色

从图中可以看到,只需要将parent和uncle节点都变成黑色,pParent变成红色 PS:最终pParent最终变成黑色,这是为了满足特征二

情况二:标准的RR型或者LL型

RR型。parent为红色,pParent为黑,uncle为null。先变色,后旋转。将parent变为黑色(特征二),pParent变为红色,然后进行一次左旋

LL型。parent为红色,pParent为黑,uncle为null。先变色,后旋转。将parent变为黑色(特征二),pParent变为红色。然后进行一次右旋

情况三:parent是红色,uncle为nil

parent处于pParent右子树,cur(新插入节点)处于parent左子树。需要先进行一次右旋,成为情况一的RR型,然后再左旋

parent处于pParent左子树,cur(新插入节点)处于parent右子树。需要先进行一次左旋,成为情况一的LL型,然后再右旋

以上就是所有存在的情况。以下我们使用代码实现插入流程

Node.java

public class Node {

    private static int black = 0;
    private static int red = 1;

    private int key = -1;
    /**
     * 节点默认为黑色
     */
    private int color = black;
    /**
     * 左节点
     */
    private Node left;
    /**
     * 右节点
     */
    private Node right;
    /**
     * 父节点
     */
    private Node parent;
    /**
     * 构造函数
     */
    public Node(int key) {
        this.key = key;
    }
}

insert(根据二叉树特性普通插入)

 /**
     * @param root    根节点
     * @param key     插入的新值
     * @return        是否插入成功
     */
    private boolean insert(Node root,int key){

        //如果当前节点为空
        if(root == null){
            root = new Node(key);
            root.color = black;
            root.parent = null;
            return true;
        }else{
            Node tmp = root;
            Node newNode;
            //新添加节点属性
            while (true){
                //从上往下遍历树节点,寻找合适的位置插入
                if(key < tmp.key){
                    //如果小于当前节点 则需要插入在左子树区域
                    if(tmp.left == null){
                        //如果父节点左树为空,那么可以直接插入
                        newNode = getNewNode(key);
                        tmp.left = newNode;
                        newNode.parent = tmp;
                        break;
                    }else{
                        //如果父节点左树不为空,继续往下循环,找到nil节点进行插入
                        tmp = tmp.left;
                    }
                }else{
                    //如果大于当前节点,那么需要放在右子树区域
                    if(tmp.right == null){
                        newNode = getNewNode(key);
                        //如果父节点右树为空,那么可以直接插入
                        tmp.right = newNode;
                        newNode.parent = tmp;
                        break;
                    }else{
                        //如果父节点右树不为空,继续往下循环,找到null节点进行插入
                        tmp = tmp.right;
                    }
                }
            }
            //遍历判断是否需要变色和旋转保持红黑树特性
            stableTree(newNode);
        }
        return true;
    }

遍历每个节点,判断是否需要变色与旋转

/**
     * 判断是否需要变色与旋转维持平衡
     */
    private void stableTree(Node node){
        //只有父节点是红色时,才需要进行判断,黑色的话,直接插入即可
        while (node.parent.color == red){
            //叔叔节点
            Node uncle;
            if(node.parent.parent.left == node){
                //如果cur(新插入)节点的parent在左子树上。那么uncle就在右子树上
                uncle = node.parent.parent.right;
                //情况一:uncle不为null。并且uncle和parent都是红色
                if(uncle != null && uncle.color == red){
                    //只需将parent和uncle都变成黑色,pParent变成红色即可
                    node.parent.color = black;
                    uncle.color = black;
                    node.parent.parent.color = red;
                    //将pParent继续往上遍历,判断是否需要调整
                    node = node.parent.parent;
                    continue;
                }
                //如果uncle不为空
                if(node == node.parent.right){
                    //并且cur节点属于右子树上,说明这是情况3.2。需要左旋一次
                    rotateLeft(node.parent);
                }

                //满足情况2的LL型结构。parent变黑,pParent变红,右旋一次
                node.parent.color = black;
                node.parent.parent.color = red;

                rotateRight(node.parent.parent);
            }else{
                //如果cur(新插入)节点的parent的右子树上,那么uncle在pParent的左子树上
                uncle = node.parent.parent.left;
                //情况一:uncle不为null。并且uncle和parent都是红色
                if(uncle != null && uncle.color == red){
                    //只需将parent和uncle都变成黑色,pParent变成红色即可
                    node.parent.color = black;
                    uncle.color = black;
                    node.parent.parent.color = red;
                    //将pParent继续往上遍历,判断是否需要调整
                    node = node.parent.parent;
                    continue;
                }
                //如果uncle不为空
                if(node == node.parent.left){
                    //并且cur节点属于左子树上,说明这是情况3.1。需要右旋一次
                    rotateRight(node.parent);
                }
                //满足情况2的RR型结构。parent变黑,pParent变红,左旋旋一次
                node.parent.color = black;
                node.parent.parent.color = red;
                rotateLeft(node.parent.parent);
            }
        }
        //需要满足特征2。根节点永远是黑色的
        this.color = black;
    }

左旋

    /**
     * 左旋
     * 和平衡二叉树原理类似,不做过多的解释
     */
    private void rotateLeft(Node bNode){
        if (bNode == bNode.parent.left) {
            bNode.parent.left = bNode.right;
        } else {
            bNode.parent.right = bNode.right;
        }
        bNode.right.parent = bNode.parent;
        bNode.parent = bNode.right;
        if (bNode.right.left != null) {
            bNode.right.left.parent = bNode;
        }
        bNode.right = bNode.right.left;
        bNode.parent.left = bNode;
    }

右旋

    /**
     * 右旋
     * 和平衡二叉树原理类似,不做过多的解释
     */
    private void rotateRight(Node node){
        if (node == node.parent.left) {
            node.parent.left = node.left;
        } else {
            node.parent.right = node.left;
        }

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

插入到此结束。

总结:红黑树的插入比平衡二叉树更为复杂,因为增加了一个颜色的维度判断。但是只需要根据5个特性和3个规则来实现代码,其实也就只是在平衡二叉树的基础上多了个颜色判断而已。从上图可总结出,仅仅只有parent节点为red的时候,才需要进行变色,并且都是parent变黑,pParent变红的规律来调整(因为不能连续出现2个red节点,但是新插入的节点又必须是红色)。变色完成后,再根据uncle节点来判断是否需要进行旋转,如果uncle不为空,那么直接变色即可,如果uncle为空,那么根据parent所在的位置进行旋转,在left就右旋,right就左旋(和平衡二叉树类似)

可能存在问题,如果发现问题,欢迎提出,咋们一起讨论解决~

上一章(玩转红黑树 (第四部分)java实现平衡二叉树(查找,删除))

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×