1. AI技术聚合首页
  2. IT

数据结构奇妙旅程之红黑树

xiaoxingxing • • IT • 阅读 26

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱
ʕ̯•͡˔•̯᷅ʔ大家好，我是xiaoxie.希望你看完之后,有不足之处请多多谅解，让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶
个人主页：xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
系列专栏：xiaoxie的JAVA系列专栏——CSDN博客●’ᴗ’σσணღ*
我的目标:”团团等我💪( ◡̀_◡́ ҂)” 

( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​+关注（互三必回）!

一.红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何 一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

二.红黑树的性质

1. 每个结点不是红色就是黑色

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的【没有2个连续的红色节点】

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 

三.红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点

2. 检测新节点插入后，红黑树的性质是否造到破坏 因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要 调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对 红黑树分情况来讨论： 

 这里解释一下为什么新插入的节点是红色的,因为假如插入节点的节点是黑色的,那么为了要满足性质4对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点就需要再插入节点为了满足性质4,这样就浪费很多空间,而要是新插入的节点是红色的,我们只需要调整颜色即可.

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

1.情况一: cur为红，p为红，g为黑，u存在且为红

出现这种情况情况,我们先需要把p和u 变成黑色,然后再把g变成红色即可.

这个时候,还需要考虑到

1.g为根节点,只需要在调整结束后,把它变为黑色即可

2.g有双亲节点,且为红色就需要将g当成cur,继续向上调整。(如果双亲节点,为黑色,p和g 变成黑色,然后再把g变成红色后就不违反红黑树的性质了)

这里再解释一下为什么要把把p和u变成黑色,然后再把g变成红色.

1.首先把p变成红色是因为cur为红色,p也为红色的话就违反了性质3,不能有两个连续的红色节点,所以需要把p变成黑色.

2.为什么要把u变成黑色是因为性质4,每条路径要有相同路径的黑色节点,如果u为红色,p为黑色就不满足该性质,所以要把u变成黑色

3.为什么要把g变成红色,因为假如g还有双亲节点的话,且双亲节点为黑色,那么,由于p和u变成了黑色,为了要满足,性质4,每条路径要有相同路径的黑色节点,就需要增加黑色节点的个数,所以需要把g变成红色,p和u变成黑色,就满足了性质4

 2.情况二:cur为红，p为红, g为黑，u不存在/u为黑

就是因为在出现情况一之后,调整,p,u,g的颜色导致了情况二的发生

我们该如何调整调整使它满足红黑树的五条性质呢,我们可以发现,仅仅简单的改变颜色并不可以满足红黑树的五条性质,这个时候我们可以发现,这个情况是不是很像AVL树树中的左树高于,右数的情况,这个时候对于AVL树来说,可以使用右旋来解决这个问题,我们是不是也可以通过旋转操作可以调整节点的位置,然后只要在稍微改变个边节点的颜色即使它满足红黑树的性质.

右旋后再根据红黑树的性质,把g变为红色,p变为黑色,即可 

3.情况三: cur为红，p为红，g为黑，u不存在/u为黑 

在调整的过程中,cur变成了红色,导致情况三的发生, 同时,我们发现和AVL树类似,仅仅通过左旋或者右旋并不可以可以调整节点的位置,因为是较高左树的右子树较高,我们先进行,左旋.

通过左旋我们发现,可以把问题转换为情况二,即可解决该问题.

4.说明

从上面的这些情况我们可以发现,在上面这些图中,p都为g的左孩子的情况,p为g右孩子的情况我并没有说明,在这里博主统一说明一下,因为p为g右孩子的情况就是p都为g的左孩子的情况的相当于镜像处理即

在情况二中

p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反， p为g的右孩子，cur为p的右孩子，则进行左单旋转

在情况三中

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

所以博主就不展示调整过程了,直接上代码

5.代码实现

public class RBTree {
    public static enum COLOR {RED, BLACK} // 定义颜色枚举，表示节点的红黑状态

    // 红黑树节点类
    public 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 RbTreeNode root;

    // 插入新节点方法
    public boolean insert(int val) {
        RbTreeNode node = new RbTreeNode(val);
        if(root == null) {
            root = node;
            return true;
        }

        // 寻找插入位置
        RbTreeNode cur = root;
        RbTreeNode parent = null;
        while (cur != null) {
            if(node.val < cur.val) {
                parent = cur;
                cur = cur.left;
            } else if(node.val > cur.val) {
                parent = cur;
                cur = cur.right;
            } else {
                System.out.println("这个节点" + val +"已经存在了");
                return false;
            }
        }

        // 插入新节点并更新父节点指向
        if(parent.val < node.val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        node.parent = parent;

        // 调整红黑树性质
        cur = node;
        while (parent != null && parent.color == COLOR.RED) {
            RbTreeNode grandfather = parent.parent;
                if(parent == grandfather.left) {//p节点为g节点的左孩子
                RbTreeNode uncle = grandfather.right;
                //uncle不为空,且uncle的颜色为红色
            // 获取叔叔节点
          
            // 情况一：叔叔节点存在且为红色
            if(uncle != null && uncle.color == COLOR.RED) {
                grandfather.color = COLOR.RED;
                parent.color = COLOR.BLACK;
                uncle.color = COLOR.BLACK;
                cur = grandfather;
                parent = cur.parent;
            } else {
                // 情况三：叔叔节点不存在或为黑色
                if(cur == parent.right) { // 需要左旋
                    rotateLeft(parent);
                    RbTreeNode tmp = parent;
                    parent = cur;
                    cur = tmp;
                }
                //情况二:叔叔节点不存在或为黑色
                rotateRight(grandfather); // 右旋以修复红黑树性质
                grandfather.color = COLOR.RED;
                parent.color = COLOR.BLACK;
            }else {///p节点为g节点的右孩子//镜像处理和/p节点为g节点的左孩子类似
                 RbTreeNode uncle = grandfather.left;
                if(uncle != null && uncle.color == COLOR.RED) {
                    grandfather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    cur = grandfather;
                    parent = cur.parent;
                }else {
                    //情况三
                    if(cur == parent.left) {
                        rotateRight(parent);
                        RbTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }
                    //情况二
                    //叔叔节点不存在 || 叔叔节点存在，但是颜色是黑色
                    rotateLeft(grandfather);
                    grandfather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }
        }

        return true;
    }

    /**
     * 右旋操作
     * @param parent 需要右旋的节点（旋转中心）
     */
    private void rotateRight(RbTreeNode parent) {
        RbTreeNode subL = parent.left;
        RbTreeNode subLR = subL.right;

        subL.right = parent;
        parent.left = subLR;

        if(subLR != null) {
            subLR.parent = parent;
        }

        RbTreeNode Pparent = parent.parent;
        parent.parent = subL;

        if(parent == root) {
            root = subL;
            root.parent = null;
            root.color = COLOR.BLACK;//如果是根节点就要为黑色
        } else {
            if(Pparent.left == parent) {
                Pparent.left = subL;
            } else {
                Pparent.right = subL;
            }
            subL.parent = Pparent;
        }
    }

    /**
     * 左旋操作
     * @param parent 需要左旋的节点（旋转中心）
     */
    private void rotateLeft(RbTreeNode parent) {
        RbTreeNode subR = parent.right;
        RbTreeNode subRL = subR.left;

        subR.left = parent;
        parent.right = subRL;

        if(subRL != null) {
            subRL.parent = parent;
        }

        // 记录parent节点的父亲节点
        RbTreeNode Pparent = parent.parent;
        parent.parent = subR;

        if(parent == root) {
            root = subR;
            subR.parent = null;
            root.color = COLOR.BLACK;//如果是根节点就要为黑色
        } else {
            if(Pparent.left == parent) {
                Pparent.left = subR;
            } else {
                Pparent.right = subR;
            }
            subR.parent = Pparent;
        }
    }
}

好了，这三种情况都讨论完了，我想强调的是：注意哪些分方向的情况，每个分方向的情形就两种情况

四.红黑树验证

这里博主在提供一下红黑树验证的方法,检测一下你自己手撕红黑树代码有没有错误

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

public void inorder(RBTreeNode root) {
if(root == null) {
return;
}
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}

2.检测其是否满足红黑树的性质

public boolean isValidRBTree()
{
// 空树也是红黑树
if(null == root)
return true;
if(root.color != COLOR.BLACK) {
System.out.println("违反了性质2：根节点不是黑色");
return false;
}
// 获取单条路径中节点的个数
int blackCount = 0;
RBTreeNode cur = root;
while(null != cur){
if(cur.color == COLOR.BLACK)
blackCount++;
cur = cur.left;
}
// 具体的检验方式
return _isValidRBtree(root, 0, blackCount);
}
private boolean _isValidRBtree(RBTreeNode root, int pathCount, int blackCount){
if(null == root)
return true;
// 遇到一个黑色节点，统计当前路径中黑色节点个数
if(root.color == COLOR.BLACK)
pathCount++;
// 验证性质4
RBTreeNode parent = root.parent;
if(parent != null && parent.color == COLOR.RED && root.color == COLOR.RED){
System.out.println("违反了性质4：有连在一起的红色节点");
return true;
}
// 验证性质5
// 如果是叶子节点，则一条路径已经走到底，检验该条路径中黑色节点总个数是否与先前统计的结果相同
if(root.left == null && root.right == null){
if(pathCount != blackCount){
System.out.println("违反了性质5：路径中黑色节点格式不一致");
return false;
}
}
// 以递归的方式检测root的左右子树
return _isValidRBtree(root.left, pathCount, blackCount) &&
_isValidRBtree(root.right, pathCount, blackCount);
}

5. AVL树和红黑树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN )，红黑树不追求绝对平衡，其只需保 证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

版权声明：本文为博主作者：小谢在努力原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/xiaoxie8023/article/details/136792334

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2024年4月1日
下一篇 2024年4月1日

相关推荐