C语言数据结构——树（三）

路径和路径长度
- 在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径（在上图种，从根结点到结点 a 之间的通路就是一条路径。）。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1（上图中从根结点到结点 c 的路径长度为 3。）；
结点的权
- 给每一个结点赋予一个新的数值，被称为这个结点的权。“权”一般代表“重要度”、概率等，我们形象的用一个具体的数字来表示，然后通过数字的大小来决定谁重要，谁不重要，谁的概率大，谁的概率低。
结点的带权路径长度
- 结点到根结点的路径长度乘以该节点的权（上图中结点 b 的带权路径长度为 2*5=10 ）
树的带权路径长度
- 树中各个叶结点的路径长度该叶节点的权的和（各叶子结点的带权路径长度之和），常用WPL(Weight Path Length)表示。
- 上图所示的这颗树的带权路径长度为：WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

3、哈夫曼树的构建方法

第一步：我们将所有的节点都作为独根结点。

第二步：我们将最小的两个结点C和A组建为一个新的二叉树，权值为左右结点之和。

第三步：将上一步组建的新节点加入到剩下的节点中，排除上一步组建过的左右子树，我们选中B组建新的二叉树，然后取权值。

第四步：同上。

4、哈夫曼树的访问

当哈夫曼树构造好以后，我们该如何访问到哈夫曼树上的叶子结点呢？
- 当我们在构造哈夫曼树时可以通过一定的的方法获取到每个叶子结点从根节点开始的访问路径，如果向左记为0，向右记为1，最终每个结点都可以用若干个0 1组成一个编码，该编码我们称之为“哈夫曼编码”。
假如有如下哈夫曼树
- 每个叶子结点的哈夫曼编码为：

5、哈夫曼树的应用

哈夫曼编码是一种编码方式，可以用于无损数据压缩。编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

数据在传输时只需要传输对应的哈夫曼编码即可，例如：发送 statespteasi，我们仅需要发送如下哈夫曼编码：

110111100111110010011100101111101100

如果我们发送哈夫曼编码给接收方，接收方该如何解码呢？

通过一定的手段重构哈夫曼树
发送方将哈夫曼树提前发送给接收方

二、B树

1、B树的基本概念

B树是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。

假如当前有一颗m阶的B树（注意阶的意思是指每个节点的孩子节点的个数），那么其符合：

（1）每个节点最多有m个子节点

（2）除了根节点和叶子节点之外，其他的每个节点最少有m/2（向上取整）个孩子节点

（3）根节点至少有两个孩子节点，（除了第一次插入的时候，此时只有一个节点，根节点同时是叶子节点）

（4）所有的叶子节点都在同一层

（5）有k个子节点的父节点包含k-1个关键码

除了上面B树的性质外，B树还有几个特点：

1，树高平衡，所有的叶节点都在同一层

2，关键码没有重复，父节点中的关键码是其子节点的分解

3，B树保证树种至少有一部分比例的节点是满的。为什么这样说，在上面的性质2中，我们知道每个节点最少可以有 m/2个节点，注意这刚好是一半，没有太满，是因为可以给后续的添加，删除留有余地，这样以来节点不会频繁的触发不平衡，没有太空则意味着B树能够保证降低树的高度。

2、B树的插入

插入规则：在叶子结点上插入结点

假设现在构建一棵四阶B树，开始插入“30”，直接作为根节点，

插入“60”，大于“30”，放右边，

插入“90”，大于“60”，放右边，

继续插入“120”，直接添加的结果如下图，此时超过了节点可以存放容量，对于四阶B树每个节点最多存放3个值，此时需要执行分裂操作

分裂操作为，先选取待分裂节点的中值，这里为“60”，然后将中值“60”放到父节点中，因为这里还没有父节点，那么直接创建一个新的父节点存放“60”，而原来小于“60”的那些值作为左子树，原来大于“60”的那些值作为右子树

继续插入“95”，因为比“60”大，放到右子树中，

继续插入“200”，因为比“60”大，放到右子树中

此时超过了节点可以存放容量，需要执行分裂操作，找到“90 95 120 200”之间的中值“95”，然后将中值“95”放到父节点中，父节点中的“90”小于“95”，于是放到“90”右边，而原来小于“95”的那些值作为左子树，原来大于“95”的那些值作为右子树

继续插入10， 100

继续插入 300

插入300后，需要执行分裂操作，找到“100 120 200 300 ”的中值“300”，然后将中值“120”放到父节点中，父节点中的“60 95”小于“120”，于是放到最右边，而原来小于“120”的那些值作为左子树，原来大于“120”的那些值作为右子树

继续插入500，600

插入600后，需要执行分裂操作，找到“200 300 500 600”的中值“300”，然后将中值“300”放到父节点最右边，而原来小于“300”的那些值作为左子树，原来大于“300”的那些值作为右子树

根节点中元素个数超过了4，选取根节点的中值“95”，然后将中值“95”放到父节点中，由于还没有父节点，那么直接创建一个新的父节点存放“95”，而原来小于“95”的那些值作为左子树，原来大于“95”的那些值作为右子树。

插入250，比根节点大，往根节点的右子树遍历，因为右子树不是叶子节点，继续往下，因为250介于120和300之间，往第二个分支

继续插入700，800

插入800以后，第三个分支需要分裂

3、B树的查找

对B树进行查找就比较简单，查找过程有点类似二叉搜索树，从根节点开始查找，根据比较数值找到对应的分支，继续往子树上查找。

比如查找“250”，"250"大于“95”，往右子树，“250”介于“120 300”之间，往第二个分支，在第二个分支中可以找到250。

4、B树的应用

文件系统中对磁盘数据的存储：

我们知道，数据是存储在磁盘中的，计算机操作磁盘上的文件是通过文件系统进行操作的，在文件系统中就使用到了B树这种数据结构。

磁盘由盘片构成,每个盘片有两面，又称为盘面。盘片中央有一个可以旋转的主轴，他使得盘片以固定的旋转速率旋转，通常是5400rpm或者是7200rpm,一个磁盘中包含了多个这样的盘片并封装在一个密封的容器内。盘片的每个表面是由一组称为磁道同心圆组成的，每个磁道被划分为了一组扇区，每个扇区包含相等数量的数据位，通常是512个子节，扇区之间由一些间隙隔开，这些间隙中不存储数据。

磁盘用磁头来读写存储在盘片表面的数据，由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘 I/O，减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此预读可以提高I/O效率。

页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（一般为4096字节），预读的长度一般为页的整倍数。主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

文件系统的设计者利用了磁盘预读原理，将一个结点的大小设为等于一个页，这样每个结点只需要一次I/O就可以完全载入。

这样设计有什么好处呢？

在实际设计中，我们把 一个结点设为一个页 ，

三、B+树

1、B+树的基本概念

B+树是B树的升级。

不同于B树，B+树的非叶子节点不再保存关键字记录的指针，只进行数据索引
B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取，所以每次查询效率一样
所有叶子结点都有一个指向右边叶子节点的指针
所有数据都保存在叶子结点

2、B+树的插入

B+树的插入与B树类似。

下面是一颗5阶B树的插入过程，5阶B数的结点最少2个key，最多4个key。

1）空树中插入5

2）依次插入8，10，15

3）插入16

插入16后超过了关键字的个数限制，所以要进行分裂。在叶子结点分裂时，分裂出来的左结点2个记录，右边3个记录。结果如下图所示：

当然我们还有另一种分裂方式，给左结点3个记录，右结点2个记录。

4）插入17， 18

插入18后关键字个数大于5，进行分裂。分裂成两个结点，左结点2个记录，右结点3个记录，关键字16进位到父结点（索引类型）中，将当前结点的指针指向父结点

5）插入若干数据后

插入6

插入9

插入19

插入20

插入20后需要进行分裂

插入21

插入22

插入22后分裂

插入7

插入7后需要分裂

根结点的关键字个数超过4，需要继续分裂。左结点2个关键字，右结点2个关键字，关键字16进入到父结点中，将当前结点指向父结点，结果如下图所示：

3、B+树的应用

Mysql数据库中使用B+树做索引：

在对数据库进行查询时，我们可能经常会使用类似如下查询语句：select name from table where ID >=80 and ID <=90，去查找某个区间的内容。

因为B+树的所有叶子节点是一种链式结构，因此在查找80到90之间的所有数据时，我们只需要找到80，然后沿着链表往后遍历即可找到80到90之间的所有数据。

思考：如果使用B树做索引效率比B+树高还是低呢？

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

小参数・大码力・易部署 | Qwen3.6-27B上线魔乐社区，基于昇腾的部署教程来了

继一周前模型开源发布后，千问再度开源Qwen3.6-27B —— 一个拥有270亿参数的稠密多模态模型，也是社区呼声最高的模型规格。Qwen3.6-27B 依然支持多模态思考与非思考模式，在智能体编程方面达到了旗舰级表现，全面超越前代开源旗舰 Qwen3.5-397B-A17B（总参数397B / 激活参数17B的MoE模型）。作为稠密架构，它无需MoE路由即可部署，是开发者在实用、可广泛部署规模