写点什么

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

用户头像
小Q
关注
发布于: 2020 年 11 月 20 日

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



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





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



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,必须做自平衡。



还有一个删除,实在是太饿了,不行了,不能随随便便应付大家,听我下回分解,哈哈哈哈,咱下次详细的讲解红黑树的应用



文章首发公众号:Java架构师联盟



发布于: 2020 年 11 月 20 日阅读数: 23
用户头像

小Q

关注

还未添加个人签名 2020.06.30 加入

小Q 公众号:Java架构师联盟 作者多年从事一线互联网Java开发的学习历程技术汇总,旨在为大家提供一个清晰详细的学习教程,侧重点更倾向编写Java核心内容。如果能为您提供帮助,请给予支持(关注、点赞、分享)!

评论

发布
暂无评论
快进收藏吃灰!字节跳动大佬用最通俗方法讲明白了红黑树算法