00:00
各位同学,我们继续来讲解数结构的实际应用的下个点,那下一个呢,要给大家讲的叫做赫夫曼数,我们先对赫夫曼数做一个基本的介绍。呃,什么是赫夫曼树呢?我们先来看一下啊,给定N个全值作为N个叶子节点,也也就是说你现在这一棵树呢,有N个叶子节点,而且每个叶子节节点呢,都会有全值,就说有值。那么构造一棵二叉树。如果这这棵树。它的带全路径长度数这边有个概念叫做数的带全路径长度,也叫WPLL,这个WPL是什么呢?Sweeted的pass这个英文单词后边呢,我们还要说这个数的带全路径长度是什么意思,大家先知道啊,也就是说如果你的这棵树的带全路径长度达到了最小。
01:03
那么这样的二叉树呢,我们就称之为最优二叉树,也叫哈夫曼树,刚才大家看到因为这个哈,这个英文呢是。我们这个作者翻译过来的,所以说有些书上呢,翻译的是赫夫曼,有些书上翻译的是哈夫曼,这个都没有什么问题,好吧,也说大家知道这个事儿就行了,还有还有的书翻译翻译成这个赫,赫元甲的赫也叫赫夫曼数。那么赫夫曼树是带权路径长度最短的树,全子较大的节点呢?它是离根最近,就说越是全值较大的这个节点,它离根节点就越近,这样才能导致这个WPL这个值是最小的。好,这是它的一个基本说明,那下面呢,这样讲肯定大家还是不太知道赫夫曼数是什么,对吧?下面我给他举几个例子,大家就比较形象的知道了,大家看这里。
02:02
关于这个赫夫曼数呢,还有几个重要的概念给各位朋友说一下。呃,第一个概念就是就叫路径,第二个概念就是路径的长度。这两个概念一定要搞清楚。什么叫做路径呢?注意听啊,在一棵树中。从一个节点往下可以达到的孩子或者是孙子节点的通路,我们称之为路径。明白意思吧。那么通路中分支的数目称之为路径的长度。那么若规定根节点的层数为一,比如这个根节点是一,那么这个就是二,就是第三层好不好?那么则从根节点到DL乘节点的路径长度就是L减一。你比如说。这个这个是根节点,我这有个13这个节点,那么从根节点到13这个节点路径的长度就是几呢?就是三减掉一个一等于二。
03:02
明白意思吧,就是路径的长度嘛,路径的长度。就是分支中数目,数目分支中数目成为路径的长度。对,那就是二。那就是二好,这个地方大家要知道啊,路径程度。那下面呢,我们再来看节点的权。节点的权及带权路径的长度。带权路径的长度,那么如果我们将数中节点赋给一个有有着某种含义的数值。那么这个数值呢,就称之为节点的全,你比如说假说这个节点,我们给它赋了一个值是13。OK,那么它的这个权就是13。这里面就又新出了一个概念,叫做节点的带权路径的长度。节点的带权路径的长度什么意思呢?就是说从根节点到该节点之间的路径长度与该节点的全的乘积,你比如说这个节点,这个节点它的全是13,那么它的路径的长度是多少呢?我们刚才算到它从这过来路径有两个,所以说这样呢就应该乘以二。
04:19
所以说呃,如果针对这一个节点而言。那么这个节点的带权路径呢,就是26。明白意思吧,也就是说节点的权和带权。路径的长度就是这个意思,就这个是节点的全是13,那么这个节点的带权路径的长度是什么呢?就是它的这个全去乘以它的这个路径长度,那路径长度刚才讲过了,路径长度是这样算的,就是如果从根节点算的话,DL层节点的路径长度就是。L减去1L代表成就一共有多少层,那就这样算下来的,明白好这样子,如果如果清楚了,过后我们再看。
05:02
下面几个案例大家就更加的清晰了,现在呢,我们要给大家说一下路的带权路径的长度,注意听啊。路的带线路径长度就是刚才我们讲的PWPL。大家还记不记得我们刚才说的,一,如果树的带圈路径长度最小,它其实就是一棵最优二叉树,也叫赫弗曼树,明白吧?那么数的带圈路径长度,它规定是什么呢?所有的叶子节点的带全路径长度之和即为WPL,也叫YT的pass全值越大的节点呢,离根节点越近,这个二叉树才会成为一个2U最优二叉树。好,那么我们可以看到,我们下面举几个例子看我假如现在有四个叶子节点。十三七八三,假如我这样构建。我这样构建,那么我这样构建过后呢?WP等于什么呢?等于13乘以二,因为13是全值,这个二是这个节点的路径长度,就是13乘以二,那么七呢,是七乘以二,八呢?八这个节点的带权路径长度是多少呢?是八乘以二,三这个节点的带全路径的长度是多少呢?是三乘以二,那整个所有节点的带全径长度之和就是WPL等于62。
06:23
那我也可以这样构建。大家看,如果我这样构建的话呢,13这个节点的带全路径长度就是13乘以一,因为它的长度是,呃,路径长度只有一嘛,那么八呢就是八乘以二,七就是七乘以三,看啊123过来了,那么三呢,三就是123也是三,这样算下来WP2就是59,大家可以看到59就小于62。那我还可以这样构建。这样构建,大家看这样构建,七的这个节点的带权路径长度就是七乘以1343乘以2848乘以33 43乘以三,那这个就是76,大家有没有发现?
07:01
大家有没有发现,其实这里面最优二叉树,呃,最优二叉树也就是赫夫曼树,其实就是这棵树。因为这棵树呢,它是全值是最小的。而且大家有没有发现,它把这个圈子最大的节点释放在离根节点最近的这一层?其他意思类推。其他以此类推。OK,那有时候你一定要保证你给的这些节点都是叶子节点,明白吧,你不能说,诶我把这个点放在非叶子节点,那那就不是我们所说的赫方赫夫曼书了,好,同学们,那关于赫夫曼苏这个概念,大家看看理解了没有,其实就是一句话。别人问你什么是赫夫曼数,你就告诉他是什么数呢?就是WPL,最小的二叉树就是赫夫曼树。就这么简单好吧,好,那口位同学关于赫夫曼数这个概念呢,先给同学们讲解到这里。
我来说两句