11
28
96 98
25
(1) LL型调整 型调整 p A 1 2
调整方法: 调整方法: 单向右旋平衡,即将 的左孩子 单向右旋平衡,即将A的左孩子 B 向右上旋转代替 成为根结点, 向右上旋转代替A成为根结点 成为根结点, 结点向右下旋转成为B的右 将A结点向右下旋转成为 的右 结点向右下旋转成为 子树的根结点, 子树的根结点,而B的原右子树 的原右子树 则作为A结点的左子树 结点的左子树. 则作为 结点的左子树. h d e B
1 38 -1 24 88
0 -1 -2
0
11
28 1
96
0
-1 0
25
0
98
1,平衡二叉树插入结点的调整方法
若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性, 若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性, 首先从根结点到该新插入结点的路径之逆向根结点方向找第一个失去平 衡的结点, 衡的结点,然后以该失衡结点和它相邻的刚查找过的两个结点构成调整 子树(最小不平衡子树 即调整子树是指以离插入结点最近,且平衡因子 最小不平衡子树), 子树 最小不平衡子树 ,即调整子树是指以离插入结点最近 且平衡因子 绝对值大于1的结点为根结点的子树 使之成为新的平衡子树. 的结点为根结点的子树,使之成为新的平衡子树 绝对值大于 的结点为根结点的子树 使之成为新的平衡子树. 38 24 88 -2
(2)RR型调整 型调整 p A -1 -2
调整方法: 调整方法: 单向左旋平衡:即将 的右孩子 的右孩子B向 单向左旋平衡:即将A的右孩子 向 左上旋转代替A成为根结点 成为根结点, 左上旋转代替 成为根结点,将A结 结 点向左下旋转成为B的左子树的根 点向左下旋转成为 的左子树的根 结点, 的原左子树则作为A结点 结点,而B的原左子树则作为 结点 的原左子树则作为 的右子树. 的右子树. B
C
e C
B
A
h+1 n
n
m
i
e
(4)RL型调整 ) 型调整 p A -1 -2 b 0 1
B m h+1 0 -1
调整方法: 调整方法:先右旋转后左 旋转平衡,即先将 即先将A结点的 旋转平衡 即先将 结点的 右孩子B结点的左子树的 右孩子 结点的左子树的 根结点C结点向右上旋转 根结点 结点向右上旋转 提升到B结点的位置 结点的位置, 提升到 结点的位置,然 后再把该C结点向左上旋 后再把该 结点向左上旋 转提升到A结点的位置 结点的位置. 转提升到 结点的位置. h+1 m
平衡二叉树(AVL) 平衡二叉树
平衡二叉树的概念 平衡二叉树的查找 平衡二叉树中结点的插入与建立 平衡二叉树中结点的删除
平衡二叉树(AVL) 平衡二叉树(AVL)
结点的平衡因子(balancd factor用bf表示) :二叉树中某结点左 结点的平衡因子( factor用bf表示) 平衡因子 表示 子树的高度与右子树的高度之差称为该结点的平衡因子. 子树的高度与右子树的高度之差称为该结点的平衡因子. 平衡二叉树是另一种形式的二叉查找树.其特点是: 平衡二叉树是另一种形式的二叉查找树.其特点是: 左右子树深度之差的绝对值不大于1 左右子树深度之差的绝对值不大于1 称有这种特性的二叉树为平衡二叉树. 称有这种特性的二叉树为平衡二叉树. 平衡二叉树 在算法中,可以通过平衡因子来具体实现平衡二叉树的定义. 在算法中,可以通过平衡因子来具体实现平衡二叉树的定义. 从平衡因子的角度可以说,若一棵二叉树中所有结点的平衡因子的绝 从平衡因子的角度可以说, 对值小于或等于1,则该树称为平衡二叉树. 对值小于或等于1 则该树称为平衡二叉树.
h
else{
p1=p->lchild;
P->bf=1,要作LL调整
If(p1->bf==1) { p->lchild=p1->rchild;p1->rchild=p; p->bf=p1->bf=0; p=p1; } else if(p1->bf==-1) {p2=p1->rchild; p1->rchild=p2->lchild; p2->lchild=p1; p->lchild=p2->rchild; if(p2->bf==0) else { } else {p1->bf=1; p=p2 ; p->bf=0; } Taller=0;} } p->bf=0;} p2->rchild=p; 要作LR调整
平均查找长度为: 平均查找长度为:O(log2n)
平衡二叉树中结点的插入与建立
在平衡二叉树BBST中插入一个结点 的大体步骤如下: 中插入一个结点x的大体步骤如下 在平衡二叉树 中插入一个结点 的大体步骤如下: 为空树, 若BBST为空树,则插入一个数据元 为空树 素为x的新结点作为 素为 的新结点作为BBST的根结点; 的根结点; 的新结点作为 的根结点 沿着插入x的路线返回 逐层回溯,必要时修改x祖先的平衡因子 的路线返回, 祖先的平衡因子, 沿着插入 的路线返回,逐层回溯,必要时修改 祖先的平衡因子,因为插 的关键字和BBST的根结点的关 若x的关键字和 的关键字和 的根结点的关 后会使某些子树的高度增加. 入x后会使某些子树的高度增加. 后会使某些子树的高度增加 键字相等,不能进行插入; 键字相等,不能进行插入; 的关键字小于BBST的根结点的或 的关键字小于 的根结点的 回溯途中,一旦发现x的某个祖先 若x的关键字小于 回溯途中,一旦发现 的某个祖先p失衡,即由p->bf=1变成 变成p->bf=2或 的某个祖先 失衡,即由 - 失衡 变成 关键字,而且在BBST的左子树中不 关键字,而且在 的左子树中不 变成p->bf=-2,则旋转以 为根的子树结构 使之平衡 则旋转以*p为根的子树结构 使之平衡. 由p->bf=-1变成 变成 则旋转以 为根的子树结构,使之平衡 存在和x有相同关键字的结点,则将 存在和 有相同关键字的结点, 有相同关键字的结点 x插入在 插入在BBST的左子树上; 的左子树上; 插入在 的左子树上 的关键字大于BBST的根结点的 若x的关键字大于 的关键字大于 的根结点的 关键字,而且在BBST的右子树中不 关键字,而且在 的右子树中不 存在和x有相同关键字的结点 有相同关键字的结点, 存在和 有相同关键字的结点,则将 x插入在 插入在BBST的右子树上; 的右子树上; 插入在 的右子树上 像一般的二叉排序树那样插入x; 像一般的二叉排序树那样插入 ;
C
A
B
C c
f
n
t
f
n
h
t p->rchild=c->lchild; /*把C的左子树挂接成 的右子树 把 的左子树挂接成 的右子树*/ 的左子树挂接成A的右子树
b->lchild=c->rchild; /*把C的右子树挂接成 的左子树 把 的右子树挂接成 的左子树*/ 的右子树挂接成B的左子树 c-rchild=b; c->lchild=p; /*把B挂接成 的右子树 把 挂接成 的右子树*/ 挂接成C的右子树 /*把A挂接成 的左子树 把 挂接成 的左子树*/ 挂接成C的左子树
输入关键字序列{16,3,7,11,9,26,18,14,15}, {16,3,7,11,9,26,18,14,15},给 例1 输入关键字序列{16,3,7,11,9,26,18,14,15},给 出构造一棵AVL树的步骤. AVL树的步骤 出构造一棵AVL树的步骤.
0 1 16 2 属于" 型 应该进行 应该进行LR调整 属于"<"型,应该进行 调整 先左旋转后右旋转平衡 0 7 LR调整后 调整后 3 0 -1 0 3 0 16 1 2 0 7 属于" 型 应该进行 应该进行LL调整 属于"/"型,应该进行 调整 单向右旋转 9 11 0 1 -1 -2
18 0 属于" 型 应该进行 应该进行LR调 属于"<"型,应该进行 调 整 先左旋转后右旋转平衡
26 0
14
-1
15
LR调整后 调整后117来自1839
15
26
14
16
从上述例题可以看出,每插入一个结点至多调整一次 全树都能达 从上述例题可以看出 每插入一个结点至多调整一次,全树都能达 每插入一个结点至多调整一次 到平衡. 到平衡
p
B a h
0 -1
A
c
a b h c
b
lc=p->rchild; p->rchild=lc->lchild; lc->lchild=p; p=lc;
/*lc指向 指向B*/ 指向 /*把B结点的左子树挂接为 的右子树 结点的左子树挂接为A的右子树 把 结点的左子树挂接为 的右子树*/ /*A结点成为 的左孩子*/ 结点成为B的左孩子 结点成为 的左孩子 /*p指向新的根结点 指向新的根结点*/ 指向新的根结点
平衡二叉树的查找
BSTNode * SearchBST(BSTNode * bt,KeyType k) {//在以 为根的平衡二叉树中 查找关键字为 的结点 找到返回指向该结点 在以bt为根的平衡二叉树中 查找关键字为k的结点 在以 为根的平衡二叉树中,查找关键字为 的结点,找到返回指向该结点 指针,否则返回 的//指针 否则返回 指针 否则返回NULL if (bt = =NULL || bt->key = =k) return bt; if(k<bt->key) return SearchBST(bt->lchild,k); else return SearchBST(bt->rchild,k); }
(3)LR型调整 型调整 p 2 1 b 0 -1 B 0 1 c m h i p->lchild=c->rchild; /*把C的右子树挂接成 的左子树 把 的右子树挂接成 的左子树*/ 的右子树挂接成A的左子树 b->rchild=c->lchild; /*把C的左子树挂接成 的右子树 把 的左子树挂接成 的右子树*/ 的左子树挂接成B的右子树 c-lchild=b; c->rchild=p; /*把B挂接成 的左子树 把 挂接成 的左子树*/ 挂接成C的左子树 /*把A挂接成 的右子树 把 挂接成 的右子树*/ 挂接成C的右子树 A 调整方法: 调整方法:先左旋转后右旋 转平衡,即将 即将A结点的左孩子 转平衡 即将 结点的左孩子 结点) (即B结点)的右子树的根 结点 结点(即C结点)向左上旋 结点( 结点) 结点 转提升到B结点的位置 结点的位置, 转提升到 结点的位置,然 后再把该C结点向右上旋转 后再把该 结点向右上旋转 提升到A结点的位置 结点的位置. 提升到 结点的位置. h+1