1.赫夫曼树

1.1 赫夫曼树介绍

赫夫曼树百科链接 (opens in a new tab)

1.2 赫夫曼概念及理解

路径及路径长度

在一颗树中，从一个节点往下可以到达的孩子或孙子节点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根节点的层数为 1，则从根节点到第 L 层节点的路径长度为 L-1。

节点的权及带权路径长度

若将树中节点赋给一个有着某种含义的数值，则这个数值称为该节点的权。节点的带权路径长度为：从根节点到该节点之间的路径长度与该节点的权的乘积。

树的带权路径长度

树的带权路径长度规定为所有叶子节点的带权路径长度之和，记为 WPL。

权值越大的节点距离根节点越近的二叉树才是最优二叉树。

WPL 最小的就是赫夫曼树。

1.3 赫夫曼树示意图

2. 赫夫曼编码

2.1 赫夫曼编码介绍

赫夫曼编码百科链接 (opens in a new tab)

1. 赫夫曼编码是赫夫曼树在通讯中的经典应用案例。
2. 赫夫曼编码广泛应用于数据文件压缩，它的压缩率在 20%~90% 之间。

2.2 赫夫曼编码原理

2.2.1 通讯中----定长编码

例如：

• 字符串：

  Im hanguoqing.Whats your name

• ASCII:

  73 109 32 104 97 110 103 117 111 113 105 110 103 46

  87 104 97 116 115 32 121 111 117 114 32 110 97 109 101

• 二进制：

  01001001 01101101 00100000 01101000 01100001 01101110 01100111 01110101 01101111 01110001 01101001 01101110 01100111 00101110

  00100000 01010111 01101000 01100001 01110100 01110011 00100000 01111001 01101111 01110101 01110010 00100000 01101110 01100001 01101101 01100101

2.2.2 通讯中----变长编码

例如：

Im hanguoqing.Whats your name

g:1 q:1 i:1 W:1 s:1 y:1 r:1 e:1 I:1 m:2 h:2 u:2 o:2 a:3 n:3 :4

0=, 1=n, 11=a, 100=o, 101=u, 111=h, 1000=m, 1001=I, 1011=e ...

按照上面编码二进制应该是如下：

1001 1000 0 111...

2.2.3 通讯中----赫夫曼编码

Im hanguoqing.Whats your name

g:1 q:1 i:1 W:1 s:1 y:1 r:1 e:1 I:1 m:2 h:2 u:2 o:2 a:3 n:3 :4

按照上面字符出现的次数构建一颗赫夫曼树，次数作为权值

注意：

1. 根据赫夫曼树，规定前缀编码，向左的路径为 0，向右的路径为 1。
2. 前缀编码：设计长短不等的编码，必须是任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。
3. 如下，i:101 u:10010

处理完二进制字符串则是赫夫曼编码处理的。

3. 二叉排序树

使用数组：

1. 使用未排序数组可以直接将数组插入到数组尾端，速度快，但是查找慢
2. 使用排序号数组，查询比较快，但是插入新数据时，需要整体移动后，插入有效的位置，过程比较慢

使用链表:

链表特点是插入数据比较方便，但是查询数据比较慢

3.1 二叉排序树介绍

• 二叉排序树(Binary Sort Tree)，又称二叉查找树(Binary Search Tree)，亦称二叉搜索树。
• 是数据结构中的一类。
• 如果有相同的值，可以将该节点放在左子节点和右节点上。

同一集数据对应的二叉排序树不唯一。但经过中序遍历得到的关键码序列都是一个递增序列。

4. 多路查找树

4.1 二叉树和 B 树

4.1.1 二叉树问题分析

二叉树操作数据效率比较高，但是如果细心想下它也存在着一定的问题：

1. 二叉树需要加载到内存中，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如 10 亿)，就存在问题了。
2. 在构建二叉树时，需要多次进行 IO 操作(海量数据存在数据库或文件中)，节点海量，构建二叉树时，速度有影响。
3. 节点海量，也会造成二叉树的高度很大，会降低操作速度。

4.1.2 多叉树

二叉树中每个节点有一个数据项，最多有两个子节点，如果允许树的每个节点可以有两个以上的子节点，那么这个树就称为 n 阶的多叉树，或者称为 n 叉树。

多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。

4.1.3 B树

B 树通过重新组织节点，降低树的高度，并且减少 IO 读写次数来提升效率。

1. 文件系统及数据库系统的设计者利用磁盘预读原理，将一个节点的大小设为等于一个页(页的大小通常位 4k)。
2. 将树的度 M 设置为 1024，在 600 亿个元素中最多只需要 4 次 IO 操作就可以读取到想要的元素，B树(B+)广泛应用于文件存储以及数据库系统中这样每个节点只需要一次 IO 就可以完全载入。

4.2 2-3树

4.2.1 2-3树介绍

树是最简单的B树结构，具有如下特点：

1. 2-3 树的所有叶子节点都在同一层(只要是 B 树都满足这个条件)
2. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。
3. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。
4. 2-3 树是由二节点和三节点构成的树。

4.3 B树，B+树，B*树

4.3.1 B树介绍

B-tree 树即 B 树，B 即 Balanced，平衡的意思。有人把 B-tree 翻译成 B-树，容易让人产生误解。会以为 B-树是一种树，而B树又是另一种树。实际上，B-tree 就是指的 B树。

2-3 树和 2-3-4 树，它们就是 B 树(英语：B-tree 也写成 B-树)，这里我们再做一个说明，我们在学习 MySQL 时，经常听到说某种类型的索引是基于 B 树或者 B+ 树的，如下图：

1. B 树的阶：节点的最多子节点个数。比如 2-3 树的阶是 3，2-3-4 树的阶是 4
2. B-树的搜索。从跟节点开始，对节点内的关键字(有序)序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围内的儿子节点；重复，直到所对应的儿子指针为空，或已经是叶子节点。
3. 关键字集合分布在整颗树中，即叶子节点和非叶子节点都存放数据。
4. 搜索由可能在非叶子节点结束。

4.3.2 B+树介绍

B+树是 B 树的变体，也是一种多路搜索树。

1. B+树的搜索与B树也基本相同，区别是B+树只有达到叶子节点才命中(B树可以在非叶子节点命中)，其性能也等价于在关键字全集做一次二分查找。
2. 所有关键字都出现在叶子节点的链表中(即数据只能在叶子节点[也叫稠密索引])，且链表中的关键字(数据)恰好是有序的。
3. 不可能在非叶子节点命中。
4. 非叶子节点相当于是叶子节点的索引(稀疏索引)，叶子节点相当于是存储(关键字)数据的数据层。
5. 更适合文件索引系统。
6. B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。

4.3.3 B*树介绍

B*树是B+树的变体，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。

1. B* 树定义了非叶子节点关键字个数至少为 (2/3)*M，即块的最低使用率为 2/3，而 B+ 树的块的最低使用率为 1/2。
2. 从第一个特点我们可以看出，B*树分配新节点的概览比B+树要低，空间使用率更高。