文章目录

• 📖 前言
• 1. AVL树的概念
• • • 1.1 二叉搜索树的缺点：
    • 1.2 AVL树的引入：
    • 1.2 AVL树的性质：
• 2. AVL树的模拟实现
• • • 2.1 AVL树结点的定义：
    • 2.2 AVL树的插入：（重点）
    • • 2.2.1 插入结点后平衡因子的变化
      • 2.2.2 插入结点后对其他结点衡因子的影响
      • 2.2.3 在不同位置插入情况分析处理
    • 2.3 AVL树的旋转操作：（重点）
    • • 2.3.1 左单旋
      • 2.3.2 右单旋
      • 2.3.3 左右双旋
      • 2.3.4 右左双旋
• 3. 验证AVL树
• • • 3.1 严格验证AVL树：

📖 前言

• 上一章节我们学习了二叉搜索树，并且模拟实现了二叉搜索树的实现。
• 在学习完之后我们知道二叉搜索树查找的时间复杂度是〇（N），这里并不是〇（logN） 具体的原因就是要搜索的二叉树并不是非常的平衡。
• 并不是所有要查找的二叉树都是满二叉树或者是完全二叉树，有可能是单边树的情况，平均下来的时间复杂度就是〇（N）。

前情回顾：二叉搜索树 👉 传送门

本章我们将学习AVL树，来解决上一章节二叉搜索树的查找时二叉树不平衡的问题，搬好小板凳准备开讲啦~~~ 🙋 🙋 🙋 🙋 🙋

1. AVL树的概念

1.1 二叉搜索树的缺点：

• 二叉搜索树虽可以减少查找的效率，但如果数据有序或接近有序时二叉搜索树将退化为单边树
• 这时查找元素相当于在顺序表中搜索元素，效率低下
• 而且如果二叉树查找是用递归实现的话，那么这种情况查找很有可能 会导致栈溢出（爆栈）！！！

1.2 AVL树的引入：

两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis（AVL树就是以这两位科学家的名字命名的）

在1962年发明了一种解决上述问题的方法：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

1.2 AVL树的性质：

首先AVL树是一棵二叉搜索树，一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是AVL树
• 任何一颗子树左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1 / 0 / 1）

平衡不是相等，与满二叉树和完全二叉树比较一下：（节点外数字代表平衡因子）

• 满二叉树： 保证每个子树高度差是0
• 完全二叉树： 最后一层缺一些结点
• AVL树： 最后两层缺一些结点

AVL树又叫高度平衡二叉搜索树。

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 〇（logN）搜索时间复杂度 〇（logN）。

2. AVL树的模拟实现

2.1 AVL树结点的定义：

• 直接实现key_value的结构 – 三叉链的形式（带父节点）

具体代码如下：

template
struct AVLTreeNode
{pair _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;AVLTreeNode(const pair& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};

• 平衡因子 —— bakance factor
• 右子树 – 左子树的高度差

AVL树并没有规定必须要设计平衡因子，只是一个实现的选择，方便控制平衡。

2.2 AVL树的插入：（重点）

• 这里的插入思路和二叉搜索树中插入的思路一致，找到合适的位置之后再链接

这里链接是比较容易的，但是链接之后对各个结点中的平衡因子的调整则是比较费劲的。

2.2.1 插入结点后平衡因子的变化

1. 首先我们来一段简单的逻辑 —— 只考虑父子之间关系：

• 当一个结点的左或者右链接了一个结点，该结点为链接结点的父节点
• 当该父节点的右边连接上孩子时，此时该父节点的右子树比左子树高了一层，平衡因子_bf + +
• 当该父节点的左边连接上孩子时，此时该父节点的左子树比右子树高了一层，平衡因子_bf – –

如图所示：

2.2.2 插入结点后对其他结点衡因子的影响

2. 插入一个结点对整个树的影响：

• 插入一个结点真正会影响的是其祖先的平衡因子的改变
• 同时插入一个结点对兄弟结点的平衡因子没有影响

如图所示：

2.2.3 在不同位置插入情况分析处理

3. 在链接新的结点的时候要满足AVL树的规则

(1)向上更新：

• 更新新插入节点祖先的平衡因子
• 没有违反规则就结束了，违反规则，不平衡了就需要处理
• 这里的处理是旋转处理（接下来会重点介绍）
• 在更新的过程中只要是发现违反了AVL树规则的就需要旋转处理

(2)如何向上更新：

• 更新的方式是沿着祖先路径更新（回溯）
• 将parent结点更新到它的_parent位置上，将cur结点更新到它的_parent位置上
• 在这个过程中一旦发现有违反AVL树规则的时即parent的平衡因子变成2或-2时
• 这时就需要进行旋转处理

具体过程如下：

• 子树高度变了，就要继续往上更新
• 子树的高度不变, 则更新完成
• 子树违反平衡规则，则停止更新, 旋转子树

情况一：

• 原来是 1 or -1 --> 0 （插入结点填在了矮的那一边）

情况二：

• 原来是 0 --> 1 or -1 （插入结点导致一边变高了）

• 当parent->_bf == 1时

• 当parent->_bf == -1时

情况三：

• 一定要检查，不保证其他地方不会出现错误
  

我们讨论问题要将各个方面的都要考虑到位才行，即使前面都正确是不会走到这一步的，但是为了万无一失还是要将这一步写上。

情况四：

• 当插入的位置满了时

具体代码如下：

bool Insert(const pair& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_bf = 0;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}//找到符合规则的位置之后再插入cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//三叉链的链接 -- 链上父节点cur->_parent = parent;while (parent){if (cur == parent->_right){parent->_bf++;}else if (cur == parent->_left){parent->_bf--;}//是否继续更新if (parent->_bf == 0) //原来是 1 or -1 --> 0 （插入结点填在了矮的那一边）{//高度不变，更新结束break;}else if(parent->_bf == 1 || parent->_bf == -1)//原来是 0 --> 1 or -1 （插入结点导致一边变高了）{//子树的高度变了，继续更新祖先cur = cur->_parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//原来是 1 or -1 --> 2 or -2 （插入结点导致本来高的一边又变高了）{//子树不平衡了 -- 需要旋转处理（左单旋的特征 -- 右边高）if (parent->_bf == 2 && cur->_bf == 1)//左单旋{RatateL(parent);}//子树不平衡了 -- 需要旋转处理（右单旋的特征 -- 左边高）else if (parent->_bf == -2 && cur->_bf == -1)//右单旋{RatateR(parent);}else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋{RatateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋{RatateRL(parent);}//旋转完之后ppNode为根的子树高度不变 -- 所以对ppNode的平衡因子没有影响break;}else // 一定要检查 -- 不保证其他地方不会出现错误{//插入之前AVL数就存在平衡子树，|平衡因子| >= 2结点assert(false);}}return true;
}

2.3 AVL树的旋转操作：（重点）

上述我们已经阐述了，在什么情况下需要对AVL树进行旋转操，接下来我们就来讲一下具体的旋转步骤。

旋转原则：

• 保持搜索树的规则
• 子树变平衡

旋转一共分为四种旋转方式：

• 左单旋、右单旋
• 左右双旋、右左双旋

2.3.1 左单旋

当右子树高的时候，这时就要向左旋转。

旋转过程：

• 将要旋转的子树的根节点设为parent，根结点的右子树为subR，subR的左节点为subRL
• 将subRL给parent的右，再将parent给subR的左
• 改变其链接关系即可
• 这样一来subR做了子树的根，根结点的左右子树高度差从2变成了0

旋转详情图：

• 代表所有情况的抽象图、长方形条表示的是子树

原理：

• 左旋转的目的是将左子树变高
• 本来右子树高，向左旋转之后，将左子树和右子树变得一样高
• 根节点的右子树的所有结点肯定比根结点大
• 所以subRL可以放在parent->left
• subRL肯定比subR小，parent也比subR小
• 所以都可以放在subR的左边

代表所有情况的抽象图长方形条表示的是子树

下面来讨论一下h

• h == 0时
  
• h == 1时

此时有两种情况，新增的节点有可能是链接在这棵树最右边结点的，左边也有可能是链接在右边

• h == 2时

此时一共有36种情况

解释：

• 因为是左单旋，所以这棵树的最左边一定是高度为二的满二叉树
• 不然要是用其余两种非满二叉树的情况，肯可能空白的子树都已经不满足AVL树了，局部子树就要旋转了
• 一共有三个位置插入空白子树，最后一个已经定下来了，所以还剩两个位置
• 剩下的两个位置每个位置能有三种空白子树可以选择，所以是3 * 3一共9种
• 固定下来的空白子树可以新增结点的位置一共有4处
• 所以综上所述一共有9 * 4一共36种

• h == 3时
  ……

• 此时一定是比h == 2时候的情况更复杂
• 所以层数越高，情况就越多
• 所以我们用长方形代替了子树

具体代码如下：

//右边高就要左旋转
//左单旋
void RatateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL != nullptr){subRL->_parent = parent;}Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (parent == ppNode->_left){ppNode->_left = subR;}else if(parent == ppNode->_right){ppNode->_right = subR;}subR->_parent = ppNode;}//更新平衡因子parent->_bf = 0;subR->_bf = 0;
}

同时代码的一些细节也是需要把控的

• subRL可能是nullptr空指针，要加以判断不然会引起非法访问
• parent有可能就是树的根，parent也有可能只是整个树的局部子树
• 所以要将parent->_parent先保存起来，方便之后的链接工作

2.3.2 右单旋

当左子树高的时候，这时就要向右旋转。

旋转详情图：

旋转过程：

• 过程和原理与左单旋过程类似，可以参考左单旋过程

与左单旋一样当讨论h时，也能分出很多种，h = 1时是2种，h = 2时36种。

具体代码如下：

//左边高就要右旋转
//右单旋
void RatateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR != nullptr){subLR->_parent = parent;}Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else if (ppNode->_right == parent){ppNode->_right = subL;}subL->_parent = ppNode;}//更新平衡因子subL->_bf = 0;parent->_bf = 0;
}

细节把控也与左单旋类似可以参考左单旋。

2.3.3 左右双旋

光有左右单旋是解决不了所有问题的，如图所示就是特殊情况：

如图所示，很显然右单旋并没有解决问题，旋转之后仍然不是AVL树，此时我们就引入了双旋：

旋转详情图：

同样可以对h进行讨论，也会对应很多种情况，不再一 一赘述。

具体代码如下：

//左右双旋
void RatateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RatateL(parent->_left);RatateR(parent);//更新平衡因子 -- 全是0的情况也要单独写，不要依赖单旋if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{//subLR->_bf旋转前就有问题assert(false);}
}

• 我们在实现双旋的时候可以复用单旋
• 但是单旋有个坑，会出现将平衡因子搞成0的情况

两种解决方案：

• 将单旋中更新的平衡因子拿出来
• 旋转之前将位置记录下来

我们采用第一种方法，单独将平衡因子拿出来处理。

2.3.4 右左双旋

旋转详情图：

同样的右左双旋和左右双旋差不多，可以参考上文。

具体代码如下：

//右左双旋
void RatateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RatateR(parent->_right);RatateL(parent);if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else{//subLR->_bf旋转前就有问题assert(false);}
}

3. 验证AVL树

我们先增加几个成员函数：

1.层序遍历打印树

void levelOrder()
{vector> vv;if (_root == nullptr){return;}queue q;int levelSize = 1;q.push(_root);while (!q.empty()){//levelSize控制一层一层出vector levelV;while (levelSize--){Node* front = q.front();q.pop();levelV.push_back(front->_kv.first);if (front->_left != nullptr){q.push(front->_left);}if (front->_right != nullptr){q.push(front->_right);}}vv.push_back(levelV);for (auto e : levelV){cout << e << " ";}cout << endl;//上一层出完，下一层就都进队列levelSize = q.size();}
}

2.中序遍历二叉树：

void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);
}void InOrder()
{_InOrder(_root);cout << endl;
}

3.求二叉树高度：

int _Height(Node* root)
{if (root == nullptr){return 0;}//后续的方式int lh = _Height(root->_left);int rh = _Height(root->_right);return lh > rh ? lh + 1 : rh + 1;
}int Height()
{return _Height(_root);
}

验证一：

void TestAVLTree()
{//升序 -- 右边高左单旋//int arr[] = { 1,2,3,4,5,6,7,8 };//降序 -- 左边高右单旋int arr[] = { 8,7,6,5,4,3,2,1 };AVLTree t;for (auto e : arr){t.Insert(make_pair(e, e));}t.levelOrder();
}

如图所示的两棵树均是满足AVL树，但是这这种验证还是不太严谨。

3.1 严格验证AVL树：

• 在插入一个结点之后，验证该棵树的每一棵子树是否都满足AVL树的规则：

bool _IsBalanceTree(Node* root)
{//空树也是AVL树if (nullptr == root)return true;//计算pRoot节点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//求差值int diff = rightHeight - leftHeight;//如果计算出的平衡因子与pRoot的平衡因子不相等，或者//pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "结点平衡因子异常" << endl;return false;}//平衡因子没有异常但是和结点的对不上if (diff != root->_bf){//说明更新有问题cout << root->_kv.first << "结点平衡因子不符合实际" << endl;return false;}//pRoot的左和右如果都是AVL树，则该树一定是AVL树//把自己和自己的左右子树都检查了，递归检查return _IsBalanceTree(root->_left)&& _IsBalanceTree(root->_right);
}bool IsBalanceTree()
{return _IsBalanceTree(_root);
}

• 通过递归的方式将整棵树的子树都验证一遍。

验证二：

• 我们插入随机值，这样更具有普遍性
• 顺序插入我们也顺便实验一下

void TestAVLTree()
{const size_t N = 1024 * 1024 * 10;vector arr;arr.reserve(N);//避免频繁扩容srand(time(0));for (size_t i = 0; i < N; i++){arr.push_back(rand());//arr.push_back(i);}AVLTree t;for (auto e : arr){t.Insert(make_pair(e, e));}cout << "是否平衡？" << t.IsBalanceTree() << endl;cout << "高度：" << t.Height() << endl;//t.InOrder();
}