AVL树

Apr 5, 2019

普通的二叉搜索树的退化

在使用二叉搜索树时，只规定了左子树的值小于根节点的值，右子树的值大于根节点的值，并没有对树的形状做出要求。

在树较为平衡（左右子树高度相差较小）时，如下图所示：
平衡时
我们在二叉搜索树上进行的增加、删除、查找的操作的时间复杂度平均为$O(log\,n)$。

但是在树比较倾斜时，在二叉搜索树上的操作的时间复杂度也会随之增加，树越倾斜，退化也就越严重，时间复杂度也就越高。

一种极端情况下，当所有的节点（除叶节点外）都只有一个子树或子节点时，该树结构会退化为链表，相应的时间复杂度也会退化为$O(n)$。
不平衡时

为了解决这个问题，平衡树也就应运而生。其中最早的平衡树便是本文的重点——AVL树。

什么是AVL树

AVL树是最早被发明的自平衡二叉搜索树。它的名字不是自平衡二叉搜索树的缩写，而是来源于它的发明者G. M. Adelson-Velsky和Evgenii Landis。

AVL树在二叉搜索树的性质上增加了一条——任一节点的两个子树高度差最大为1。因此，AVL树在执行增加、删除、查找操作的时间复杂度在平均、最坏情况下均为$O(log\,n)$。不会出现二叉搜索树中退化的情况。

平衡因子

AVL树中使用这个参数来判定当前节点是否是平衡的。平衡因子由当前节点的左子树高度减去右子树高度得到。

所以当一个节点的平衡因子大于1或小于-1时，则可以判定当前节点不平衡，需要进行调整。

另外，AVL树中也可以不保存节点的平衡因子，而保存树的高度，在需要时计算得到。

旋转

旋转是一种改变树的平衡性的操作，几乎所有的平衡树都是通过旋转操作来调整树的结构，使树保持平衡状态。

旋转分为两类：

  • 左旋转
  • 右旋转

左旋转

总共3步：

  • 将根节点的右子节点设置为右子节点的左子节点。
  • 将右子节点的左子节点设置为根节点。
  • 将右子节点设置为根节点。

相应的代码为：

  1. AVLTreeNode* RotateL(AVLTreeNode* root) {
  2.     AVLTreeNode* temp = root->right;
  3.     root->right = temp->left;
  4.     temp->left = root;
  6.     return temp;
  7. }

旋转前后对比：
左旋转

从图中可以看出，左旋转之后，相比于原来的树，左子树高度增加了1，右子树高度减少了1。

右旋转

类似于左旋转，也为三步：

  • 将根节点的左子节点设置为左子节点的右子节点。
  • 将左子节点的右子节点设置为根节点。
  • 将左子节点设置为根节点。

相应的代码为：

  1. AVLTreeNode* RotateR(AVLTreeNode* root) {
  2.     AVLTreeNode* temp = root->left;
  3.     root->left = temp->right;
  4.     temp->right = root;
  6.     return temp;
  7. }

旋转前后对比：
右旋转

从图中可以看出，右旋转之后，相比于原来的树，右子树高度增加了1，左子树高度减少了1。

AVL树中不平衡情况及对应旋转操作

在操作AVL树过程中，总共会遇到4种不平衡的情况：LL、RR、LR、RL。

LL情况——右旋转

LL情况是指根节点的左子节点的左子树高度比右子树高度大2的情况。即：
LL
图中A节点为根节点。

进行一次右旋转即可使树重新平衡。

RR情况——左旋转

RR情况是指根节点的右子节点的右子树高度比左子树高度大2的情况。即：
RR
图中A节点为根节点。

进行一次左旋转即可使树重新平衡。

LR情况——先左旋转，再右旋转

LR情况是指根节点的左子节点的右子树比左子树高度大2的情况。即：
LR
图中A节点为根节点。

此时需进行两次旋转：

  • 先以左子节点（B）为根进行一次左旋转。（将情况转化为LL情况）
  • 再以A节点为根进行一次右旋转。

RL情况——先右旋转，再左旋转

RL情况是指根节点的右子节点的左子树比右子树高度大2的情况。即：
RL
图中A节点为根节点。

此时需进行两次旋转：

  • 先以右子节点（B）为根进行一次右旋转。（将情况转化为RR情况）
  • 再以A节点为根进行一次左旋转。

AVL树的操作

在AVL树上操作主要有三种：增加、删除、查找。

三种操作与二叉搜索树上对应的三种操作基本相同，只是增加、删除操作有可能会引起树的不平衡，需要进行额外调整。

为便于说明，此处先对AVL树结构进行说明：

  1. class AVLTree {
  2.   private:
  3.     class AVLTreeNode {
  4.       public:
  5.         int val;              /// 当前节点所存的数值
  6.         int height;           /// 当前节点的高度
  7.         AVLTreeNode* left;    /// 左子树
  8.         AVLTreeNode* right;   /// 右子树
  10.         // 得到root节点的高度
  11.         static int Height(AVLTreeNode* root);
  13.         AVLTreeNode(int val = 0);
  14.         ~AVLTreeNode();
  15.     };
  17.     // 内部树结构
  18.     AVLTreeNode* root;
  20.     // 计算root节点的高度
  21.     void CalcHeight(AVLTreeNode* root);
  23.     // 取得以root为根的树上的最大值节点
  24.     AVLTreeNode* FindMax(AVLTreeNode* root);
  26.     // 取得以root为根的树上的最小值节点
  27.     AVLTreeNode* FindMin(AVLTreeNode* root);
  29.     // LL情况，以root为根进行右旋转
  30.     AVLTreeNode* RotateLL(AVLTreeNode* root);
  31.     // LR情况，先以root节点左儿子为根进行左旋转，再以root为根进行右旋转
  32.     AVLTreeNode* RotateLR(AVLTreeNode* root);
  33.     // RR情况，以root为根进行左旋转
  34.     AVLTreeNode* RotateRR(AVLTreeNode* root);
  35.     // RL情况，先以root节点右儿子为根进行右旋转，再以root为根进行左旋转
  36.     AVLTreeNode* RotateRL(AVLTreeNode* root);
  38.     // 向AVL树内插入值为val的一个节点，返回插入该节点后，整个树的根节点
  39.     // result返回插入结果，成功插入则返回1，如果该值已经存在则返回0
  40.     AVLTreeNode* Insert(AVLTreeNode* root, int val, int& result);
  42.     // 在AVL树中删除值为val的节点，如果不存在则跳过，返回删除该节点后，整个树的根节点
  43.     // result返回删除结果，成功删除则返回1，如果该值不存在则返回0
  44.     AVLTreeNode* Remove(AVLTreeNode* root, int val, int& result);
  46.     // 在AVLTree销毁时，递归释放整颗树
  47.     void DeleteRoot(AVLTreeNode* root);
  49.     // 中序遍历整颗树
  50.     void Print(AVLTreeNode* root);
  52.   public:
  53.     AVLTree();
  54.     ~AVLTree();
  56.     // 向AVL树内插入值为val的一个节点，若成功插入则返回1，若已存在些节点则返回0
  57.     int Insert(int val);
  58.     // 在AVL树中删除值为val的节点，若成功删除则返回1，若该节点不存在则返回0
  59.     int Remove(int val);
  60.     // 在AVL树中查找值为val的节点，该节点存在则返回1，否则返回0
  61.     int Find(int val);
  63.     // 中序遍历整颗树
  64.     void Print();
  65. };

其中两个辅助函数具体实现为：

  1. int AVLTree::AVLTreeNode::Height(AVLTreeNode* root) {
  2.     // 返回当前节点的高度，若为空则返回-1
  3.     return root ? root->height : -1;
  4. }
  1. void AVLTree::CalcHeight(AVLTreeNode* root) {
  2.     // 当前节点的高度为左、右子树最高者高度 + 1
  3.     root->height = std::max(AVLTree::AVLTreeNode::Height(root->left),
  4.                             AVLTree::AVLTreeNode::Height(root->right)) +
  5.                    1;
  6. }

插入

主要分4步：

  • 寻找到插入的位置。（如果值已经存在则插入失败）
  • 创建节点并插入。
  • 如果插入操作引起了不平衡，进行调整。
  • 回溯时计算出沿插入路径上所有节点的新高度。

插入操作函数为：

  1. AVLTree::AVLTreeNode* AVLTree::Insert(AVLTreeNode* root, int val, int& result) {
  2.     result = 0;
  3.     // 如果当前节点为空，则返回一个新建的节点
  4.     if (!root) {
  5.         root = new AVLTreeNode(val);
  6.         result = 1;
  7.         return root;
  8.     }
  10.     // 当前节点值比要插入的值大，则应向左子树进行插入
  11.     if (root->val > val) {
  12.         // 向左子树插入值为val的节点
  13.         root->left = Insert(root->left, val, result);
  15.         // 如果在向左子树插入节点后，引起了树的不平衡（即左子树比右子树高2个单位），则需进行旋转调整
  16.         // 因为是向左子树插入，所以左子树的高度必定大于等于右子树的高度
  17.         if (AVLTreeNode::Height(root->left) -
  18.                 AVLTreeNode::Height(root->right) ==
  19.             2) {
  20.             // 如果是插入的左子节点的左子树，则对应LL情况，只需进行右单旋转即可
  21.             if (val < root->left->val) root = RotateLL(root);
  22.             // 否则为LR情况，需进行两次旋转
  23.             else
  24.                 root = RotateLR(root);
  25.         }
  26.     }
  27.     // 当前节点值比要插入的值小，则应向右子树进行插入
  28.     else if (val > root->val) {
  29.         // 向左子树插入值为val的节点
  30.         root->right = Insert(root->right, val, result);
  32.         // 如果在向右子树插入节点后，引起了树的不平衡（即右子树比左子树高2个单位），则需进行旋转调整
  33.         // 因为是向右子树插入，所以右子树的高度必定大于等于左子树的高度
  34.         if (AVLTreeNode::Height(root->right) -
  35.                 AVLTreeNode::Height(root->left) ==
  36.             2) {
  37.             // 如果是插入的右子树的右子树，则对应RR情况，只需进行左单旋转即可
  38.             if (val > root->right->val) root = RotateRR(root);
  39.             // 否则为RL情况，需进行两次旋转
  40.             else
  41.                 root = RotateRL(root);
  42.         }
  43.     }
  45.     // 回溯时计算出沿插入路径上所有节点的新高度
  46.     CalcHeight(root);
  47.     return root;
  48. }

由于高度是通过回溯进行更新的，所以当插入完成后，以root为根的左右子树的高度均以更新完成，只需要用左右子树新的高度差即可判断出是否不平衡。

如果不平衡，通过插入值val与root节点值的相对大小即可判断出相应的不平衡的类型。进行对应的操作即可。

删除

与插入类似，也分为4步：

  • 寻找到要删除的节点的位置。（如果值不存在则删除失败）
  • 如果对应节点只有一个子节点，直接删除；若有两个子节点，则需找出对应的替代节点之后，再进行删除。
  • 如果删除操作引起了不平衡，进行调整。
  • 回溯时计算出沿删除路径上所有节点的新高度。

具体实现如下：

  1. AVLTree::AVLTreeNode* AVLTree::Remove(AVLTreeNode* root, int val, int& result) {
  2.     result = 0;
  3.     if (!root) {
  4.         return nullptr;
  5.     }
  6.     // 待删除节点位于右子树
  7.     if (root->val < val) {
  8.         // 在右子树中删除节点
  9.         root->right = Remove(root->right, val, result);
  10.         // 如果删除后引起了树的不平衡（即左子树的高度与右子树的高度差为2），则需要进行旋转调整
  11.         if (AVLTreeNode::Height(root->left) -
  12.                 AVLTreeNode::Height(root->right) ==
  13.             2) {
  14.             // 如果右儿子的左子树的高度小于右儿子的右子树的高度，
  15.             // 则删除的节点位于右儿子的左子树上，不平衡情况对应RR，
  16.             // 进行左旋转即可
  17.             if (AVLTreeNode::Height(root->right->left) <
  18.                 AVLTreeNode::Height(root->right->right))
  19.                 root = RotateRR(root);
  20.             // 否则删除的节点位于右儿子的右子树上，不平衡情况对应RL，
  21.             // 需进行两次旋转
  22.             else
  23.                 root = RotateRL(root);
  24.         }
  25.     }
  26.     // 待删除节点位于左子树
  27.     else if (root->val > val) {
  28.         // 在左子树中删除节点
  29.         root->left = Remove(root->left, val, result);
  31.         // 如果删除后引起了树的不平衡（即右子树的高度与左子树的高度差为2），则需要进行旋转调整
  32.         if (AVLTreeNode::Height(root->right) -
  33.                 AVLTreeNode::Height(root->left) ==
  34.             2) {
  35.             // 如果左儿子的右子树的高度小于左儿子的左子树的高度，
  36.             // 则删除的节点位于左儿子的右子树上，不平衡情况对应LL，
  37.             // 进行右旋转即可
  38.             if (AVLTreeNode::Height(root->left->right) <
  39.                 AVLTreeNode::Height(root->left->left))
  40.                 root = RotateLL(root);
  41.             // 否则删除的节点位于左儿子的左子树上，不平衡情况对应LR，
  42.             // 需进行两次旋转
  43.             else
  44.                 root = RotateLR(root);
  45.         }
  46.     }
  47.     // 否则应当删除当前节点
  48.     else {
  49.         result = 1;
  50.         int t;
  51.         // 当前节点有两个子节点，则从中选取高度大的一个子树进行替代，避免引起树的不平衡
  52.         if (root->left && root->right) {
  53.             // 左子树高度大于右子树时，选取左子树中最大值替代当前节点，并删除原最大值节点
  54.             if (AVLTreeNode::Height(root->left) >
  55.                 AVLTreeNode::Height(root->right)) {
  56.                 AVLTreeNode* temp = FindMax(root->left);
  57.                 root->val = temp->val;
  58.                 root->left = Remove(root->left, temp->val, t);
  59.             }
  60.             // 否则，选取右子树中最小值替代当前节点，并删除原最小值节点
  61.             else {
  62.                 AVLTreeNode* temp = FindMin(root->right);
  63.                 root->val = temp->val;
  64.                 root->right = Remove(root->right, temp->val, t);
  65.             }
  66.         }
  67.         // 如果当前节点只有一个子节点或没有子节点，直接删除即可
  68.         else {
  69.             AVLTreeNode* temp = root;
  70.             root = root->left ? root->left : root->right;
  71.             delete temp;
  72.         }
  73.     }
  75.     // 如果返回节点不为空时，回溯地计算出删除路径上所有节点的新高度
  76.     if (root) CalcHeight(root);
  77.     return root;
  78. }

其中两个辅助函数实现如下：

  1. AVLTree::AVLTreeNode* AVLTree::FindMax(AVLTreeNode* root) {
  2.     if (!root) return nullptr;
  3.     AVLTreeNode* temp = root;
  4.     while (temp->right) temp = temp->right;
  5.     return temp;
  6. }
  1. AVLTree::AVLTreeNode* AVLTree::FindMin(AVLTreeNode* root) {
  2.     if (!root) return nullptr;
  3.     AVLTreeNode* temp = root;
  4.     while (temp->left) temp = temp->left;
  5.     return temp;
  6. }

与插入类似，通过高度差判断是否不平衡，通过相对值大小判断具体不平衡类型。

查找

与二叉搜索树查找相同，不再赘述。

相同值的处理

上述结构仅支持序列中没有相同值的情况，如果存在一组有相同值的序列，并且想将相同的值都存储下来，则需要对此结构进行一些修改。

一种办法是在AVLTreeNode结构中添加一个indexs属性用于存储对应值在原序列中的位置，如果插入时值相同，则向indexs中添加对应的位置编号。

附注

文中完整代码请参考：https://github.com/anscor/BlogCode/tree/master/AVLTree。

另附两个数据结构的可视化网站，在进行较为抽象的数据结构与算法学习时，可以用于直观地检验自己编写代码的正确性：

参考

  1. https://zh.wikipedia.org/wiki/AVL%E6%A0%91
  2. https://gaomf.cn/2017/02/11/Data_Structure_AVLTree/