其实,不用看结点C 其实,不用看结点C 北大物些 有,轴即叠究 物啦 铭权有,轨量邮多究 RR型单旋转 RR型单旋转 c 或1 北京大学值歌张写所有即究 旋转运算的实质 双旋转 以R型图示为例,总共有7个部分 三个结点:a、b、c RL或者LR需要进行双旋转 四橾子树T。、T1、T2、T3 这两种情况是对称的 加重c为根的子树,但是其结构其实没有变化 T2、c、T可以整体地看作b的右子树 我们只讨论RL的情况 LR是一样的 目的:重新组成一个新的AVL结构 保留了中序周游的性质 TaT,bT2eT3 1010 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 55 其实，不用看结点C T3 h h+1 T2 h -1 b -2 a T1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 56 其实，不用看结点C a T3 h T2 h b 0 0 h+1 T1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 57 RR型单旋转 T3 h/ h-1 1 b 2 a T2 h-1 /h T1 T0 h h 1 c 或-1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 58 RR型单旋转 b T1 h a T0 h 0 0 1 c 或-1 T2 h-1 /h T3 h/ h-1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 59 旋转运算的实质 „ 以RR型图示为例，总共有7个部分 „ 三个结点：a、b、c „ 四棵子树T0 、T1 、 T2 、 T3 „ 加重c为根的子树，但是其结构其实没有变化 „ T2 、c、 T3可以整体地看作b的右子树 „ 目的：重新组成一个新的AVL结构 „ 平衡 „ 保留了中序周游的性质 „ T0 a T1 b T2 c T3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 60 双旋转 „ RL或者LR需要进行双旋转 „ 这两种情况是对称的 „ 我们只讨论 RL的情况 „ LR是一样的