(a)
程序讲解-双旋转
2
A
-1
B
-1
C
AR h-1
BL
CL h-2 CR
1
C
1
B
2
A
AR CR
BL CL
0
C
1
0
B
A
BL CL CR AR
(b)
程序讲解-双旋转
2
A
-1
B
0
BL
C
AR h-1
ቤተ መጻሕፍቲ ባይዱ
CL CR
2A
1C
0
AR
B
CR
BL CL
0C
0
0
B
A
BL CL CR AR
(c)
程序讲解-双旋转
private AvlNode<AnyType> doubleWithLeftChild(AvlNode<Node> A) {
3）因此，在二叉平衡树上进行查找时，查找过 程中和给定值进行比较的关键字的个数和
log(n) 相当。
1 5
2
课堂练习
1、按次序输入关键字：1, 2, 3, 4, 5, 6,7，试画出 AVL树的构造和调整过程。
2、按次序输入关键字：e, i, p, k, m, l,b，试画出 AVL树的构造和调整过程。并求其在等概率的情况 下查找成功的平均查找长度。
//LR型，先左旋转，后右旋转 A.left=rotateWithLeftChild(A.left); return rotateWithRightChild(A); }
对于RL型，同理可得到doubleWithRightChild( )方法， 详见课本100页，4-43
程序讲解-主程序
private AvlNode<AnyType> insert(AnyType x, AvlNode<AnyType> t){
空树的高度定义为-1。
平衡二叉树的定义
节点的平衡因子：该节点的左子树的深 度减去它的右子树的深度
平衡二叉树所有节点的平衡因子只可能为： -1，0，1。
平衡二叉树的定义
2
5
2
0
4
8
1
2
0
1
平衡因子 >1
1
5
1
0
4
8
0
2
平衡因子 <=1
非平衡二叉树
平衡二叉树
平衡二叉树的定义
5
7
2
8
2
8
1
47
1
4
3
旋转
-2
A
-2
A
h-1 AL
B C
h-1 AL
C
B
CL
BR
CL
CR
h-1
X
CR
h-1
BR
X
平衡二叉树的构造-双旋转
一、双旋转-RL型的调整过程
先在A的右儿子和孙子之间右旋转，再在A和它的新儿子之间左
旋转 -2
0
A
C
h-1 AL
C
B
CL
CR
h-1
BR
X
A
B
h-1 AL
CL h-1 CR
BR
X
平衡二叉树的构造—举例
B
LL型：围绕左孩子单旋转
0
A
AvlNode<AnyType> B=A.left;
A.left=B.right;
BL
B.right=A;
BR AR X
X
A.height=Math.max(height(B.left),height(A.right))+1;
B.height=Math.max(height(B.left),A.height)+1;
程序讲解-双旋转
2A
-1
B
1
BL
C
AR h-1
CL CR h-2
2A
2C
AR
0
B
CR
BL CL
0
C
0
-1
B
A
BL CL CR AR
LR型：先以C为根左旋转，再以C为根右旋转 rotateWithLeftChild(B) rotateWithLeftChild(A.left) rotateWithRightChild(A)
平衡二叉树的构造-单旋转
一、单旋转-RR型
-1 A
-2 A
h-1 AL
B
BL h-1 BR
h-1 AL
B
BL
BR
h
平衡二叉查找树
X
插入x后不再平衡
平衡二叉树的构造-单旋转
一、单旋转-RR型的调整过程 左旋转
0
-2 A
B
h-1 AL
B
BL
BR
h
X
h-1 AL
A
BR BL h
X AL
抓住节点B往上拽使之成为根节点，自然，A成为了B的 左孩子，BR,AL的性质不变，BL成为了A的右孩子。
B
CR
BL
CL
h-1
X
AR h-1
B
A
BL
CL CR
h-1
X
AR h-1
平衡二叉树的构造-双旋转
一、双旋转-RL型
-2
A
-1 A
h-1 AL
B
C
BR CL h-2 CR
h-1 AL
B
C
BR
CL
CR
h-1
X
平衡二叉查找树
插入x后不再平衡
平衡二叉树的构造-双旋转
一、双旋转-RL型的调整过程
先在A的右儿子和孙子之间右旋转，再在A和它的新儿子之间左
B.height=Math.max(height(B.left),A.height)+1; return B; }
程序讲解-单旋转
-2
A
-1
B
AL
BL BR
0B 0A
AL
BL
RR型：围绕右孩子单旋转
AvlNode<AnyType> B=A.right;
A.right=B.left;
BR
B.left=A;
问：含 n 个关键字的二叉平衡树可能达到的最
大深度是多少？
平衡二叉树的查找性能分析
n=0
n=1
n=2
空树 最大深度为0 最大深度为1
最大深度为2
n=3 ?
平衡二叉树的查找性能分析
n =4
n =7
最大深度为3 n =5,6 ?
最大深度为 4
1.44log(n+2)-1.328
平衡二叉树的查找性能分析
X
X
A.height=Math.max(height(A.left),height(B.left))+1; B.height=Math.max(height(B.right),A.height)+1;
程序讲解-单旋转
private AvlNode<AnyType> rotateWithRightChild(AvlNode<Node> A) { //RR型，左旋转
一、双旋转-LR型的调整过程
先在A的左儿子和孙子之间左旋转，再在A和它的新儿子之间右旋转
2A
2A
B
C
BL
AR h-1
C
B
CR
AR h-1
CL
CR
h-1
X
BL
CL
h-1
X
平衡二叉树的构造-双旋转
一、双旋转-LR型的调整过程
先在A的左儿子和孙子之间左旋转，再在A和它的新儿子之间右旋转
2A
0
C
C
35
平衡二叉树
非平衡二叉树
平衡二叉树的构造
造成不平衡的原因 单旋转 双旋转 举例
平衡二叉树的构造
当向一个AVL树中插入一个新节点是，有可能 破坏AVL树的特性。
5
2
8
将6插入到AVL树中
将会破坏关键字为8的节点 处的平衡。
1 47 36
即关键字为8的节点必须重 新平衡。
如果发生这种情况，就需在插入完成之前恢复平 衡的性质。我们称恢复调整的过程为旋转(rotation)
单旋转举例
从空AVL树开始依次插入关键字3,2,1,4,5,6,7
3 插入2
3 3 插入1
LL型，右旋转
2
插入4
2
2
1
3
1
2
2
2
RR型，左旋转
插入5
1
4
1
3
1
3
3
5
4
4
5
单旋转举例
从空AVL树开始依次插入关键字3,2,1,4,5,6,7
2
1
4
插入6
1
2 4
RR型，左旋转
3
5
3
5
1
6
4 25
36
单旋转举例
平衡二叉树的构造
2 -2
A
A
2
-2
A
A
B
B
B
B
C
C
C
C
X
X
X
X
LL
RR
LR RL
平衡二叉树的构造-平衡方案
一、插入发生在“外边”的情况， 即LL型和RR型 平衡方案：单旋转(single rotation)
二、插入发生在“内部”的情况， 即LR型和RL型 平衡方案：双旋转(double rotation)
