当前位置：首页 > article >正文

没有对象来和我手撕红黑树吧

article 2024/10/30 17:22:42

1. 红黑树的介绍

红黑树也是一种自平衡的二叉搜索树，在每一个节点增加了一个存储位来表示节点的颜色，可以是红色也可以是黑色，通过约束颜色来维持树的平衡，具有以下的性质：

每个节点不是红色就是黑色
根节点为黑色
如果一个节点为红色，那么它的两个孩子节点为黑色（一条路径上不能有两个连续的红色节点）
对于每个节点，从该节点及其所有后代所在的叶子节点的简单路径上，均包含相同数目的黑色节点
每一个叶子节点都是黑色的

2. 节点的定义

这里节点除了包含节点的值，左子树，右子树和父亲节点的引用外，还需要添加颜色的属性

static class RBTreeNode {
    public RBTreeNode left;
    public RBTreeNode right;
    public RBTreeNode parent;
    public int val;
    public COLOR color;

    public RBTreeNode(int val) {
        this.val = val;
        //新创建的节点默认是红色的
        this.color = COLOR.RED;
    }
}

颜色只有红色和黑色，可以使用枚举类来定义节点的颜色

public enum COLOR {
    RED,BLACK
}

节点默认创建为红色的原因：如果节点是黑色，那么插入时就会增加该路径黑色节点的个数，其他路径都需要增加黑色节点，节点是红色的话就不会影响黑色节点的个数，如果上一个节点也是红色，只需要向上调整节点的颜色即可

3. 插入

在寻找插入到哪个位置时，也是和二叉搜索树一样的，（需要注意的是，第一次插入之后需要手动的把 root 节点的颜色修改为黑色）当找到插入的位置之后，可以分为一下几种情况

3.1. p 是左子树

cur 为红色， p 为红色，g 为黑色，u 存在且为红色

两个红色不能连在一起，此时就必须把 p 修改为黑色，然后为了保持黑色是相同的， u 也需要修改为黑色

这个时候就会有一个问题，如果 g 是一个黑色节点的子树，那么这时修改 p , u 就会增加黑色节点的数目，就需要把 g 改为红色，假如 g 就是根节点的话，还是需要把 g 改回黑色，所以说最后处理完之后，无论 g 当前是红色还是黑色，都手动的改为黑色

那如果 g 的父亲节点本身就是红色的话，证明它一定是有父亲节点的，然后按照上面的方式调整之后继续向上调整即可

cur 为红色且是左节点，p 为红色，g 为黑色，u 不存在或者是黑色

如果 u 不存在，那么 cur 一定是新插入的节点，原来的肯定是不能有两个连续的红色节点的

当 u 存在且为黑色的时候

这种情况在调整的过程中会出现

对于这种情况的解决方案就是，先右旋 p ，再调整颜色

cur 为红且是右节点，p 为红，g 为黑，u 不存在或 u 为黑

这种情况也应该是调整过程中出现的

此时对 p 进行一个左旋，然后交换 cur 和 p 的引用，就变成了第二种情况，继续按照第二种的情况调整就好

3.2. p 是右子树

然后就是 p 是右子树的情况，也是和上面一样的三种情况：

cur 为红色， p 为红色，g 为黑色，u 存在且为红色

这种情况和上面的是一样的

cur 为红色且是右节点，p 为红色，g 为黑色，u 不存在或者是黑色

只不过这次是需要右旋的，其余步骤还是和之前一样

cur 为红且是左节点，p 为红，g 为黑，u 不存在或 u 为黑

当以上所有的情况都考虑完之后，还需要手动的把 root 节点的颜色改为黑色

4. 红黑树的验证

验证的话主要就是验证有没有两个红色节点相连和每条路径的黑色节点数量是否相等

先来看红色节点是否相连：只需要在遍历的过程中遇到红色节点之后，去看它的父亲节点是否是红色的即可，然后递归执行

    private boolean checkRedColor(RBTreeNode root){
        if(root == null) return true;
        if(root.color == COLOR.RED){
            RBTreeNode parent = root.parent;
            if(parent.color == COLOR.RED){
                System.out.println("两个红色节点连续了");
                return false;
            }
        }
        return checkRedColor(root.left) && checkRedColor(root.right);
    }

判断每条路径黑色节点的数量是否相同：首先求出一条路径的黑色节点的数量，然后再遍历每条路径，同时统计路径上的黑色节点的个数，和开始计算的出的黑色节点个数对比，如果不相同那么就不满足红黑树的性质

private boolean checkBlackNum(RBTreeNode root,int pathBlackNum,int blackNum){
    if(root == null) return true;
    if(root.color == COLOR.BLACK){
        pathBlackNum++;
    }
    if(root.left == null && root.right == null){
        if(pathBlackNum != blackNum){
            System.out.println("黑色节点不符合要求");
            return false;
        }
    }
    return checkBlackNum(root.left,pathBlackNum,blackNum)&&
    checkBlackNum(root.right,pathBlackNum,blackNum);
}

最后把这两种情况都结合起来，同时还需要判断根节点的颜色是否是黑色

public boolean isRBTree(){
    if(root == null) return true;
    //根节点必须为黑色
    if(root.color != COLOR.BLACK) return false;
    //存储当前红黑树中的黑色节点个数
    int blackNum = 0;
    RBTreeNode cur = root;
    while(cur!=null){
        if(cur.color == COLOR.BLACK){
            blackNum++;
        }
        cur = cur.left;
    }
    //检查是否存在两个连续的红色节点和每条路径的黑色节点是否相同
    return checkRedColor(root) && checkBlackNum(root, 0, blackNum);
}

查看全文

http://www.kler.cn/a/371831.html