408数据结构学习笔记——树与二叉树的应用——哈夫曼树和哈夫曼编码、并查集

简介: 408数据结构学习笔记——树与二叉树的应用——哈夫曼树和哈夫曼编码、并查集

1.哈夫曼树和哈夫曼编码

1.1.哈夫曼树的定义

权值:树的结点带有的某种意义的数值

带权路径长度:从树的跟该结点的路径长度(经过的边数与该点的权值的乘积

树的带权路径长度(WPL):所有叶结点的带权路径长度之和(算法题考过)

66308140907d46c4a72ca4f7ee405deb.png哈夫曼树:n个结点形成的所有二叉树中,wpl值最低的树(也称为最优二叉树)

1.2.哈夫曼树的构造

  1. 找到当前权值最低的两个结点,形成一个新的树,其根节点权值为两点之和
  2. 在森林中将两个结点删除,并将该树加入。
  3. 循环进行1、2,直到森林中仅有一棵树为止

6320e1a77d264759a8bee685b26faa5a.png

  1. cd结点权值最低,形成新的结点
  2. b(cd)结点权值最低,形成新的结点
  3. a(b(cd))权值最低,形成新的结点

1.3.哈夫曼树的性质

  1. 哈夫曼树不唯一
  2. 权值越小的结点路径长度越大
  3. 哈夫曼树的结点总数为2n - 1
  1. 哈夫曼树构造前,结点总数为n
  2. 构造哈夫曼树需要执行n - 1次合并,每次合并新增一个结点,即新增n - 1个结点
  3. n + n - 1 = 2n - 1
  1. 哈夫曼树不存在度为1的点(要么为0(叶子结点),要么为2(分支节点))

1.4.哈夫曼编码

前缀编码:没有一个编码是另一个编码的前缀

f5281caa54d8484f84dc38f8c42a13ad.png

由哈夫曼树构造哈夫曼编码,0向左子树,1向右子树(01指向左还是右没有明确规定)

哈夫曼编码的作用是可以不采用固定长度编码方式,从而压缩数据

2.并查集

2.1.并查集的基本操作

并查集:将元素划分为若干个互不相干的子集

并:将两个集合归并为一个集合(让一个树成为另一个树的子树)

查:确定一个指定元素的集合(查看其根节点是哪一个)

采用双亲表示法:并和查仅需更改或查看指向其双亲结点的伪指针

1.初始化:将每个结点的值设置为-1,表示每个结点都是一颗单独的树,即n个子集

99d7ab75e7a74f19863a794e4f8f89c4.png

#define MAXSIZE 100
int UFsets[MAXSIZE];    //集合数组
//初始化并查集
void Initial(int S[]){
    //-1表示集合中(森林)每个元素都是独立的个体(树)
    for (int i = 0; i < MAXSIZE; i++) S[i] = -1;
}

2.查(最坏O(n)):找该结点的根节点

并(O(1)):①两个结点是根节点:直接修改root2的值为root1的下标

②两个结点是非根节点:通过查操作,分别找到root1和root2的根节点,然后将root2的根节点的值为root1的根节点的下标

//查找,传入数组和数组下标
int Find(int S[], int x){
    //循环遍历查找其根节点,根节点的值为-1
    while(S[x] >= 0) x = S[x];
    return x;
}
//并,两个集合合并为一个
void Union(int S[], int root1, int root2){
    //两个元素是同一个集合
    if (root1 == root2) return;
    //将root2的根节点改为root1
    S[root2] = root1;
}

2.2.并查集的Union操作的优化(小树合并到大树)

1.如果每次都是大树合并到小树,则树的高度每次都会 + 1,导致并查集的使用效率降低→find最坏时间复杂度O(n)

2.每次都让让小树合并到大树,可以延缓树的增高→find最坏时间复杂度O(log n)

优化:根节点的数据的绝对值等于其结点总数,结点总数更大的树为大树,将更小的树并入大树

//并优化
void Union(int S[], int root1, int root2){
    //root1的树结点更多,相较下root2为大树
    if (root1 < root2){
        S[root1] += S[root2];    //root1的结点数更新
        S[root2] = root1;    //root2并入root1
    }
    else{    //root2为大树
        S[root2] += S[root1];    //root2的结点数更新
        S[root1] = root2;    //root1并入root2
    }
}

根节点代表的是该树的总结点个数,因此合并时,可以通过两个树根节点的值相加的方式得到合并后的树的总结点个数

39fa7021fa7b4bd18da566c1213cef62.png

2.3.并查集的Find操作的优化(压缩路径)

第一轮循环:和之前find操作一样,找到该结点的根节点

第二轮循环:将该结点find操作经历的每个结点挂到根节点上(修改路径上每个结点的值为根节点的下标)

find操作可以进一步优化为O(α(n)) << O(log n)α(n)通常为常数级

fb1d7a265c2345059644ec1bb4270b86.png

int Find(int S[], int x){
    int root = x;
    //向上循环遍历树,找到其根节点
    while(S[root] >= 0) root = S[root];
    while (x != root){
        int temp = S[x];
        S[x] = root;    //将x的双亲结点改为root
        x = temp;
    }
    return root;
}

3.王道课后题e5f4708cbb24421481f086fe555f607b.png

1.(AB)CDEF→((AB)C)EF→((AB)C)(DE)F→(((AB)C)(DE))F→((((AB)C)(DE))F)

  1. 最坏情况下,两个表的元素是交错的,即m1<n1<m2<n2....<m<n,除了最后一个元素不用比较以外,所有元素都要比较一次
  2. 第一次合并:10 + 35 -1 = 44
  3. 第二次合并:45 + 40 - 1 = 84
  4. 第三次合并:50 + 60 - 1 = 109
  5. 第四次合并:110 + 85 - 1 = 194
  6. 第五次合并:195 + 200 - 1 = 394

2..每次找当前最少的两个表合并成为一个新表

ceb526c2cb7243288ba3258df3557a79.png

  1. 二叉树
  2.   a.遍历当前字符集的每个字符

         b.如果当前扫描到的字符为0,则进入其左子树;如果当前扫描到的字符为1,则进入其右子树,直到碰到叶子结点,取出叶子结点所存储的数据

  1. 扫描字符集

      1.如果在还没有遍历完当前字符集时就到了叶子结点,则不具有前缀特性

       2.如果在遍历完当前字符集,并没有创建新的结点,则不具有前缀特性

       3.1和2都没有发生,则具有前缀特性






相关文章
|
13天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
25 1
|
18天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
|
3天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
29 8
|
11天前
|
机器学习/深度学习 存储 人工智能
数据结构在实际开发中的广泛应用
【10月更文挑战第20天】数据结构是软件开发的基础,它们贯穿于各种应用场景中,为解决实际问题提供了有力的支持。不同的数据结构具有不同的特点和优势,开发者需要根据具体需求选择合适的数据结构,以实现高效、可靠的程序设计。
28 7
|
25天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
4天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
52 9
|
21小时前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
2天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
21 4
|
26天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
26 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
7天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!