Huffman树、二叉排序树.ppt

文档介绍：Huffman树、二叉排序树
胡俊峰 2016/04/8
2
今天的内容
Huffman树
二叉排序树简介
3
建立n个元素的堆?
从0开始,不断插入堆:O(nlogn)
4
有没有更好(高效率)的方法?
0
1
2
3
4
5
6
7
8
9
10
11
5
哈夫曼树及其应用
哈夫曼树
哈夫曼算法
哈夫曼编码
6
Huffman树与最优编码
信息与编码
扩充二叉树与最优编码
Huffman树
7
扩充二叉树的概念
把原二叉树的结点都变为度数为2的分支结点
如果原结点的度数为2,则不变
度数为1,则增加一个分支,
度数为0(树叶),则增加两个分支。
空二叉树的扩充二叉树规定为只有一个外部结点组成的二叉树。
德
智
5
体
7
70
18
内部节点
Y
N
Y
Y
N
N
100
8
概率加权、前缀编码、加权平衡二叉树
wi是第i个外部结点的权值
li为从根到第i个外部结点的路径长度
m为外部结点的个数。
WPL = 1 x 5 + 2 x 70 + 3 x 18 + 3 x 7
= 5 + 140 + 54 + 21 = 220
德
智
5
体
7
70
18
内部节点
Y
N
Y
Y
N
N
100
外部路径
1
0
0
0
1
1
9
外部路径与加权外部路径
“外部路径长度” E:在扩充的二叉树里从根到每个外部结点的路径长度之和。
其中,li为从根到第i个外部结点的路径长度,m为外部结点的个数。
设扩充二叉树具有m个带权值的外部结点,那么从根结点到各个外部结点的路径长度与相应结点权值的乘积的和,叫做扩充二叉树的带权的外部路径长度。
其中,wi是第i个外部结点的权值,li为从根到第i个外部结点的路径长度,m为外部结点的个数。
10
哈夫曼树:
对于一组非负实数{w1 , w2 , w3 ,…, wm},存在一棵以wi(i = 1,2,…,m)为权的m个外部结点的扩充的二叉树,使得带权的外部路径长度WPL最小。这棵二叉树就称为哈夫曼树或最优二叉树。
WPL = 1 x 70 + 2 x 18 + 3 x 5 + 3 x 7
= 70 + 36 + 15 +21 = 142
智
体
70
德
7
18
5
内部节点
Y
N
Y
Y
N
N
100