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

你将获得

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

教学服务

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

讲师介绍

老师头像

高杰

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

课程详情

大家都在问

想了解高级开发课

294人在问去咨询

想了解Compose

294人在问去咨询

怎么加入技术交流群?

294人在问去咨询

知识星球是什么?

294人在问去咨询

二叉树和平衡二叉树 - 高杰视频文稿

那红黑树这个东西,我相信大多数Android开发是从JAVA8的hash map这里了解到的,那么为什么Java的hash map要在原来的数组加列表的时间上进一步优化,这个列表长度超过八的时候会将列表转化为红黑树呢,那很简单,那就是效率的原因,我们来看一下这个常见的数据结构的操作时间复杂度这个列表,这地方这这个列表呢,它的查询是简朴,大多是o on,那红黑树呢,红黑树,它长与时间复杂度是o lo Ken,一个o一个o log,如果当列表长度还不是特别长的时候,那么这个o an其实也没有很慢,但是当列表长度变长了以后呢,这个o lo Ken就会和她的OL拉开差距了,所以在列表长度达到条件的时候,我们需要将列表转换为红黑树,那么为什么是要红黑树而不是普通的二叉树呢,我们看这个二叉树,他的查询时间复杂度也是o lock and,这又是为什么呢,其实啊,也很简单,这个二叉树的查询时间复杂度是o lo Ken,这是在二叉树在一般情况下的时间复杂度,如果是最坏的情况呢,那么他的查询时间复杂度就变成了OL啦,那最坏的情况下是OMG,那这不就和列表是一样的吗,那其实,画个图就很容易明白了,当我们插入的数据是这种情况9532,我们把这个插入到二叉树中会变成一个什么东西呢,那可以看到这是一个二叉树,但是他表现得起来和列表其实没什么两样,在这种最坏的情况下,每次添加元素都在最左侧创建一个新的子节点,那他的查询时间复杂度on是不是就很容易理解啦,那么有什么办法可以避免二叉树产生这种最坏的情况呢,先抛开红黑树,我们来看一下另外一个有很多节点的普通二叉树,这个二叉树呢,不像刚刚退化成列表的那个树一样,即使元素有30多个,那树的高度或者说深度,也就是说,根结点到子节点的最远距离也是只有五层呢,那么我要查找这个数中的任意元素,我通过二分法最多寻找五次就可以确定啦,那不难看出来,一棵大树查找树的效率和树的高度是有关系的,那从这一点出发呢,如果我们能通过某种手段来控制树的高度,而这个平衡二叉树,他呢,就通过控制树的高度来保证一棵二叉树不会退化成列表,这样呢,在最坏情况下也能保持o log en的查询时间复杂度啦,那么这个平衡二叉树是如何控制这个树的高度呢,我们来看一下平衡二叉树再添加这种数据的时候的处理方案,那可以看到我们第三个元素四倍添加到第二个结点的左子节点中的时候,这个整个二叉树的平衡被破坏了,当然这个平衡被破坏不能依靠我们肉眼来看,平衡二叉树是通过节点的左右两个子树的高度差来判断的,现在这个根节点的左子树高度是二,右子树高度是零,那只要这个差值大于了一,注意,是大于一,而不是有高度差就认为不平衡啦,那高度差是一的时候,也就是说刚添加第二个节点的时候,这种情况,那这个平衡二叉树还是认为他是处于平衡状态的,绕远了,前面我们说过,左右指数的高度差超过了一,那就说明这棵树他不平衡啦,那不平衡怎么办呢,这时候我们就要采取手段让整棵树恢复平衡啦,那这个手段就是,旋转,我们通过旋转的操作,将元素久从原本是元素六的父节点变成了现在是元素六的右子节点,那这个旋转的操作看起来很简单,就是因为原本这个场景就很简单,因为只有这三个元素,那我们来看另外一个元素多一些的平衡二叉树,那这棵平衡二叉树呢,他目前还是处于一个平衡的状态,那根结点的左指数高度是一二是二,幼指数高度是一,高度X2减一没有超过一,那说明处于平衡的状态,但是当我们把一个新的这个元素二插入到术中,这时候整棵树就会变成这个样子,那现在这棵树的平衡就被破坏了,所以我们需要进行旋转的操作,我们把元素五变成元素九的父节点,那元素九变成元素五的右子节点,这时候你会发现,出问题啦,这个元素五怎么有三个字节点啦,这该怎么办,其实很简单,让这个元素六插入到元素灸的着指数里面就可以了,那为什么一定是插入到原宿酒的左子树而不是右子树或者别的什么地方呢,这个看旋转操作前的数就明白了,这个六步可能会比元素九还要大的,这就是平衡二叉树的旋转操作,当然针对我们这种往左指数左结点插入元素的情况,我们需要的是这种旋转,也有人叫做它又全