|
LL 平衡旋转（右单旋转）。
由于在结点 A 的左孩子（L）的左子树（L）上插入了新结点，A 的平衡因子由 1 增至 2,导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。
将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树。
如图 4-26 所示，结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。
RR 平衡旋转（左单旋转）。
由于在结点 A 的右孩子（R）的右子树（R）上插入了新结点，A 的平衡因子由-1 减至-2,导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。
将 A 的右孩子 B 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为 A 结点的右子树，如图 4-27 所示。
LR 平衡旋转（先左后右双旋转）。
由于在 A 的左孩子（L）的右子树（R）上插入新结点，A 的平衡因子由 1 增至 2,导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。
先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置，如图 4-28 所示。
RL 平衡旋转（先右后左双旋转）。
由于在 A 的右孩子（R）的左子树（L）上插入新结点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。
先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置，如图 4-29 所示。
注意：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_itimes 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）哈夫曼树的构造
（编辑：晋中站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
