保研面试408复习9——哈夫曼树和B树、资源分配图

1.哈夫曼树

哈夫曼树（Huffman Tree）是一种用于数据压缩的二叉树。它是根据字符出现的频率来构建的，以便最频繁使用的字符有最短的编码。以下是哈夫曼树的生成过程：

生成过程步骤：

1. 统计频率：

   • 计算每个字符在文本中出现的频率。

2. 初始化优先队列：

   • 创建一个优先队列（通常是最小堆），并将每个字符及其频率作为一个节点插入队列中。优先队列按频率排序，频率最小的节点有最高优先级。

3. 构建哈夫曼树：

   • 从优先队列中取出两个频率最小的节点，创建一个新节点作为它们的父节点。新节点的频率等于这两个节点频率之和。
   • 将新节点插回优先队列中。
   • 重复上述步骤，直到优先队列中只剩下一个节点。这个节点就是哈夫曼树的根节点。

4. 生成哈夫曼编码：

   • 从根节点开始，为每个左边分支分配一个“0”，为每个右边分支分配一个“1”。
   • 遍历整棵树，从根节点到每个叶子节点形成的路径就是该字符的哈夫曼编码。

示例：

假设我们有以下字符及其频率：

• A: 5
• B: 9
• C: 12
• D: 13
• E: 16
• F: 45

步骤 1: 初始化优先队列：

[(5, 'A'), (9, 'B'), (12, 'C'), (13, 'D'), (16, 'E'), (45, 'F')]
1

步骤 2: 构建哈夫曼树：

1. 取出频率最小的两个节点 (5, 'A') 和 (9, 'B')，创建新节点 (14, AB)：

[(12, 'C'), (13, 'D'), (14, 'AB'), (16, 'E'), (45, 'F')]
1

2. 取出频率最小的两个节点 (12, 'C') 和 (13, 'D')，创建新节点 (25, CD)：

[(14, 'AB'), (16, 'E'), (25, 'CD'), (45, 'F')]
1

3. 取出频率最小的两个节点 (14, 'AB') 和 (16, 'E')，创建新节点 (30, ABE)：

[(25, 'CD'), (30, 'ABE'), (45, 'F')]
1

4. 取出频率最小的两个节点 (25, 'CD') 和 (30, 'ABE')，创建新节点 (55, CDABE)：

[(45, 'F'), (55, 'CDABE')]
1

5. 取出最后两个节点 (45, 'F') 和 (55, 'CDABE')，创建根节点 (100, FCDABE)：

[(100, FCDABE)]
1

步骤 3: 生成哈夫曼编码：

• 从根节点开始，左边分支为“0”，右边分支为“1”。
• A的编码：从根节点到A的路径是右-右-左，即110。
• B的编码：从根节点到B的路径是右-右-右，即111。
• C的编码：从根节点到C的路径是左-左，即00。
• D的编码：从根节点到D的路径是左-右，即01。
• E的编码：从根节点到E的路径是右-左，即10。
• F的编码：从根节点到F的路径是左，即0。

最终的哈夫曼编码如下：

A: 110
B: 111
C: 00
D: 01
E: 10
F: 0
1
2
3
4
5
6

哈夫曼树的生成过程通过利用字符频率构建一个最优二叉树，实现了数据压缩，减少了平均编码长度。

2.B树

m阶B树：

• 根结点至少2个子节点，最多m个子节点
• 其他结点至少$\lceil m/2\rceil$个子节点，最多m个子节点

3.B+树

m阶B+树：

• 根结点至少2个子节点，最多m个子节点
• 其他结点至少$\lceil m/2\rceil$个子节点，最多m个子节点
• 与B树不同的是：
  • ①B+树的内部节点只存储键值，不存储数据，数据都存储在叶子结点中
  • ②B+树的键值一定都会出现在叶子结点中
  • ③B树的内部节点存储的不仅仅是键值，也存储数据。

4.资源分配图（死锁预防）

资源分配图（Resource Allocation Graph, RAG）是一种用于描述系统中进程和资源分配关系的有向图。它在操作系统中用于分析和检测死锁情况。通过资源分配图，可以直观地看到哪些进程正在等待哪些资源，以及哪些资源已经分配给了哪些进程。

资源分配图的构成

1. 节点：资源分配图中的节点分为两类：

   • 进程节点（用圆形表示）：表示系统中的进程。
   • 资源节点（用矩形表示）：表示系统中的资源，每个资源节点可以有若干个实例（小圆点表示）。

2. 边：资源分配图中的边也是两种类型：

   • 请求边（由进程节点指向资源节点）：表示进程请求资源。
   • 分配边（由资源节点指向进程节点）：表示资源已经分配给进程。

资源分配图的使用

资源分配图用于描述系统中进程和资源的状态，并可以用于死锁的分析和检测。下面是一些关键点：

1. 资源分配图的例子：

   • 如果一个进程P1请求一个资源R1，则在图中画一条从P1指向R1的请求边。
   • 如果资源R1分配给了进程P1，则在图中画一条从R1指向P1的分配边。

2. 死锁的检测：

   • 单实例资源系统：如果资源分配图中存在一个环，则系统处于死锁状态。
   • 多实例资源系统：如果资源分配图中存在一个环，不一定处于死锁状态，具体情况需要进一步分析。

死锁的预防和避免

1. 预防死锁：

   • 预防死锁是通过某些策略确保系统不会进入死锁状态。例如，通过资源有序分配法或者一次性资源分配法来防止系统进入死锁。
   • 使用资源分配图可以帮助设计这些策略，确保在分配资源时不会形成环。

2. 避免死锁：

   • 避免死锁是在系统运行过程中，通过动态地分配资源，确保系统始终处于安全状态。例如，使用银行家算法来避免死锁。
   • 在每次资源分配之前，通过资源分配图来模拟分配后的状态，如果不会形成环，则进行分配，否则拒绝该请求。

总结

资源分配图是一种有效的工具，用于描述和分析系统中进程和资源的关系。它在死锁的检测、预防和避免中起着重要的作用。通过资源分配图，可以直观地看到系统中的资源分配情况，进而采取适当的策略来处理可能的死锁问题。