您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

红黑树以及JAVA实现

时间:2022-08-15 13:59:49  来源:CSDN  作者:七包辣条

前言

红黑树是一种特殊的B树是B树种2-3-4树的一种特殊实现,红黑树保证了每个节点只会有两个子节点,通过对每个节点进行染色,然后通过不同颜色的节点组合来分别代表2-3-4的2节点、3节点、4节点树的情况。在学习红黑树之前,我们需要先去了解2-3-4树。

一、 B树

那么如果想要对红黑树有一个较为深刻的理解,我认为首先去理解其根源,也就是B树是必不可少的

1.1 概念

树形结构首先可以分为等叉树和不等叉树,等叉树是每个节点的键值个数都相同、子节点个数也都相同,不等叉树是每个节点的键值个数不一定相同、子节点个数也不一定相同。

最简单的等叉树是二叉树,直接二叉树的作用并不大,我们一般会要求二叉树所有的节点按照一定的顺序排列,这样我们进行插入、删除、查找时效率就会非常高,我们把这样的树叫做二叉搜索树或者二叉查找树。它的具体定义是这样的,二叉搜索树,要么是个空树,要么符合以下几个条件:

  1. 左子树如果存在的话,左子树所有节点的键值都要小于根节点的键值
  2. 右子树如果存在的话,右子树所有节点的键值都要大于根节点的键值
  3. 它的所有子树也都要符合前面的两个条件(前面的小于同时换成大于也成立)。

经过这样定义之后,二叉树就变成了二叉搜索树,它的插入、删除、查找效率一般情况下都是O(logn)。

相较于等叉树,我们可以对不等叉树的节点键数值数和插入、删除逻辑添加一些特殊的要求使其能达到绝对平衡的效果,我们把这种树叫做 B树,全称Balance Tree,是一种自平衡树,它和等叉树最大的不同首先表现在存储结构上,等叉树上每个几点的键值数和分叉数都是相同的,而B树不是。如果某个B树上所有节点的分叉数最大值是m,则把这个B数叫做m阶B数。下面我们来看一下B树的具体定义:

  1. 所有节点最多有m个子节点
  2. 非根非叶子结点至少有m/2(向上取整)个子节点
  3. 根节点至少有两个子节点(除非总结点数不足3个)
  4. 所有叶子节点都在同一层
  5. 任意节点如果有k个键值,则有k+1个子节点指针,键值要按照从小到大排列,子节点数上所有的键值都要在对应的两个键值之间

B树看似5条定义很复杂,但实际上自己分析一下理解后会发现还是蛮简单的。第一条,对子节点数进行限制,这也是m阶B树m的由来,第二条,是用来限制树的紧凑性,避免树又高又长。第三条没什么好说的。第四条规定了B树是一个绝对平衡树不会退化为线性结构,所以B树的效率永远是O(logn)。第5条保证了B树的元素的有序,以便高效率的查找。

1.2 2-3-4树

2-3-4树其实就是4阶的B树,目前网上讲的红黑树大多数就是2-3树或者是2-3-4树转化而成的。这里仅对2-3-4树进行讲解

1.3 2-3-4树的插入

节点分类

  • 2节点:一个节点中有1个键值,2条链接
  • 3节点:一个节点中有2个键值,3条链接
  • 4节点:一个节点中有3个键值,4条链接

首先是2节点的插入,由于2-3-4树是4阶B树,最多可以有4条连接,一个节点最多有3个键值,所以这里直接添加即可

 

然后是3节点的插入,2节点插入之后,转化为4节点,仍保持一个节点的状态

 

4节点插入,由于2-3-4树是4阶B树,所以当对4节点插入的时候,就需要对4节点进行分裂,首先将中间的节点上升,然后,根据B树定义,将新增的节点和叶子的其中一个节点结合,形成一个3节点,比如,下图中要插入4,首先123分裂,之后4根据大小顺序,放在3的右边,和3形成一个3节点。

 

之后如果继续插入,第二层节点如果再形成4节点的情况下插入,那么分裂之后出来的节点,应该和父节点再构成节点

 

如果向上和父节点构成节点,但是父节点已经是4节点了,这个时候父节点就需要继续分裂,在往上的情况一次类推,进行递归分裂

 

1.4 2-3-4树的删除

相对于插入,B树的删除就相对复杂,需要分情况讨论

1.4.1 当删除节点是叶子节点

当删除节点是叶子节点的时候,又分为以下情况

1.4.1.1 当删除节点为非2节点

直接删除即可,因为从一个非2节点中删除一个键值以后,并不违反B树的定义

1.4.1.2 当删除节点为2节点

这种情况又要分多种情况

1.4.1.2.1 兄弟节点是非2节点

当兄弟节点是非2节点,我们可以直接从兄弟节点借一个元素过来,让当前删除节点形成非2节点,这样情况就转换为了2.3.3.1的情况,直接删除要删除的节点既可

 

1.4.1.2.2 兄弟节点是2节点

如果兄弟节点是2节点,那么此时就需要从父节点借元素了,待删除结点和父节点、兄弟节点构成一个4节点,然后将待删除节点删。

如果父节点是非2节点,那么借走就接走了,如果是2节点,借走了当前位置就空了,所以需要再从这个节点的兄弟或父节点借一个元素,如果直到根节点也没有找到一个非2节点,那么这个B树的高度就会减一。

 

1.4.2 如果删除节点是非叶子节点

  1. 如果被删除节点是非叶子节点,那么我们就需要找到他的后继元素,然后将后继元素的值覆盖被删除元素,再将后继元素删除即可
  2. 那么如何寻找后继节点呢?一般来说就是key大小最接近被删除元素的叶子节点中的元素,这个元素可以大于key也可以小于key,这个是我们可以自己定义,这里我们选小于被删除元素的那个。也就是左子树节点中最大的元素。

 

二、 红黑树

通过上一节,我们了解了红黑树的前身或者说是其本源B树之后我们再来看红黑树,相信你能够更容易理解红黑树,看出其操作的底层逻辑

在讲解之前我先讲红黑树的类结构放出来

public class RedBlackBST<Key extends Comparable<Key>, Value> {

    //很明显,这个常量用来代指红或黑
    private static final boolean Red = true;

    private static final boolean Black = false;

    //根节点
    private Node root;


    //节点类结构
    private class Node {
        Key key;
        Value value;
        Node left, right, parent;
        int N;
        boolean color;

        public Node(Key key, Value value, Node parent, int n, boolean color) {
            this.key = key;
            this.value = value;
            N = n;
            this.color = color;
            this.parent = parent;
        }

    }

    public RedBlackBST() {

    }

    //用来判断一个节点是还是黑色
    private boolean isRed(Node x) {
        if (x == null) return false;
        return x.color == Red;
    }

}

2.1 红黑树的定义

红黑树,本质上其实就是将一个B树(我们这里讨论2-3-4树)转化为一个二叉树。那么如何去转化的同时又能继承B树绝对平衡性呢?答案就是通过染色和旋转,到这里打住,让我们先来看红黑树的定义

  1. 所有的节点不是黑色就是红色
  2. 根节点是黑色的
  3. 所有叶子节点是黑色的
  4. 从每个叶子到跟的所有路径上不能有两个连续的红色节点
  5. 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点

2.2 2-3-4树节点到红黑树的转换

在解释这几个定义之前我们需要先来开2-3-4树中节点转化到红黑树中的形式是怎样的

首先我们要明白的是,在红黑树中,只有黑色节点才计入高度,红色节点代表着其和父节点的链接是红色的。

非2节点由黑色节点+红色节点组合的形式表示,红黑树对应到2-3-4树的节点组合中只会存在一个黑色节点。

2.2.1 2节点转换

 

2.2.2 3节点转换

3节点转换成红黑树就是一个黑色节点带着红色子节点的树,这个树可以是左倾的也可以是右倾的,根据节点的key来决定,在以2-3树为基础实现的红黑树中,我们一般只允许左倾或则右倾树存在,如果出现不允许的倾斜树情况,一般会通过旋转变色来调整。

 

2.2.3 4节点转换

 

2.2.4 例子

 

2.3 红黑树定义解释

先在我们再来来挨个看这5条定义

  1. 第一条这个没什么好说的,红黑树红黑树,那肯定节点不是红色就是黑色
  2. 由于根节点必然是没有父节点的,而在上面我们所列举的转换形式中并没有红色节点为父节点的结构,所以根节点必然是黑色的
  3. 在红黑树中叶子节点会默认拥有两个为null的子节点,颜色自然是黑色
  4. 不允许又连续两个红色节点是为了限制红黑树的阶数为4,不允许出现2、3、4节点之外的节点类型
  5. 对应2-3-4树的第五条,保证了树的绝对平衡,对应到红黑树中只有黑色节点代表高度,所以只需要保证黑色节点的数目一致即可。

2.3.1 红黑树的旋转与变色

我们在对红黑树进行添加的时候,一开始按照二叉树的方式添加,每个新节点的初始元素为红色(root节点为黑色),当我们继续进行添加,发现当前的红黑树结构不符合定义时,我们就需要通过旋转和对节点变色来重新平衡红黑树。

2.3.2 红黑树的旋转

先说旋转,红黑树的旋转分为左旋和右旋,我们先通过左旋来进行详细讲解。左旋就是一个节点绕着他的右子节点逆时针旋转,变成右子节点的左子节点,我们以下图为例

 

A进行左旋,变成B的左子节点,于此同时,B原先的左子树变成A的右子树,A的父节点变为B的父节点。

A的左子树依旧是A的左子树,B的右子树也依旧是B的右子树,不做变化。

这样,我们就完成了一次左旋,右旋则是绕则操作节点自身的子节点顺时针旋转,变成左子节点的右子树,左子节点的右子树迁移到操作节点的左子树,操作节点的父节点变成左子节点的父节点。原理一模一样。

2.3.3 红黑树的变色

当然,我们在旋转以后,如果不变色,结果肯定是不正确的,只有进行变色之后的红黑树才是正确的,由于变色有很多种情况,所以我们这里只举一个简单的例子,后面在讲解添加和删除的时候再进行细致列举。

 

首先我们这里有一个两个节点的二叉树,现在他是正确的,这个时候我们再插入一个新的节点3,那么根据二叉树的性质,插入后这个树会变成这个样子

 

当然,这个结果明显是错误的,其结构明显不符合我们我们在2.2.2中展示的任何一种形式,所以我们要通过旋转和变色变换为2.2.2中的哪几种形式。

 

首先这个组合在2-3-4树种是一个4节点,但是他的形态并不符合红黑树的节点,所以我们需要将它转换为已个合法的形态,先进行旋转,1节点左旋,这个时候结构对了,但是颜色不对,需要将2变色为黑色,而1变色为红色,这样我们的这个红黑树就完全符合定义了。

 

这就是一个最简单的旋转变色的红黑树自动平衡过程。

下面是左旋和右旋的JAVA代码实现,并没有添加变色,因为变色的逻辑并不是固定的故而我们将其解耦到其他方法中

//左旋
    Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        if(h.right!=null){
            h.right.parent = h;
        }
        x.parent = h.parent;
        h.parent = x;
        x.left = h;
        if(x.left!=null){
            x.left.parent = x;
        }
        if(x.parent!=null){
            int cmp = x.parent.key.compareTo(x.key);
            if(cmp>0) x.parent.left = x;
            else x.parent.right = x;
        }
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        show();
        return x;
    }

    //右旋
    Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        if(h.left!=null){
            h.left.parent = h;
        }
        x.parent = h.parent;
        h.parent = x;
        x.right = h;
        if(x.right!=null){
            x.right.parent = x;
        }
        if(x.parent!=null){
            int cmp = x.parent.key.compareTo(x.key);
            if(cmp>0) x.parent.left = x;
            else x.parent.right = x;
        }
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        show();
        return x;
    }

2.4 红黑树的添加

红黑树的添加分为以下几种情况

2.4.1 在黑色节点下面插入

这种情况无论是插入在左还是右,都可以直接插入,红黑树的正确性不会受到影响

2.4.2 在红色节点下插入且被插入节点无兄弟节点

2.4.2.1 当被插入的节点是右子节点

 

在右侧插入

 

操作步骤:

1.节点1左旋


2. 变色,1变色为红色, 2变色为黑色

在左侧插入

 

这种情况会比上面那种多一个步骤

1.节点3右旋,无需变色,这个操作主要是为了将情况转换为上面在右侧插入的情况,然后下面按照在右侧的情况处理即可

2.节点1左旋

3.变色,1变色为红色,2变色为黑色

2.4.2.2 当被插入节点是左子节点

其实这种情况和上面的处理逻辑是一样的,只不过左右是反过来的,就不再赘述了,大家自己举一反三即可。

2.4.3 在红色节点下插入且被插入节点有兄弟节点

这种时候,我们需要先进行变色,再插入,如下图(这里,我们默认,1节点是有父节点的,1节点非根节点)

 

2和3节点变黑色,1节点变红色,这个变化其实对应着2-3-4树的4节点插入,其实就是将一个4节点拆分开来,中间的节点向上和父节点组合,左右两边的节点分裂为两个单独的节点,然后再正常插入一个新的节点。红黑树也是这么个道理。

2、3节点变黑,形成单独的节点,而1节点则变红和父节点结合,那么这里我们要注意的是,1节点和父节点结合的时候,也相当于一次新的插入,相当于在1的父节点新插入一个红色,所以这个过程是递归的,一直向上传递,直到红黑树的结构符合定义为止。

 

到这里,红黑树的插入操作就结束了,以上的操作,只是单纯的一步操作,这些操作只是在插入之后对被插入节点红黑树的一个平衡,我们在进行旋转变色之后,很有可能上层的节点就又不符合定义了,这个时候我们就需要进行递归的旋转变色, 直到最后整个红黑树平衡。

下面扔代码


        if (cmp < 0) h.left = put(h.left, h, key, val);
        else if (cmp > 0) h.right = put(h.right, h, key, val);
        else h.value = val;

        //判断红黑,进行旋转,调整树的平衡
        if (isRed(h.right) && isRed(h.right.right)) {
            h.right.color = h.color;
            h.color = Red;
            h = rotateLeft(h);
        }
        if (isRed(h.right) && isRed(h.right.left)) {
            //RL问题,先右旋,将问题转换为RR
            h.right = rotateRight(h.right);
            //变色
            h.right.color = h.color;
            h.color = Red;
            //再左旋
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h.left.color = h.color;
            h.color = Red;
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.left.right)) {
            //LR问题,先左旋,将问题转换为LL问题
            h.left = rotateLeft(h.left);
            //变色
            h.left.color = h.color;
            h.color = Red;
            //再右旋
            h = rotateRight(h);
        }

        h.N = size(h.left) + size(h.right) + 1;

        return h;
    }

欢迎点赞关注+转发!



Tags:红黑树   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
C++ STL之std::map:红黑树的魔法与性能测试
最近在使用C++写代码,也是刚接触C++,恰巧碰到一个需要使用map的地方,不知道其查找元素的性能怎么样,所以研究了下,做个记录,目前从x86平台测试map查找一个元素大概需要2us,这里你需...【详细内容】
2023-11-23  Search: 红黑树  点击:(201)  评论:(0)  加入收藏
一文搞懂二叉搜索树、B树、B+树、AVL树、红黑树
我们假设B+树一个节点可以有100个关键字,那么3层的B树可以容纳大概1000000多个关键字(100+101100+101101*100)。而红黑树要存储这么多至少要20层。所以使用B树相对于红黑树和A...【详细内容】
2023-08-29  Search: 红黑树  点击:(408)  评论:(0)  加入收藏
红黑树插入调整方案
红黑树插入有五种情况,每种情况对应着不同的调整方法:一、 新结点(A)位于树根,没有父结点。直接让新结点变色为黑色,规则2得到满足。同时,黑色的根结点使得每条路径上的黑色结点数...【详细内容】
2023-03-31  Search: 红黑树  点击:(239)  评论:(0)  加入收藏
面试让我手写红黑树
作者:小傅哥 博客:https://bugstack.cn沉淀、分享、成长,让自己和他人都能有所收获!一、前言:挂在树上!不知道你经历过HashMap的夺命连环问!为啥,面试官那么喜欢让你聊聊 HashMap?因...【详细内容】
2022-10-10  Search: 红黑树  点击:(218)  评论:(0)  加入收藏
比红黑树更快的跳表到底是什么数据结构?如何实现?
前言在头条创作了一个月左右的时间,收获了50+粉丝,很是开心,我会把数据结构与算法的文章更新到底,第一次看我文章的同仁如果觉得不错的话就关注一下我哦,你的支持就是我创作的动...【详细内容】
2022-10-10  Search: 红黑树  点击:(316)  评论:(0)  加入收藏
红黑树以及JAVA实现
前言红黑树是一种特殊的B树是B树种2-3-4树的一种特殊实现,红黑树保证了每个节点只会有两个子节点,通过对每个节点进行染色,然后通过不同颜色的节点组合来分别代表2-3-4的2节点...【详细内容】
2022-08-15  Search: 红黑树  点击:(313)  评论:(0)  加入收藏
数据结构 --- 红黑树
和AVL树一样,红黑树也是自平衡二叉搜索树。红黑树同样解决了在特定情况下二叉搜索树会退化成链表的问题。但是红黑树又不像AVL树那样高度平衡,这就让红黑树在插入删除频繁的场...【详细内容】
2022-06-16  Search: 红黑树  点击:(268)  评论:(0)  加入收藏
红黑树底层原理及Linux内核红黑树算法深度研究
1. 红黑树1.1 红黑树概述红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL...【详细内容】
2021-06-24  Search: 红黑树  点击:(404)  评论:(0)  加入收藏
一文看懂 HashMap 中的红黑树实现原理
前言本文咱们了解一下红黑树的设计,相比 jdk1.7 的 HashMap 而言,jdk1.8 最重要的就是引入了红黑树的设计,当冲突的链表长度超过 8 个的时候,链表结构就会转为红黑树结构。01、...【详细内容】
2021-01-18  Search: 红黑树  点击:(355)  评论:(0)  加入收藏
看了两天HashMap源码,终于把红黑树插入平衡规则搞懂了
絮叨学校短学期刚结束了,离学校开学还有很多天,一直呆在寝室玩游戏岂不是浪费了大好时光,于是心血来潮想看看HashMap的源码。虽然我没有经历过面试,但是java程序员都知道,HashMap...【详细内容】
2020-09-27  Search: 红黑树  点击:(284)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(14)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(51)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(45)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(77)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(87)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(96)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(64)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(108)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(78)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(165)  评论:(0)  加入收藏
站内最新
站内热门
站内头条