00:00
同学们,我们继续学习数据结构和算法的下一个内容。什么呢?平衡二叉树。那平衡二叉树呢?又叫AV l树。那么为什么会有平衡二叉数这种这种类型的数出现呢?我们还是看一个实际的案例,这个案例呢可以说明二叉排序数它可能存在的一个问题,你比如说现在我给大家一个数列是123456这个。很好理解,123456,那么现在我要求大家创建一棵二叉排序树,同学们想,如果说按照给出的这个数列,我们来产生一棵二叉排序树,它应该长成什么样子,是不是?长成这个样子的。大家看是不是因为因为你在加入的时候,它总是要满足二叉排序数的要求,那你新加的这个节点,它总是在原先那个节点的右边。
01:01
你有没有发现这个数列形成的一棵二叉排序树更像是一个单链表?更像是一个单链表,当然了,对于对于这样来说呢,它的插入速度和删除速度应该没有影响,但是它的查询速度其实就很慢了。对不对,也就是说他根本就不可能发挥二叉排序数它的一个优势,甚至他的查询比单链表还要慢,为什么呢?因为他在进行这个检索的时候,他还要判断它的左指数是不是为空,每次都有个判断。所以说我们发现当有这样的数列的时候呢,我们这个二叉排序数是有问题的,也就是我这边给他分析的,我总结了一下。左指数全部为空。从形式上看呢?大家看到左边这一个更像一个单链表,插入速度呢,没有影响,因为它仍是链表的形式,但是查询速度明显降低,因为需要依次比较,不能发挥我们BST它的一个优势,因为每次还要比较左指数,因此查询速度甚至比单链表还慢。
02:10
那么解决方案是什么?各位朋友,显然我们提出这个问题就是要引出平衡二叉素,所以说在这种情况下呢,我们需要使用的是平衡二项素,实际上就是原对我们二叉排序数的一种升级,或者叫优化。明白我的意思吧,那么下面呢,我们就来看一下何为平衡二叉树。什么是平衡二叉数呢?我这里总结了三点。啊,没有讲那么复杂,咱们就把最核心的讲出来就行了。平衡二叉数呢,又叫平衡二叉搜索数,说白了就是在二叉搜索数或者叫二叉排序基础上优化,他们又被称为什么呢?AV l数,以保证查询效率较高。那么平衡二叉树它有什么特点呢?大家看它有这个定义很重要啊,它是一棵空树,或者它的左右两个指数的高度的绝对值不超过一,就说你左边的左指数可以比右指数高,或者右指数可以比左指左指数的高度高,但是绝对值不能超过一。
03:15
那就说你不能出现这样一棵树,左子树噼里啪啦的往下面一直走,但是呢,到了右子树这边呢,诶只有一棵,那这个就没有意义了,其实它就相当单链表了,对不对?所以这个要求是第一个,第二个要求左右两个指数又又都是一棵平衡二叉树。好,这一点是要求的,那有了这样一个要求,其实就能保证我们这棵二叉树的效率,那平衡二叉树实现的方法呢,比较多,有红黑素这种算法,有AV l,注意啊,这里写的AV l指的是算法,不是指的AV l素,它是一种算法,替罪杨树最补伸展术这样一些方法来实现。
04:00
那么我们来看一下,下面我画了三个三个图形,大家觉得哪个是AV数,为什么?大家先先看上一分钟。好了,大家看完一分钟过后呢,我们来一起聊一聊这个视频大家可以看。对于这个顶点而言,对于这个顶点而言,它的左指数的高度,它的这个左指数,我这个它的这个左指数高度为二,它的右指数高度为一,因此呢,它的差值。它的这个高度的绝绝对差,差值的绝对值不超过一。因此它是。就是第一棵树就是avr树,这棵树是不是呢?也是你看对于这个顶点而言,它的左子树的高度为二,它的右子树的高度也为二,虽然它这边这这棵它的柚子树没有右右节点没有,但是不影响,也就说这棵树呢。这边的左指数高度为二,它的右指数的高度也为二,这样一相减等于零,因此它也是一棵AV l树。
05:05
A,压树啊,当然你这前提这边还是这边还是一颗。质平衡二叉树啊。这点这点要明,也就是说平衡二叉树它的前提是他首先是一棵二叉排序树,明白我的意思吧,你不能说你噼里啪啦我就违反了二叉排序数来,他是在二叉排序数的基础上来实现的,明白。好,这棵也是,我们再看这一棵,是不是呢?这棵就不是了,大家看这棵树呢,它的左子树的高度为几啊?是三,它的柚子树的高度为几呢?为一,三减去一等于二,显然它已然超过了几,超过了一,所以说从这边来看呢,第一棵树。这棵树是,这棵树也是,这棵树不是好的,我再说一遍啊,我我这只是画了一个高度,实际上他人忍这棵树的它的左子节点和右子节点以及顶点的关系仍要仍然要满足是一个二叉搜索数,或者叫做二叉排序数,明白。
06:07
好,那这个就是给同学们介绍的平衡二叉树的概念。那下面自然就是到了我们代码实现部分,我们要用代码来实现。平衡二叉树。怎么实现呢?我们下一个章节为大家讲解。
我来说两句