课程介绍
课程目录
用户评论
课程介绍
课程目录
用户评论

你将获得

  • HashMap 基本结构
  • HashMap 源码解析
  • 红黑树、二叉树与平衡二叉树
  • 2-3 树

教学服务

  • 名师授课,不走弯路
  • 高质量技术交流群,圈内大佬云集

讲师介绍

老师头像

高杰

Kotlin 专家、谷歌开发者社区讲师
Kotlin 专家,HenCoder 及码上开学成员之一,受邀担任谷歌开发者社区讲师。拥有丰富的 Android 开发经验,擅长 Android 组件化开发及性能优化,对布局优化、过度绘制、内存泄露等有比较深入的研究。具备丰富的大型互联网金融项目架构设计经验。

课程详情

大家都在问

想了解高级开发课

294人在问去咨询

想了解Compose

294人在问去咨询

怎么加入技术交流群?

294人在问去咨询

知识星球是什么?

294人在问去咨询

红黑树 - 高杰视频文稿

经过前面的介绍,应该理解二三竖是一个什么东西了吧,那么我们的红黑树和二三数有什么关联呢,那这个关联我们先放一下,其实我们可以先看一下二三数和普通的二叉树最大的区别,最大的区别是什么呢,就是二三数有三节点这种东西存在那儿,结点在二叉树中就是一个普通的节点,对吧,在红黑树中,或者说在二叉树中,每个结点都是这种所谓的二节点,但是三结点是二叉树中没有的东西,如果我们想把这个三节点转换为二叉树中有的东西,应该怎么做呢,其实啊,非常简单,首先将这个三节点,分为两个节点,并且让他们互相连接起来,同时呢,因为他们两个其实是一个整体兄弟关系,所以连接他们的方式就稍微特殊一点儿,用红色做标记,不过啊,在二叉树中是没有这种兄弟关系的,所以我们把它排版一下,让他变成二叉树的形式,那这样一来呢,原本的二叉树中不存在的三节点就变成了一个符合二叉树规则的形状,通过这种手段,虽然它是一棵二叉树,但是我们还是可以用它来表示出二三数中的三节点,对吧,另外有一点要注意的是,这个红色引用要怎么表示呢,应该不会有人看到这个红色引用,然后万物皆对象去创建一个表示引用的,累出来吧,我们可以让原本的这个三节点中分裂出去的一个节点改变一下颜色,这样只要在节点类中,比如这个Nord类,那用一个玻璃来控制就可以了,如果这个read为臭,那就是红色节点,那反过来就是黑色节点,那么我们应该让哪个节点变成红色的呢,那当然是这个子节点啦,因为子节点它只有一个父节点,而父节点它是有两个子节点的,什么意思,如果这个父节点是红色的,那么谁知道这个父节点和哪一个子节点才是原来的三节点呢,那儿子节点如果是红色的,那么很快就能知道,其实这两个节点其实是一个三节点,既然我们有办法通过这样的手段让三节点转换为二叉树能够接受的方式,所以我们的二三数就可以通过这样的规则转换为一颗红黑树啦,那么我们就有了这样一颗红黑树,接着呢,我们用这颗红黑树回过头去看一下红黑树的五条定义,这有五条建议,第一条,节点是红色或者黑色的,这个真的是这个废话,那第二条这个根是黑色的,为什么跟一定是黑色呢,让我们从这个二三数的角度来看,如果这个根是二三数中的二节点,这个二节点对应红黑树中的节点,就是黑色的,而如果这个根节点是二三术中的三节的话,这个三节点就是在二叉树上表示的,是需要被拆分的,那么他还是有黑色的节点,并且呢,拆分出来的两个节点不可能是红色的在上面,因为红色的只能是子节点,那这样一来,根结点是黑色的,显然就完全符合啦,那第三点,所有的叶子都是黑色的,叶子是量节点,这里看起来好像不太符合了,但是啊,实际上红黑树的所有叶子节点都是为LAN的黑色节点,我们在看第四条,每个红色节点必须有两个黑色子节点,也就是说,从每个结点到根的所有路径上不能有两个连续的红色节点,那我们继续用二三数的角度上去看,其实很简单,这个红色节点表示有三节点存在,而三节点对应红黑树上其实是一个黑色父节点和一个红色子节点,所以不管你二参数是什么结构,都不可能出现两个连续的红色节点,出现两个红色节点意味着什么,其实就是意味着出现了临时的四节点,那这句话如果理解不了,其实没什么关系,我先往后面看,另外啊,这个第四条的性质的目的,是需要和第五条性质的联系来看的,那我们来看第五条性质,从任意节点到每个叶子节点的所有简单路径,都包含相同数目的黑色节点,这条让我们从二战术的角度上去看,这个二战术本身就是一个平衡术,虽然有了节点上会有两个元素对应红黑树中的有两个节点,但是这两个节点总是只有一个黑色节点,所以这一条规定就很容易符合啦,其实从第五条我们可以看出来,有可能有的陆地上有很多红色节点,那么很显然经过的总节点数量肯定比路径上没有红色结的情况多,那上面这种情况,最左侧的这个两个红色节点的路径,就是最左边这条经过的总的节点数量是二个红色和三个黑色儿,右边的是三个黑色,他们的深度差为二,从这里呢,可以看出来,红黑树并不是一个严格意义上的平衡二叉树,那虽然红黑树不是严格意义上的平衡二叉树