数据结构与算法（python版）-- 04 二叉树续

哈夫曼树

• 思想：使权值比重大的节点最靠近树根；权值越小越远离树根；
• 二叉树中叶子节点的带权路径为 权重w i ∗ l i {w_i * l_i}wi​∗li​，l i {l_i}li​为根到叶子的路径长度，w i {w_i}wi​为叶子节点的比例（权重）；
• 树的带权路径长度 = 所有叶子节点的带权路径长度和；
• 有n个叶子节点的二叉树中，带权路径长度最小的二叉树，为哈夫曼树， 是一种最优的二叉树；
• 哈夫曼树不是唯一的，但树WPL 【带权路径长度】是唯一的；
  

• 哈夫曼树的构建步骤

  • 以每个权值创建只有一个根节点的二叉树，形成二叉树森林，并按照树根权值升序排序；

  • 在该森林中，每次取根节点权值最小的两棵树，合并成一棵新树，新树根的权值为左右子树（根）权值之和；

  • 从森林中删除使用过的旧树，添加新树，并重新排序；

  • 重复以上步骤，直到森林中只剩一棵树停止；

  • 利用如下权值，构造一棵哈夫曼树：
    
    

  • 哈夫曼树没有度为1的节点（即都是度为0或2）；

  • 哈夫曼树 优化 if 分支的比较次数， if 条件先走比例最大的情况，elif 条件走剩余部分中比例最大的情况，依次处理；
    

编程实现哈夫曼树

• 节点结构：数据、左子树指针、右子树指针,父节点指针；
• 构建以【7，5，2，4】为权值的哈夫曼树；
  • 以每个权值的叶子节点为根，构建只有根的二叉树，放入列表；
  • 列表升序排序（以根节点权值升序），并取出（根节点）权值最小的两棵树，分别为左右子树，新的根节点权值为左右子树权值之和；
  • 新的二叉树放入列表中，并重新排序（以根节点权值升序），并重复步骤2；直到列表中只有一棵树为止。

classNode:def__init__(self,data,left=None,right=None,height=1,parent=None):self.data=data self.left=left self.right=right# 可以加入统计树高self.height=height self.parent=parentdefbuild_huffman(alist):# 初始化只有一个根的二叉树的森林forest=[Node(v)forvinalist]whilelen(forest)>1:# 升序排序forest.sort(key=lambdai:i.data)left=forest.pop(0)right=forest.pop(0)# 合并树root_data=left.data+right.data root=Node(root_data)root.left=left root.right=right root.height+=max(left.height,right.height)left.parent=root right.parent=root# 新树入森林forest.append(root)returnforest[0]defpreorder_travel(root):ifrootisNone:returnprint(root.data,end=" ")preorder_travel(root.left)preorder_travel(root.right)# 中序inorder# 后序postorderif__name__=='__main__':weights=[7,5,2,4]root=build_huffman(weights)preorder_travel(root)# 先序遍历：18 7 11 5 6 2 4

哈夫曼编码

• 编码，将字符信息转为0/1二进制串；
• 为节约传输时间，使编码的二进制串尽可能短；-> 非等长编码
• 任何字符的编码不能是其他编码的前缀，保证解码的唯一性；
• 哈夫曼编码
  • 统计每个字符的概率，作为权重；
  • 按照权重，构建哈夫曼树；
  • 左分支的路径符号为0，右分支路径符号为1；
  • 从根到叶子节点的路径符号连接，即为该叶子对应字符的编码；

例子

• 传输字符串为“ABCACCDAEAE”，每个字符概率为0.36、0.1、0.27、0.1、0.18，计算该字符串的哈夫曼编码结果。
• 思路
  • 统计字符概率作为权重；
  • 以权重构建哈夫曼树；
  • 左子树路径标记为0， 右子树路径标记为1；
  • 每个叶子对应的字符，编码结果为路径符号连接；

• 编程实现

classNode:def__init__(self,data,left=None,right=None,height=1,parent=None):self.data=data self.left=left self.right=right self.height=height self.parent=parent# 父节点defbuild_huffman(alist):# 初始化只有一个根的二叉树的森林forest=[Node(v)forvinalist]origin_leafs=forest.copy()whilelen(forest)>1:# 升序排序forest.sort(key=lambdai:i.data)left=forest.pop(0)right=forest.pop(0)# 合并树root_data=left.data+right.data root=Node(root_data)root.left=left root.right=right root.height+=max(left.height,right.height)left.parent=root right.parent=root# 新树入森林forest.append(root)returnforest[0],origin_leafsdefcount_weight(s):""" 统计每个字符的概率，概率越大，编码越短 """dict_={}n=len(s)forcins:ifcindict_:dict_[c]+=1else:dict_[c]=1char_list=[]weights=[]fork,vindict_.items():char_list.append(k)weights.append(round(v/n,3))returnchar_list,weightsdefhuffman_encode(leafs,root):num=len(leafs)# 每个叶子节点的编码node_encode=[""]*numforiinrange(num):node=leafs[i]whilenodeisnotroot:# 从叶子节点开始，向根节点查找ifnode.parent.leftisnode:node_encode[i]="0"+node_encode[i]else:node_encode[i]="1"+node_encode[i]node=node.parentreturnnode_encodeif__name__=='__main__':s="ABCACCDAEAE"char_list,weights=count_weight(s)print(char_list)print(weights)# 创建huffman树root,leafs=build_huffman(weights)preorder_travel(root)# 1.001 0.364 0.182 0.182 0.091 0.091 0.637 0.273 0.364# 获取每个叶子节点对应的符号的 编码result=huffman_encode(leafs,root)print("\n",result)# 字符 ['A', 'B', 'C', 'D', 'E']# 频数 [4, 1, 3, 1, 2] , 计算树的WPL 时使用频数计算；# 权重 [0.364, 0.091, 0.273, 0.091, 0.182]# 先序遍历1.001 0.364 0.182 0.182 0.091 0.091 0.637 0.273 0.364# 编码 ['11', '010', '10', '011', '00']

• 计算该huffman树的唯一WPL = 2 * 4 + 3 * 1 + 2 * 3 + 3*1 + 2 * 2 = 24， 即传输该字符串需要的总比特数；
• 每个字符的平均码长 =W P L 总字符数 \frac {WPL} {总字符数}总字符数WPL​=24 11 \frac {24} {11}1124​= 2.18
• 等长编码，即每个字符的编码bit 一样长，一个bit位可以表示2 1 2^121，x xx个bit位可以表示n个字符，2 x = n 2^x=n2x=n，则x = l o g 2 n x=log_2nx=log2​n向上取整；
• 压缩率（节省率） = (等长编码总位数 − 哈夫曼编码总位数) / 等长编码总位数 × 100%。
  

树的性质

• 除了根节点，每个节点都有一个前驱节点【一条边】，所以 n个节点的树中有n − 1 {n-1}n−1条边；
• 度为k的树中，第i层最多有k i − 1 {k^{i-1}}ki−1个节点
• 度为k的、高为h的树中，至多有( k h − 1 ) / ( k − 1 ) {(k^h - 1) /( k -1)}(kh−1)/(k−1)个节点；
• n个节点的度为k的树中，最小高度为l o g k ( n ∗ ( k − 1 ) + 1 ) {log_k(n*(k-1) + 1) }logk​(n∗(k−1)+1)向上取整
  

树的存储

• 双亲表示法，每个节点存储数据、父节点的编号（或地址），便于查找父节点；
• 孩子节点表示法，每个节点存储数据、孩子的编号（或地址），便于查找孩子节点；
• 数组+单链表，节点存储数据和链表的头节点，链表表示（从左到右的）孩子节点；
• 长子兄弟表示法，长子作为左子节点，兄弟作为右子节点；

树与二叉树的转换

• 每个树都可以转为唯一的二叉树；

• 基于左孩子右兄弟表示法；

• 树转为二叉树，二叉树的右子树一定为空；

  • 以树根为二叉树的根节点；
  • 最左侧孩子作为左子树，每个节点的右兄弟作为自己的右子树 【形成右链】；
  • 删除线，每个父节点只保留最左侧孩子的连线，删除与其他孩子的连线；
  • 加线，兄弟之间加右链线；
  • 递归处理每个孩子节点的转换【从左到右顺序】；
    

• 二叉树还原树；

  • 以二叉树的根为树根；
  • 二叉树的左孩子作为树的第一个最左侧的孩子，二叉树左孩子的右链中恢复树的其他孩子；
  • 删除原二叉树中双亲节点与右孩子的连线；
  • 递归处理二叉树中其他节点的转换【从左到右的顺序】；
    

森林与二叉树转换；

• 森林转为二叉树；

  • 将森林中的每棵树，转为唯一二叉树；
  • 将依次转换的每棵二叉树的根连线，形成右链，即后面的二叉树作为其前面的二叉树的右子树；
  • 以第一棵二叉树的根为整个二叉树的树根；
    

• 二叉树转为森林；

  • 将根节点与右孩子、右孩子的右孩子，… 之间的连线断开，形成多棵二叉树；
  • 每棵二叉树还原树，得到初始的森林；

  
  

B树

• B树是多路平衡查找树，是多叉树；

• 所有叶子节点在同一层，保证平衡；

• 叶子节点不存储信息，表示查找失败；

• 终端节点表示最后一排具有关键字的节点；

• 左子树的值都小于父节点中的值，父节点的值都小于右子树的值；

• B树的阶表示每个节点的子节点数中的最大值，一般设置为偶数；

• B树的键，表示每个节点中存储的数据个数；

• B树用于磁盘的存储、查询，如文件系统、数据库索引；

• m阶B树的性质：

  • 根节点至少一个键，至少两个子树，最多m个子树（m-1个键）；
  • 每个节点中的值升序 或者降序；
  • 除根以外的节点，至少m/2 【向上取整】棵子树，至多m棵子树（m阶）；
  • 除根以外的节点，至少m/2 - 1【向上取整】个键，至多m-1个键；
  • 所有叶子节点在同一层（保证平衡）；
  • 树矮，磁盘IO少，查询效率高；
  • 中序遍历有序性；
  • 计算如下B树的阶数（注意叶子节点没有画出）4阶
    

• m阶(如6阶)B树的插入:

  • 取一个待插入的值，若当前B树为空或仅有一个根节点，则直接插入根节点，否则就与根中的键比较大小，走进对应的子树节点中插入，并排序（一般升序，也可降序）；
  • 若插入后，当前节点键数超出上限（m-1），则触发分裂（否则本次插入完成），将中间的键值提取到父节点中，左边的键值形成左节点，右边的键值形成右节点；若父节点键值超限，则触发分裂，同样方式处理分裂；
  • 如下为1到17之间的序列数值构建的B树；
    

• m阶B树的查找，从根节点中，依次比较每个关键字，找到则结束，未找到 则在关键字区间内的子树中继续查找；若走到叶子节点，则查找失败；

• m阶(如6阶)B树的删除

  • 叶子节点的键删除后，若剩余关键字数量大于等于最小阈值，则结束；否则删除后【键个数不满足节点最少键数】，则向左右兄弟借，若向左兄弟借，则左兄弟最大键值进入父节点，父节点中被夹持的键值借给键不足的节点；当左右兄弟都不够借时，当前节点需要与左或右兄弟进行合并（先将父节点中被夹持的键值拉下来，在一起合并到兄弟节点中）
  • 非叶子节点的删除，将左边子树的最大值【前驱节点】或者右边子树的最小值【后驱节点】与待删除的值对换，然后在页节点中删除该值；删除键后不满足最小关键字数，则向兄弟节点借。
  • 如下为5阶B树，尝试删除键3、25；
    
    删除3【删除后向右兄弟借，父下来，兄上去】：
    
    删除25【叶子节点中直接删除】：
    

  删除 38 非叶子节点：
  

B树的python实现

pending

B+ 树

• B+树的根节点至少两个键，两个子树；
• m阶 B+树的非根非叶子节点的子树返回【m/2 上取整, m】，节点关键字与子树数量保持一致；
• 叶子节点存储数据，并且叶子之间存在链表关系；
• 非叶子节点中不存储数据，只存储导航信息【数据的索引】；

练习题

答案：

1. D, A
2. D
3. A
4. D
   

B树构建
基于如下的数据，以插入方式构建3阶B树，画出构建过程：
{15, 5, 20, 3, 10, 25, 8, 12, 18, 22, 28}
1.插入15，空树直接创建根节点；
2.插入5，只有一个根节点时直接插入根 [5 | 15]
3.插入20，[5 | 15 | 20] 关键字超限，触发分裂

4.插入3， 3 <15 则到关键字15的左侧子树中插入

5.插入10， [3 | 5 | 10] 触发分裂

6.插入25

7.插入8，8在5-15关键字之间，所以到这个区间下的子树中插入；

8.插入12，[8 | 10 | 12] 触发分裂，提取中间节点到父节点中，再次触发父节点的分裂；

9.插入18，[18 | 20 | 25]

10.插入22；

11.插入28，形成最终的B树：