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

你将获得

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

教学服务

  • 学习群答疑
  • 面试指导
  • 名师实战授课,作业练习
  • 高质量技术交流群

讲师介绍

老师头像

高杰

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

免费领取资料

免费领取资料

试听课|课程目录|课程大纲|关键知识点

课程详情

添加助教微信咨询课程,领取试听课/课程大纲:rengwuxian001

大家都在问

想了解高级开发课

294人在问去咨询

想了解Compose

294人在问去咨询

怎么加入技术交流群?

294人在问去咨询

知识星球是什么?

294人在问去咨询

2-3 树 - 高杰视频文稿

前面我们提到了平衡二叉树,那么既然讲了这么多,所以什么是红黑树呢,让我们来打开微机百科来看一下红黑树的介绍,微机百科宏伟的介绍,这里是它的一些介绍,然后用途和好处,然后这里有它的性质,这里有兴致,红黑树是每个节点都带有颜色属性的,二叉查找树颜色为红色或黑色,在二叉查找树强制一般要求以外,对于任何有效的红黑树,我们增加了如下的额外要求,第一,节点是红色和黑色的,这个很好理解,第二,根是黑色的,第三,所有的叶子节点都是黑色的,叶子节点是量节点,都是这样,那第四,每个红色节点必须有两个黑色的节点,这就比较有意思,意思也就是说,从每个叶子到根的所有路径上,不能有两个连续的红色节点,就不能这个红色节点,然后后面又跟着红色节点,然后第五条从任意节点到其每个叶子节点的所有简单路径,也就是最短路径,都包含相同数目的黑色节点,那下面就是一个具体的红黑树的图例,这里五条性质,那如果看完这五条性质以后,然后明天早上还能记起来的话,我只能说牛逼,因为这些规则,看起来太学术了,那这是红黑树的定义,没错,但是红黑树为什么会有这样的定义呢,那这五条定义看起来就像是有人在问什么是电脑,然后你回答,电脑也就是计算机,是由运算器,控制器,存储器,输入设备,输入设备五个部分组成的,那完全正确,但是对于我们理解电脑是个什么东西并没什么卵用,我们想知道什么是电脑,其实并不是想知道它是什么定义,知道他为什么需要这五个部分组成,对我们理解更有帮助,如果你去网上搜索什么是红黑树,那会看到有非常多的文章是这样来告诉你什么是红黑树的,第一步,写上来给你看位数的定义,第二步,然后举几个红位数增删节点的案例,比如说一颗原本是满足这些定义的红黑树,然后但是呢,在插入或者删除之后也不满足红黑树的定义啦,这时候就要进行一些调整颜色节点或者树的结构的操作,最后啊,在文章结尾总结一下红黑树增删的几种情况,并且说明红黑树的时间复杂度来做结尾,这些文章呢,完全正确,看完后你可能也觉得,他很牛逼,那红衣术都讲得头头是道,但是啊,就我个人来说,中博客我大概是看十次忘十次,等下次给我提到红艺术,我就只能记起几个比较炫酷的名词,左旋,右旋,还有lo Ken,那14看完以后呢,我还是不知道红黑树是如何搞出这一个看起来近乎神奇的定义,只要满足了这几个定义,就能让一棵树保持平衡,那换句话说,我都忍不住想去知乎上去提问一下,红黑树是怎么想到的问号,好这里正好有一个,我点开一下,这里有个人提问,红艺术是怎么想到的,看AV l树尚可理解,左右指数深度差不能超过一数,较为平均,搜索复杂度是o log and底数为二,但是从AV l树倒红黑树就很难理解啦,红黑树是在AV l树之基础上更进一步吗,这是个提问,那似乎洪卫戍并没有提到,似乎红黑树没有题深度差的要求,那一堆红黑集体的规则我怎么也记不住,更谈不上理解啦,请问红黑树是在什么情况下提出来的,用于解决哪些问题呢,不要给我一对红色的规则讲解,那些讲解总是讲规则复杂度,可是到底是要解决什么问题呢,如果需要避免二叉树退化成为列表,搜索复杂度变为o log n AV l树已经解决这个问题了,然后他下面说有朋友提到了二三十个二三次数,确实啊,这两种树的定义都很好懂,那什么时候用这两种树呢,适合用来解决什么问题呢,前面的这些问题,我猜,去学过红黑树的人可能都会有这个类似的疑问在后面,他还提到二三数合234数,这个可能很多人没有听说过呢,我们先往下面看,首先这里有个答主,她回答了这个问题,红黑树是在AV l树之基础上更进一步吗,他回答道,红黑树与acl没多大关系,红黑树并不是以AI为基础,没想到吧,红黑树和FL其实没什么关系的,别以为我们前面先提到了平衡二叉树,就觉得红黑树和他有关系啦,后面呢,他,提到这个问题,请问红黑树究竟是在什么情况下提出来的,用于解决哪些问题呢,大家回答的,某种意义上可以说是为了解决FL插入删除操作与查询操作收支不平衡的问题,A2为了保证查询效率、速度而付出了较大维护代价,而有些时候插入删除多余查询,我们就可以牺牲查询的速度而较快的完成插入删除