《提高组(高中组)初赛复习资料4》.ppt

* 左改组（新插入结点出现在危机结点的左子树上进行的调整） 的情况分析： 1、LL 情况：(LL：表示新插入结点在危机结点的 左子树的左子树上) A B +1 h-1 0 +2 +1 h h-1 h-1 LL 改组 BL BR AR B A 0 h 0 h-1 h-1 BL BR AR 危机结点 改组前：高度为 h + 1 中序序列： A B BL BR AR 改组后：高度为 h + 1 中序序列： A B BL BR AR 注意：改组后 平衡度为 0 A B * 2、LR 情况：（LR：表示新插入结点在危机结点的 左子树的右子树上） 情况A： A B +1 h-1 0 +2 -1 h-1 LR 改组 BL AR 危机结点 C CL CR h-2 h-2 h-1 0 +1 C B 0 h-1 h-1 BL AR A CR h-2 CL h-1 -1 0 改组前： 高度为 h + 1 中序序列： 注意：改组后 平衡度为 0,0,-1 C B A B BL AR C CL CR 改组后： 高度为 h + 1 中序序列： A B BL AR C CL CR A * 情况B ： A B +1 h-1 0 +2 -1 h-1 LR 改组 BL AR 危机结点 C CR CL h-1 h-2 h-2 0 -1 C B 0 h-1 h-1 BL AR A CL h-1 CR h-2 +1 0 改组前： 高度为 h + 1 中序序列： 注意：改组后 平衡度为 +1,0,0 C B A B BL AR C CR CL 改组后： 高度为 h + 1 中序序列： A A B BL AR C CR CL * 三种情况的区分： 如果B的平衡度为＋1 则为 LL型改组； 否则为 LR型改组： 若C的平衡度为： 1:则为LRA型改组； －1:则为LRB型改组。 * 右改组（新插入结点出现在危机结点的右子树上进行的调整） 的情况分析： 1、RR 情况： （RR：表示新插入结点在危机结点的右子树的右子树上） 处理图形和 LL 镜象相似 2、RL 情况： （RL：表示新插入结点在危机结点的右子树的左子树上） A、处理图形和 LRA 镜象相似 B、处理图形和 LRB 镜象相似 * 平衡二叉排序树查找的分析 平衡树上进行查找的时间复杂度为： O(log2n) * B-树(平衡多叉树) 1 100 9 48 2 112 1 4 6 2 36 1 68 90 2 101 110 2 121 1 B- 树中不存在相同的关键字 * 一棵 m 阶 B- 树或者是一棵空树，或者是满足下列条件的平衡 m 叉树： 树中每个结点至多有 m 棵子树； 除根结点之外，其他每个结点至少有 m/2 棵子树； 若根结点不是叶结点，则至少有两棵子树； 所有叶结点都在同一层上，叶结点不包含任何信息； 每个非叶结点包含下列信息： (n, P0, K1, P1, K2, P2, … , Kn, Pn) K1 ＜ K2 ＜ … ＜ Kn P0 所指子树中所有结点的关键字均小于 K1 Pi 所(1＜i＜n)指子树中所有结点的关键字均大于 Ki且小于 Ki+1 Pn 所指子树中所有结点的关键字均大于 Kn m/2 ≤ n + 1 ≤ m m/2 － 1 ≤ n ≤ m – 1 * B- 树结点的结构类型： typedef struct mbs { int keynum; keytype Key[m]; /* 0 号单元未用*/ struct mbs *link[m]; } * 查找36 查找108 1 100 112 9 48 2 1 4 6 2 36 1 68 90 2 101 110 2 121 1 36 * 100 20 60 5 10 80 25 40 120 180 110 116 132 189 200 3 阶 B- 树插入： 插入90 100 20 60 5 10 80 90 25 40 120 180 110 116 132 189 200 * 插入195 100 20 60 5 10 80 90 25