当前位置 博文首页 > m0_58397045的博客:Java二维数组输出猫狗
面:考你几个红黑树的知识点🦀
面:2-3树都是不没看,回去等消息吧!
红黑树规则
1. 根节点是黑色
2. 节点是红黑或者黑色
3. 所有子叶节点都是黑色(叶子是NIL节点,默认没有画出来)
4. 每个红色节点必须有两个黑色子节点(也同样说明一条链路上不能有链路的红色节点)
5. 黑高,从任一节点到齐每个叶子节点,经过的路径都包含相同数目的黑色节点
那么,这些规则是怎么总结定义出来的呢?接下里我们一步步分析讲解。
首先2-3树
(读法:二三树)就是一个节点有1个或者2个元素,而实际上2-3树转红黑树是由概念模型2-3-4树
转换而来的。-4叉
就是一个节点里有3个元素,这在2-3树中会被调整,但是在概念模型中是会被保留的。
虽然2-3-4树
也是具备2-3树
同样的平衡树的特性,但是如果直接把这样的模型用代码实现就会很麻烦,且效率不高,这里的复杂点包括;
所以,希望找到一种平衡关系,既保持2-3树平衡和O(logn)的特性,又能在代码实现上更加方便,那么就诞生了红黑树。
2-3树
转红黑树,也可以说红黑树是2-3树
和2-3-4树
的另外一种表现形式,也就是更利于编码实现的形式。
简单转换示例;
从上图可以看出,2-3-4树与红黑树的转换关系,包括;
综上,就是2-3-4树的节点转换,总结出来的规则,如下;
在简单2-3树转换红黑树
的过程中,了解到一个基本的转换规则右旋定义,接下来我们在一个稍微复杂一点的2-3树
与红黑树的对应关系,如下图;
上图是一个稍微复杂点的2-3树,转换为红黑树的过程,是不这样一张图让你对红黑树更有感觉了,同时它也满足一下条件;
通过在上一章节2-3树的学习,在插入节点时并不会插到空位置,而是与现有节点融合以及调整,保持整个树的平衡。
而红黑树是2-3-4树的一种概念模型转换而来,在插入节点时通过红色链接相连,也就是插入红色节点。插入完成后进行调整,以保持树接近平衡。
那么,为了让红黑树达到平衡状态,主要包括染色、?左右旋转、这些做法其实都是从2-3树演化过来的。接下来我们就分别讲解几种规则的演化过程,以此更好了解红黑树的平衡操作。
左旋定义: 把一个向右倾斜的红节点链接(2-3树,3-叉双元素节点),转化为左链接。
背景:顺序插入元素,1、2、3,2-3树保持平衡,红黑树暂时处于右倾斜。
接下来我们分别对比两种树结构的平衡操作;
红黑树的左旋,只会处理与之对应的2-3树节点进行操作,不会整体改变。
右旋定义: 把一个向左倾斜的红节点连接(2-3树,3-叉双元素节点),转换为右连接。
背景:顺序插入元素,3、1、1,2-3树保持平衡,红黑树暂时处于左倾斜。
接下来我们分别对比两种树结构的平衡操作;
你会发现,左旋与右旋是相互对应的,但在2-3树中是保持不变的
左旋、右旋,我们已经有了一个基本的概念,那么接下来我们再看一个可以综合左右旋以及对应2-3树的演化案例,如下;
以上的例子分别演示了一个元素插入的三种情况,如下;
在2-3树中,插入一个节点,为了保持树平衡是不插入到空位置上的,当插入节点后元素数量有3个后则需要调整中间元素向上,来保持树平衡。与之对应的红黑树则需要调整颜色,来保证红黑树的平衡规则,具体参考如下;
接下来我们把上面讲解到的旋转
、染色
,运用到一个实际案例中,如下图;
7、2、8、1、4、3、5
3、5、6
。7、4、2
,最小节点在中间,左旋平衡树结构。7、4、2
为做倾顺序节点,因此需要做右旋操作。注意,所有连接红色节点的,都是是红色线。以此与2-3树做对应。
根据2-3-4树模型的红黑树,在删除的时候基本是按照2-3方式进行删除,只不过在这个过程中需要染色和旋转操作,以保持树平衡。删除过程主要可以分为如图四种情况,如下;
红色子叶节点的删除并不会破坏树平衡,也不影响树高,所以直接删除即可,如下;
其实我投简历的时候,都不太敢投递阿里。因为在阿里一面前已经过了字节的三次面试,投阿里的简历一直没被捞,所以以为简历就挂了。
特别感谢一面的面试官捞了我,给了我机会,同时也认可我的努力和态度。对比我的面经和其他大佬的面经,自己真的是运气好。别人8成实力,我可能8成运气。所以对我而言,我要继续加倍努力,弥补自己技术上的不足,以及与科班大佬们基础上的差距。希望自己能继续保持学习的热情,继续努力走下去。
也祝愿各位同学,都能找到自己心动的offer。
分享我在这次面试前所做的准备(刷题复习资料以及一些大佬们的学习笔记和学习路线),都已经整理成了电子文档,需要的朋友可以【点赞+关注】戳这里即可免费获取
能8成运气。所以对我而言,我要继续加倍努力,弥补自己技术上的不足,以及与科班大佬们基础上的差距。希望自己能继续保持学习的热情,继续努力走下去。
也祝愿各位同学,都能找到自己心动的offer。
分享我在这次面试前所做的准备(刷题复习资料以及一些大佬们的学习笔记和学习路线),都已经整理成了电子文档,需要的朋友可以【点赞+关注】戳这里即可免费获取
cs