中国科学技术大学：《数据结构及算法》课程教学资源（PPT课件讲稿）二叉平衡树旋转

二叉排序树的平衡旋转 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 1 中国科学技术大学 二叉排序树的平衡旋转

LL型旋转 A B 2 0 B 0 AR B Bu h-1 BR h-1 BR AR h-i 插入节点 ypb@ustc.edu.cn 2 中国科学技术大学

ypb@ustc.edu.cn 2 中国科学技术大学 LL型旋转 A 2 B 1 BL BR AR h h-1 h-1 B 0 A 0 BR AR BL h h-1 h-1 插入节点

LR型旋转 C 2 0 B B A 0 AR h-2 BL h-1 C Cr AR h- h-1 h-1 BL h- h-2 插入节点 ypb@ustc.edu.cn 3 中国科学技术大学

ypb@ustc.edu.cn 3 中国科学技术大学 LR型旋转 A 2 B -1 C 1 h-1 CL h-2 CR BL h-1 插入节点 AR C 0 B 0 A -1 BL h-1 CL CR h-2 h-1 AR h-1 h-1

RR型旋转 A B -2 0 B -1 0 h-1 A h-1 B BR h- A h-1 B h BR 插入节点 ypb@ustc.edu.cn 4 中国科学技术大学

ypb@ustc.edu.cn 4 中国科学技术大学 RR型旋转 A -2 B -1 h-1 AL BL BR h h-1 B 0 A 0 BL h-1 BR h h-1 AL 插入节点

RL型旋转 C -2 0 B A B .1 0 A h-l 1 h-1 BR h- R h-2 h- h-1 BR h- h-2 CR 插入节点 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 5 中国科学技术大学 RL型旋转 A -2 B 1 C 1 h-1 CL h-2 CR AL h-1 C 0 A 0 B -1 BR h-1 AL h-1 CL h-1 CR h-2 BR h-1 插入节点