数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

AVL树 AVL树(平衡的二叉查找树)或者是一棵空树 或者左右子树均为AVL树，且左右子树的深度 之差的绝对值不超过1 若定义二叉树上结点的平衡因子BF(Balance Factor) 为该结点的左子树的深度减去右子树的深度，那么 在AVL树上所有结点平衡因子只可能为-1, 0, 1 只要二叉树上有一个结点的平衡因子的绝对值大于 1,则该二叉树就是不平衡的。 对AVL树来说，它的深度和logN同数量级，因此 我们希望任何初始序列构成的二叉查找树都 是 AVL树。

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

1 1 -1 0 0 0 1 1 0 0

-1 2 1

平衡二叉树和不平衡二叉树示例

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

设最小不平衡子树的根为A,调整的规律可归纳 为下列四种： 1. RR型调整(单右旋); 2. LL型调整(单左旋) ; 3. LR型调整(先左后右双旋); 4. RL型调整(先右后左双旋); 上面的几种情况在经过平衡旋转处理后，以*b 或*c为根的新子树为平衡二叉树，而且它的深度和 插入之前以*a为根的子树相同。 因此，当平衡的二叉排序树因插入结点而失去 平衡时，仅需对最小不平衡子树进行旋转处理。

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

最小不平衡子树: 最小不平衡子树:指离插入结点最近，且以平衡因子绝对值大于1的结点 为根的子树。 27 -2 10 -1 18 最小 不平衡子树 0 25 1 51 41 0 插入结点 1

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

A 1

A 2 B

B 0 A

B 0 γh hβ h α

1

γ h h+1α hβ hβ

0

h α

γh

RR型调整操作示意图 RR型调整操作示意图 (αBβ)A(γ)= (α)B(βAγ) 调整规则∶将A的左子女B提升为新二叉树的根；原来 的根A连同其右子树γ向右下旋转成为B的右子树；B 的原右子树β作为A的左子树。 插入项位于最近的平衡因子为+2的祖先结点的左孩子 的左子树时使用。

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

1 27 A 1 0 10 B 0 05

2 27 A 10 B

0 05 0

10

B 27 A 0

1 2 27 A 1 10 B 0 0 51 γ 0 10 B 1 05 α 0 27 A 0 03 RR型调整操作示例 型 0 18 β 0 51 γ

1 05 α 0 0 18 β 0 03

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

A -1

A -2

B 0 B A 0 h+1 γ βh

B αh hβ 0 αh hγ h β -1

hγ

hα

LL型调整操作示意图 (α)A(βBγ)= (αAβ)B(γ) 型调整操作示意图 调整规则：将A的右子女B提升为新二叉树的根；原来 的根A连同其左子树向左下旋转成为B的左子树；B的 原左子树作为A的右子树。 插入项位于最近的平衡因子为-2的祖先结点的右孩子 孩子的右子树时使用。

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

-1 27 A 0 51 B -1 -2 27 A 0 10 -10 51 B α 0 0 41 -1 73 γ β 0 99

-2 27 A -1 51 B 0 73

0 27 0

51 A

B 73 0

0 51 B -1 γ 0 27 73 A 0 10 α 0 41 β 0 99

LL型调整操作示例 型

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

A 1

A 2

C 0

B 0 0 h α h-1β γ h-1 C h α δ h

B -1 1 C δ h

B 0

A -1

h α h β γ h-1

β h

γ h-1

δ h

LR型调整操作示意图 ((α)B(βCγ))A(δ)= (αBβ)C(γAδ) 型调整操作示意图 调整规则∶设C为A的左子女的右子女，将A的孙子结点C提升 为新二叉树的根；原C的父结点B连同其左子树α向左下旋转成 为新根C的左子树，原C的左

子树β成为B的右子树；原根A连 同其右子树δ向右下旋转成为新根C的右子树，原C的右子树γ 成为A的左子树。 插入项位于最近的平衡因子为+2的祖先结点的左孩子的右子树 时使用。

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

1

27 A 0 51 δ

-2 27 A -1 10 B 0 51 δ

0 10 B

0 05 α 0 18 C 0 18 C

0 05 α 1 18 C 0 16 β

0 10 B -1 27 A 0 05 0 16 β 0 51 δ

LR型调整操作示例 型

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

A -1 B

A -2 B h α C δ h γ h-1 h β 1 δ h γ h-1 h α β h 0 A 0 δ

C 0 B -1 γ h-1 δ h

h αC 0

0

h-1β

RL型调整操作示意图 (α)A((βCγ)B(δ))= (αAβ)C(γBδ) 型调整操作示意图 调整规则：设C为A的右子女的左子女，将A的孙子结点C提升 为新二叉树的根，原来C的父结点B连同其右子树δ向右下旋 转成为新根C的右子树，C的原右子树γ成为B的左子树；原来 的根A连同其左子树α向左下旋转成为新根C的左子树，原来C 的左子树β成为A的右子树。 插入项位于最近的平衡因子为-2的祖先结点的右孩子的左子树 时使用。

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

-1 -1 27 A 0 10 α 0 41 C 0 73 δ 0 0 41 C -1 B 0 27 51 A 0 10 α 0 30 β 0 73 δ 0 0 51 B 0

-1 -2 27 A 0 10 1 51 B α 1 41 0 73 δ 0 β C 0 30

RL型调整操作示例 型

数据结构与算法分析 C++语言描述(第2版)Larry Nyhoff AVL树 PPT

性能分析含有n个结点的AVL树的高度是h= O(log2n)。插入结点 的时间耗费最大为树的深度O(log2n)。 算法在查找插入结点的同时也找到最小不平衡子树。 最小不平衡子树中平衡因子的最大调整时间为最小不平衡 子树的深度。四种子树调整时 …… 此处隐藏：1201字，全部文档内容请下载后查看。喜欢就下载吧 ……