AVL树是一种特殊的二叉搜索树,由两位俄国数学家G.M.Adelson-Velskii和E.M.Landis所发明,所以取名AVL树。AVL树本质上是一种
平衡的二叉搜索树
一、基本概念
1、AVL树需要满足:
- 每一个节点的左子树和右子树高度差至多为1
- 满足二叉搜索树的性质
2、平衡因子(Balance Factor, BF):左子树高度 - 右子树高度
,因此,由AVL的条件可知,一颗AVL树,它的BF的取值范围只能是{-1, 0, 1}
3、最小不平衡子树:离插入节点最近,且|BF| > 1
的节点为根的子树
二、实现原理
AVL树需要在每次树的结构发生改变的时候,计算BF,通过旋转调整来使得BF取值为{-1, 0, 1}
内,且同时符合二叉搜索树的性质。旋转总共有4种情况,如下:
1、BF > 1,最小不平衡子树根节点的BF和其左子树根节点的BF符号相同,则 右旋:
步骤:
- 保存左子树的根节点为L
- 由二叉搜索树的性质,可知P左边的所有节点数值都小于它的数值。所以,旋转后,P->left = L->right
- L->right = P
- 根节点替换为L
实现:
void rotateR(AVLNode* p) {
AVLNode* L;
L = p->left;
p->left = L->right;
L->right = p;
p = L;
}
2、BF < -1,最小不平衡子树根节点的BF和其右子树根节点的BF符号相同,则 左旋:
步骤:
- 保存右子树的根节点为R
- 因为R的左子树的节点值肯定大于P,所以应该成为P的右子树。P->right = R->left
- R->left = P
- 根节点替换为R
实现:
void rotateL(AVLNode* p) {
AVLNode* R = p->right;
p->right = R->left;
R->left = p;
p = R;
}
3、最小不平衡子树的根节点的BF和其子树根节点的BF符号不同,且子树根节点BF < -1时,先左旋子树,使得BF值符号相同后,再进行一次旋转,如:
4、同理,最小不平衡子树的根节点的BF和其子树根节点的BF符号不同,且子树根节点BF > 1时,先右旋子树,使得BF值符号相同后,再进行一次旋转
三、性能
AVL相比普通的二叉搜索树,最大的优点是不会出现退化为链表,导致查找时间为O(n)的情况。因为AVL树的每次结构变化,都会进行平衡操作,如此一来,能够使得AVL树的查找操作的时间复杂度为O(logn),插入删除也为O(logn)