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

原创
11/20 14:30
阅读数 4.3K

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

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

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

 

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

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架构师联盟

展开阅读全文
打赏
2
9 收藏
分享
加载中
写的很棒,通俗易懂。
11/21 07:54
回复
举报
更多评论
打赏
1 评论
9 收藏
2
分享
返回顶部
顶部