|
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）哈夫曼树的定义
（编辑：浙我家）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
