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，其不仅先要按值满足二叉查找树的结构，而需要按优先级满足堆的结构，因为优先级是随机的，所以在构成堆的时候，会随机的调整二叉树的结构，使其不致于完全失衡。
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扫ky]()
vc=" src="/uploadfile/Collfiles/20161004/20161004090000185.png" />
对于一个vEB树其根结点为T，根结点的范围为{0, …, M1}，则根结点的子结点范围为√M。子结点的数目为√M，因此对于子结点[i] 其说，其子结点（T的孙子结点）为{i√M, …, (i+1)√M1}。
另外每个结点还保留两个属性：最小值和最大值。
13.5 多路归并-败者树
对于外部排序中的多路归并操作来说，对于k路平衡的归并排序，每一次归并操作都需要从k路中找到最小值，当增大k的值可以减少磁盘读写的次数，但增大k的值也会使合并的时候会增加算法复杂度。这个时候我们引入了败者树。
在败者树中，父结点记录其左右子结点进行比赛的败者（即归并时的较大值为败者），而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。
如上图所示：方框中{b0,b1,b2,b3,b4}表示待记录的结点，圆框表示一次比赛的败者，败者结点上面的数字表示胜者
使用败者树来加快合并排序，可以在O(logk)的复杂度下找到最小数，当然也可以用最小堆来达到相似的效果？。
13.6 字典树
字典树又名单词查找树（Trie树），主要是利用字母作为结点，而查找单词的过程就是搜索路径的过程，其经常被用于文本词频统计。其利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高，在面试的时候，凡是字符串的快速查找都离不开这个结构，这个结构非常简单。
