快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

作者 : 开心源码 本文共4197个字,预计阅读时间需要11分钟 发布时间: 2022-05-13 共282人阅读

不知道大家有没有看今天的那个面试官被害视频,我那神奇的同事不知道那个脑回路忽然被打通了,在办公室问了一句:是不是面试官问了一下红黑树,把面试的人给问毛了啊,都问,我不会这个还问,而后暴起下手呀!!而后办公室掀起了一阵探讨热潮

树,这个大学时代数据结构与算法的重点之一,当时真的也是头疼了好久,但是其实现在想想,害,没啥变化,仍旧头疼,看下面这张图,树包含的内容

快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

而树的内容又以二叉树作为重点,先来复习一下基础知识

BST树:

二叉搜索树(Binary Search Tree,简写BST),又称为二叉排序树,属于树的一种,通过二叉树将数据组织起来,树的每个节点都包含了健值key、数据值data、左子节点指针、右子节点指针。其中健值key是最核心的部分,它的值决定了树的组织形状;数据值data是该节点对应的数据,有些场景可以忽略,举个例子,key为身份证号而data为人名,通过身份证号找人名;左子节点指针指向左子节点;右子节点指针指向右子节点。

特点:

左右子树也分别是二叉搜索树。

左子树的所有节点key值都小于它的根节点的key值。右子树的所有节点key值都大于他的根节点的key值。二叉搜索树可以为一棵空树。

一般来说,树中的每个节点的 key值都不相等,但根据需要也可以将相同的key值插入树中

AVL树:

AVL树,也称平衡二叉搜索树,AVL是其发明者姓名简写。AVL树属于树的一种,而且它也是一棵二叉搜索树,不同的是他通过肯定机制能保证二叉搜索树的平衡,平衡的二叉搜索树的查询效率更高。

特点:

AVL树是一棵二叉搜索树。

AVL树的左右子节点也是AVL树。

AVL树拥有二叉搜索树的所有基本特点。

每个节点的左右子节点的高度之差的绝对值最多为1,即平衡因子为范围为[-1,1]。

还有一个就是今天我们探讨的重点:红黑树,我们就来看一下

红黑(Red-black)树

是一种自平衡二叉查找树,1972年由Rudolf Bayer发明,它与AVL树相似,都在插入和删除操作时能通过旋转操作保持二叉查找树的平衡,以便能取得高效的查找性能。它可以在O(logn)时间内做查找,插入和删除等操作。红黑树是2-3-4树的一种等同,但有些红黑树设定只能左边是红树,这种情况就是2-3树的一种等同了。对于AVL树来说,红黑树牺牲了部分平衡性以换取插入/删除操作时一些的旋转操作,整体来说性能要优于AVL树。

特点:

节点是红色或者黑色。根节点是黑色。

每个叶节点(NIL节点)是黑色的。

每个红色节点的两个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

最长路径不超过最短路径的2倍

快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

上图就是一颗简单的红黑树。其中Nil为叶子结点,并且它是黑色的。(H和M的黑色叶子节点没画出来)

详情到此,为了后面讲解不至于混淆,我们还需要来商定下红黑树少量结点的叫法,如图2所示。

快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

我们把正在解决(遍历)的结点叫做当前结点,如图2中的D,它的父亲叫做父结点,它的父亲的另外一个子结点叫做兄弟结点,父亲的父亲叫做祖父结点。

3.基本操作

前面讲到红黑树能自平衡,它靠的是什么?三种操作:左旋、右旋和变色。

  • 左旋:逆时针旋转,父节点被自己的右孩子取代,而自己成为自己的左孩子(注:左旋只影响旋转结点和其右子树的结构,把右子树的结点往左子树挪了。)

快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

  • 右旋:顺时针旋转,父节点被左孩子取代,而自己成为自己的右孩子(注:右旋只影响旋转结点和其左子树的结构,把左子树的结点往右子树挪了。)

快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

  • 变色:结点的颜色由红变黑或者由黑变红。

所以不难看出,无论什么旋转操作都是局部的改变了树的的节点,但要保持红黑树的性质,结点不能乱挪,还得靠变色了。怎样变?具体情景有不同变法,来看一下

快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

至此,变色的任务完成,按照步骤,满足规则,一步步进行,错过一步可能就了解不了了

快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

好了,理论的东西,到这里基本就讲解完了,红黑树难吗?说实话我个人觉得,这破玩意太为难人了

4.红黑树的部分实现

红-黑树的节点实现

红-黑树是对二叉搜索树的改进,所以其节点与二叉搜索树是差不多的,只不过在它基础上添加了一个boolean型变量来表示节点的颜色,具体看RBNode类: public class RBNode<T extends Comparable<T>>{  boolean color; //颜色    T key; //关键字(键值)    RBNode<T> left; //左子节点    RBNode<T> right; //右子节点    RBNode<T> parent; //父节点        public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {  this.key = key;       this.color = color;       this.parent = parent;        this.left = left;        this.right = right;    }       public T getKey() {       return key;   }       public String toString() {       return "" + key + (this.color == RED? "R" : "B");   }}

左旋的具体实现

上面对左旋的概念已经有了感性的认识了,这里就不再赘述了,我们从下面的代码中结合上面的示用意,讨论一下左旋的具体实现: /*************对红黑树节点x进行左旋操作 ******************//* * 左旋示用意:对节点x进行左旋 * 左旋做了三件事:*  1\. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时) *   2\. 将x的父节点p(非空时)赋给y的父节点,同时升级p的子节点为y(左或者右) *    3\. 将y的左子节点设为x,将x的父节点设为y *    */private void leftRotate(RBNode<T> x) {   //1\. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)    RBNode<T> y = x.right;    x.right = y.left;        if(y.left != null)        y.left.parent = x;        //2\. 将x的父节点p(非空时)赋给y的父节点,同时升级p的子节点为y(左或者右)   y.parent = x.parent;       if(x.parent == null) {        this.root = y; //假如x的父节点为空,则将y设为父节点    } else {       if(x == x.parent.left) //假如x是左子节点            x.parent.left = y; //则也将y设为左子节点        else            x.parent.right = y;//否则将y设为右子节点   }        //3\. 将y的左子节点设为x,将x的父节点设为y   y.left = x;    x.parent = y;        }

右旋具体实现

上面对右旋的概念已经有了感性的认识了,这里也不再赘述了,我们从下面的代码中结合上面的示用意,讨论一下右旋的具体实现: /*************对红黑树节点y进行右旋操作 ******************//* * 左旋示用意:对节点y进行右旋 * 右旋做了三件事: *  1\. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时) *   2\. 将y的父节点p(非空时)赋给x的父节点,同时升级p的子节点为x(左或者右) *    3\. 将x的右子节点设为y,将y的父节点设为x *    */private void rightRotate(RBNode<T> y) {  //1\. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)    RBNode<T> x = y.left;   y.left = x.right;       if(x.right != null)        x.right.parent = y;        //2\. 将x的父节点p(非空时)赋给y的父节点,同时升级p的子节点为y(左或者右)    x.parent = y.parent;       if(y.parent == null) {       this.root = x; //假如x的父节点为空,则将y设为父节点 } else {      if(y == y.parent.right) //假如x是左子节点          y.parent.right = x; //则也将y设为左子节点      else          y.parent.left = x;//否则将y设为右子节点   }       //3\. 将y的左子节点设为x,将x的父节点设为y   x.right = y;  y.parent = x;     } 

5.功能

这里我就简单的详情一下,篇幅起因(我不会承认是我饿了,想去吃宵夜了,嘿嘿嘿),后面我会进行详细的详情

5.1查找

由于红黑树是一颗二叉平衡树,并且查找不会破坏树的平衡,所以查找跟二叉平衡树的查找无异,为了让大家更好了解,看下面这张 二叉树查找流程图

快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

非常简单,但简单不代表它效率不好。正因为红黑树总保持黑色完美平衡,所以它的查找最坏时间复杂度为O(2lgN),也即整棵树恰好红黑相隔的时候。能有这么好的查找效率得益于红黑树自平衡的特性,而这背后的付出,红黑树的插入操作功不可没~

5.2 插入

插入操作包括两部分工作:

一查找插入的位置 即找到要插入的父节点;
二插入后自平衡。

查找插入的父结点很简单,跟查找操作区别不大,还是以一张流程图总结一下

快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

特别注意:

假如在面试的时候有人问你插入结点是应该是什么颜色呢?答案是红色。理由很简单,红色在父结点(假如存在)为黑色结点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。但假如插入结点是黑色,那么插入位置所在的子树黑色结点总是多1,必需做自平衡。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 快进收藏吃灰!字节跳动大佬用最浅显方法讲明白了红黑树算法

发表回复