【数据结构】4. 树与二叉树(9)

LL 平衡旋转（右单旋转）。
由于在结点 A 的左孩子（L）的左子树（L）上插入了新结点，A 的平衡因子由 1 增至 2,导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。
将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树。
如图 4-26 所示，结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。

注意：LR 和 RL 旋转时，究竞新结点插入在 C 的左子树还是右子树上，不影响旋转过程，而图 4-28 和图 4-29 中以插入 C 的左子树中为例。

（3）平衡二叉树的查找

在平衡二叉树上进行査找的过程和二叉排序树相同，因此，在査找的过程中和给定值进行比较的关键字个数不超过树的深度。
假设以 Nk 表示深度为 h 的平衡树中含有的最少结点数。
显然，\(N_0=0,N_1=1,N_2=2\)，并且有 \(N_h = N_{h-1}+N_{h-2}+1\)。
可以证明，含有 n 个结点平衡二叉树的最大深度为
\(\mathcal{O}(\log_2{n})\)，因此，平衡二叉树的平均査找长度为 \(\mathcal{O}(\log_2{n})\)。如图 4-30 所示。

注意：
该结论可用于求解给定结点数的平衡二叉树的查找所需的最多比较次数（或树的最大高度）。
如，问含有 12 个结点的平衡二叉树中查找某个结点的最多比较次数是？

4.5.3 哈夫曼（Huffman）树和哈夫曼编码

（1）哈夫曼树的定义

在许多实际应用中，树中结点常常被賦予一个表示某种意义的数值，称为该结点的权。
从树根结点到任意结点的路径长度（经过的边数）与该结点上权值的乘积称为该结点的带权路径长度。
树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为
\(WPL = \sum_{i=1}^n w_i\times i_i\)
式中，\(w_i\) 是第 i 个叶结点所带的权值；\(i_i\) 是该叶结点到根结点的路径长度。
在含有 N 个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称为最优二叉树。

例如，图 3-31 中的 3 棵二叉树，都有 4 个叶子结点 a、b、c、d，分别带权 7、5、2、4,它们的带权路径长度分别为

(a) WPL=7X2+5X2+2X2+4X2=36

(b) WPL=7X3+5X3+2X144X2=46

(c) WPL=7x]+5x2+2x3+4x3=35
其中图 4-31(c) 中树的 WPL 最小。可以验证，它恰为哈夫曼树。

（2）哈夫曼树的构造

给定 N 个权值分别为 \(w_1,w_2,w_N\) 的结点。
通过哈夫曼算法可以构造出最优二叉树，算法的描述如下：

1. 将这 N 个结点分别作为 N 棵仅含一个结点的二叉树，构成森林 F。
2. 构造一个新结点，并从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。
4. 重复步骤 2 和 3，直至 F 中只剩下一棵树为止。

从上述构造过程中可以看出哈夫曼树具有如下特点：

1. 每个初始结点最终都成为叶结点，并且权值越小的结点到根结点的路径长度越大。
2. 构造过程中共新建了 N-1 个结点（双分支结点），因此哈夫曼树中结点总数为 2N-1。
3. 每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

例如，权值{7,4}的哈夫曼树的构造过程如图 4-32 所示。

（3）哈夫曼编码

（编辑：ASP站长网）