频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
【C++研发面试笔记】13. 基本数据结构-哈夫曼树、树堆及其他树簇
2016-10-05 08:56:00         来源:tostq的专栏  
收藏   我要投稿

13.1 哈夫曼树

哈夫曼又称最优二叉树,是一种带权路径长度最短的二叉树。

13.1.1 哈夫曼树的构造

假设有n个权值,则构造出的哈夫曼树有n个叶子节点.n个权值记为{w1,w2,w3…wn},哈夫曼树的构造过程为:

将w1,w2,w3…wn看成具有n棵树的森林,每棵树仅有一个节点。 从森林中,选取两棵根节点权值最小的树,两棵树分别作为左子树与右子树,构建一棵新树。新树的权值等于左右子树权值之和。 从森林中删除两棵权值最小的树,将构建完成后的新树加入森林中。 重复2、3步骤,直到森林只剩一棵树为止。这棵树便是哈夫曼树。

这里写图片描述

13.1.2 再看哈夫曼编码

将权值作为结点构建了哈夫曼树后,我们可以由如下规则获得它们的哈夫曼编码:
从根节点到每一个叶子节点的路径上,左分支记为0,右分支记为1(或者右分支为0,左分支为1),将这些0与1连起来即为叶子节点的哈夫曼编码。
哈夫曼编码


13.2 Treap树堆

二叉搜索树BST的主要问题就是其结构与数据相关,树的深度可能会很大(即出现了不平衡问题),前面我们已经知道了通过AVL树和红黑树能调整树的结构,使树不致于太过失衡。但是AVL树和红黑树调整树结构,不仅非常复杂还需要大量的旋转操作。
Treap树就是另一种解决二叉搜索树可能深度过大的数据结构,Treap=Tree+Heap,即Treap树就是树和堆的组合。
Treap本身是一棵二叉搜索树,它的左子树和右子树也分别是一个Treap,和一般的二叉搜索树不同的是,Treap还纪录一个额外的数据,就是优先级,而优先级是需要通过最大堆(最小堆)来维持的。即Treap在以关键码构成二叉搜索树的同时,还通过优先级来满足堆的性质。这些优先级是在结点插入时,随机赋予的,Treap根据这些优先级满足最大堆(最小堆)的性质。
Treap插入删除都非常简单直观,速度也不错,其插入和删除操作时间平均复杂度大概是log(n),很好地平衡了编码复杂度和时间效率。但由于优先级(优先级是个堆)是随机生成的,相较于RB-Tree来说,不够稳定,所以在实际应用中比较少见点。

13.2.1 Treap的结构

作为Treap,其不仅先要按值满足二叉查找树的结构,而需要按优先级满足堆的结构,因为优先级是随机的,所以在构成堆的时候,会随机的调整二叉树的结构,使其不致于完全失衡。
Treap的结构

13.2.2 Treap插入

先根据Key值以BST树的插入到合适位置
这里写图片描述 再根据随机优先级,来调整堆,这里只涉及到了两个旋转
这里写图片描述

13.2.3 Treap删除

由于Treap的删除有二叉树节点的删除方式,也可以像堆的删除方式。

用二叉搜索树的方式删除:先在BST中找到要删除的节点
该节点是叶节点,直接删除。 该节点只有一个非空子节点,将其子节点代替其位置,然后删除。 该节点有两个非空子节点。用它右子树的最小值或左子树的最大值来代替它,然后把它删除。 用堆的方式删除:类似于最大堆或最小堆的删除结点方式

13.3 可合并堆-斐波那契堆

有些时候,我们需要涉及到堆的合并,对于二叉堆来说,合并一组堆的非常复杂。为了方便合并堆,我们引入了可合并堆。斐波那契堆是一种可合并堆,其求最小值,插入,降低元素值,和合并操作可以在常数平摊时间O(1)内完成。删除和删除最小值也都 可以在O(log n)平摊时间内完成。
斐波那契堆是一组最小堆有序树集合,其中每一棵树(堆)都满足最小堆的属性,每一个斐波那契堆还维持一个最小值属性。因此,在优先队列中经常使用斐波那契堆来实现。
斐波那契堆

13.3.1 斐波那契堆的操作

插入新节点:将新的节点当做一棵新的树的根插入到根表中即可。 合并两个堆:主要分为两步:
将两个根表通过指针合并为一个根表 比较两个堆的min[H],取较小作为新min[H], 删除最小节点:
将被删除节点的每个孩子都看做新的堆中的一棵树的根,并加入到根表中
这里写图片描述 遍历根表,合并度数相同的树,并更新合并后所得树的度 直到所有树的度都不相同
这里写图片描述 减小结点的值:此时会破坏最小堆的性质:
如果最小堆性质被破坏,则将该结点直接从原来的树移除后,直接串联在根表中 如果节点的父节点没有失去过孩子,则结束 如果节点的父节点失去过孩子,将节点p当做被删除节点,将它从树中剪掉,移到根表中 重复上面的操作 删除结点:
找到要删除的结点 将该关键值减小为比最小值还小的值 删除最小结点点

13.4 线段树-van Emde Boas树

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。——百度百科

线段树
van Emde Boas树(又名泛峨眉大悲寺树⊙_⊙||,或者V树),其也是一种实现优先队列的方法,其可以在最坏情况下O(lglgN)实现查找、插入、删除、查找最值、合并、分裂等操作。不过种数据结构要求关键字必须为0~N-1的无重复的整数,且N=2^n。
vEB扫kyvc=" src="https://www.2cto.com/uploadfile/Collfiles/20161004/20161004090000185.png" />
对于一个vEB树其根结点为T,根结点的范围为{0, …, M?1},则根结点的子结点范围为√M。子结点的数目为√M,因此对于子结点[i] 其说,其子结点(T的孙子结点)为{i√M, …, (i+1)√M?1}。
另外每个结点还保留两个属性:最小值和最大值。


13.5 多路归并-败者树

对于外部排序中的多路归并操作来说,对于k路平衡的归并排序,每一次归并操作都需要从k路中找到最小值,当增大k的值可以减少磁盘读写的次数,但增大k的值也会使合并的时候会增加算法复杂度。这个时候我们引入了败者树。
在败者树中,父结点记录其左右子结点进行比赛的败者(即归并时的较大值为败者),而让胜者参加下一轮的比赛。败者树的根结点记录的是败者,需要加一个结点来记录整个比赛的胜利者。
这里写图片描述
如上图所示:方框中{b0,b1,b2,b3,b4}表示待记录的结点,圆框表示一次比赛的败者,败者结点上面的数字表示胜者
使用败者树来加快合并排序,可以在O(logk)的复杂度下找到最小数,当然也可以用最小堆来达到相似的效果?


13.6 字典树

字典树又名单词查找树(Trie树),主要是利用字母作为结点,而查找单词的过程就是搜索路径的过程,其经常被用于文本词频统计。其利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高,在面试的时候,凡是字符串的快速查找都离不开这个结构,这个结构非常简单。
字典树

点击复制链接 与好友分享!回本站首页
上一篇:【C++研发面试笔记】11. 基本数据结构-红黑树RBT
下一篇:C++研发面试笔记:基本数据结构-查找表与并查集
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站