愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

AVL树学习总结

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)