怎么注销网站备案,wordpress 手册 插件,旅游网站建设那家好,嘉兴网站搜索排名5.5 树与二叉树的应用 概念 结点的权#xff1a;大小可以表示结点的重要性 结点的带权路径长度#xff1a;从树的根到该结#xff0c;的路径长度#xff08;经过的边数#xff09;与该结点权的乘积 树的带权路径长度#xff1a;树中所有叶结点的带权路径长度之和(WPL) …5.5 树与二叉树的应用 概念 结点的权大小可以表示结点的重要性 结点的带权路径长度从树的根到该结的路径长度经过的边数与该结点权的乘积 树的带权路径长度树中所有叶结点的带权路径长度之和(WPL) 哈夫曼树最优二叉树在含有n个带权叶结点的二叉树中其中带权路径长度(WPL) 最小的二叉树 编码方式 每个字符对应二进制长度分 固定长度编码每个字符对应相同长度的二进制编码 可变长度编码允许不同字符用不同长度的二进制编码 按是否有歧义分 解码无歧义前缀编码没有一个编码是另一个编码的前缀 解码有歧义非前缀码 哈夫曼编码利用构造哈夫曼树的方法得到哈夫曼编码左边0右边1 并查集 如何查到一个元素到底属于哪一个集合? ·指定元案出发一路向北找到根节点 如何断两个元素否属于同一个集合? ·分别查到两个元素的根判断根节点是否相同即可 如何把两个集合并为一个集合? ·让一棵树成为另一棵树的子树即可 采用双亲表示法存储并查集树的好处 容易向上溯源易于查 另一棵树的根指向目标树的根即可实现并易于并
理解 哈夫曼树的构造 并查集的实现 定义有n个元素则定义大小为n的数组根的值为-1其他结点值为根节点的下标 查操作往上溯源找到只为-1的根节点的下标最坏复杂度O[n] 并操作两个集合合并成一个把其中一个集合的根的值改成另一个根节点的下标即可复杂度O[1] 并操作的优化尽可能降低并查集的高度 修改复杂度为O[1]的并操作该方法使得构造的树高不超过log₂n向下取整1从而查操作的复杂度降到O[log₂n] 每次合并的时候让小树合并到大树的根下 根的值仍然取负值但是绝对值是该树的所有节点数目从而可以体现树的大小 查操作的优化压缩路径复杂度O[α(n)] 路径上经过的结点都直接挂到根节点下面 while循环向上溯源目的是找到根与优化前一样 再次while循环目的是把路上的结点都直接转接到根节点下面优化内容如果每个叶结点都经过这个操作那么原来的树的高度就变成了2一个根其他全是叶子
技巧 在有n个叶子结点的哈夫曼二叉树中非叶子结点一共有n-1个总共有2n-1个结点叶结点个数即为可编码的个数 哈夫曼编码不超过4已经编码两个1、01则最多还可以编码4个0000、0001、0010、0011 哈夫曼二叉树的度只有0和2两种情况 n个有序的序列和m个有序的序列合并最坏情况要比较mn-1次大小
