AVL树的概念
首先抛出一个问题 为什么AVL树会诞生呢？
还记不记得我们在学习二叉搜索树最后总结的时候说的一句话
在二叉搜索树是完全二叉树的情况下效率最高 此时的效率是 LogN
在二叉搜索时是单边树的情况下效率最差 此时效率退化至 N
为了解决这个退化的效率问题 AVL树诞生了
AVL树是由两位俄国科学家G.M. Adelson-Velsky和E.M.Landis在1962年发明的。他们在一篇论文中提出了AVL树这一概念，并将其命名为"AVL树"，以纪念他们的姓氏的首字母。
AVL树是一种自平衡二叉搜索树，它能够保证插入、删除和查找操作的时间复杂度都是O(log n)，因此在很多场合下都很有用。
AVL树可以是一颗空树 也可以是具有以下性质的一颗二叉搜索树
1 它的左右子树都是AVL树
2 树的左右子树高度差不超过一 （以下样例均为右子树减左子树）
上面就是一棵AVL树
蓝色数字表示的是左右子树的高度差值(以下简称平衡因子) 它们都是不超过1的
红色的数字表示储存数据的值 符合二叉搜索树的性质
我们可以发现 当一颗二叉搜索树是AVL树的时候 假设它一共有N个节点 那么它的高度非常接近LogN 同样的搜索效率也接近LogN
这也就解决了单边树的低效问题
AVL树节点类的定义
我们这里使用KV模型来实现AVL树
为了方便后续的操作 使用三叉链结构来完成它
一个节点除了指向它的左右两个子节点之外还指向它的父节点 一共三个指针 所以称为三叉链
此外 我们还增加一个int类型的数据 来记录平衡因子
代码表示如下
template<class K, class V> struct AVLTreeNode { // 三叉连 AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; // 平衡因子 int _bf; // 储存的键值对 pair<K, V> _kv; // 构造函数 AVLTreeNode(const pair<K , V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_bf(0) //因为构造出来之后没有左右子树 所以说平衡因子为0 {} };
AVL树的插入
AVL树的插入满足下面几个步骤
1 遵循二叉搜索树的插入原则 找到待插入位置
2 找到插入位置之后 插入节点
3 更新平衡因子 如果平衡因子不满足AVL树的条件 则使之满足
第一步第二步很简单 如果还有不明白的同学可以参考这篇博客
二叉搜索树的实现
接下来我们重点学习第三步
由于我们插入一个节点之后 只有可能是这个节点的父节点的高度受到影响
所以说我们只需要更新它的祖先节点 这也是我们为什么设计成三叉链结构的原因 - 方便找祖先节点
（这个图稍微有点漏洞 我们这里假设新增的节点是6.5 前面的节点都是浮点数）
新增节点之后我们开始更新平衡因子 遵循下面的规则
1 如果新增节点在父节点的右边 则平衡因子++
2 如果新增节点在父节点的左边 则平衡因子–
这里我们可以发现 如果有一个父节点的平衡因子更新成了0 则无需向上继续更新了
怎么解释这个现象呢？
我们都知道 平衡因子是根据父节点左右子树的高度来确定的
如果父节点的平衡因子被更新成了0 那么肯定就说明 原来有一边的高度是大于另一边的 而且是大于1
插入一个新的节点之后两边的高度差就被填平了
那么对于父节点的父节点来说 这边子树的高度并没有变化 所以说我们不需要向上更新了
所以说我们有具体的规则如下
如果父节点的平衡因子更新之后结果为1或者-1 则需要继续向上更新祖先节点的平衡因子
如果父节点的平衡因子更新之后结果为0 则不需要继续向上更新祖先节点的平衡因子
如果父节点的平衡因子更新之后结果为2或者-2 则需要进行旋转操作来处理异常
我们假设目前的节点是cur 它的父节点是parent
因为我们执行的是插入操作 所以说我们的节点肯定是增加的 就看增加的是父节点的左子树还是右子树
因为我们不能确定是左子树还是右子树 所以要执行判断
如果cur是parent的左节点 则平衡因子–
如果cur是parent的右节点 则平衡因子++
但是到这里还没完 我们要需要继续向上更新 执行下面的代码
cur = parent; parent = parent->_parent;
最差的情况下 我们一直要更新到根节点
按照上面的规则 我们写出代码
bool insert(const pair <K,V>& kv) { if (_root == nullptr) // 如果AVL树为空 则直接为其根节点 { _root = new Node(kv); return true; } // 如果不为空 则按照二叉树的插入方式 通过key值 即first来比较 Node* cur = _root; // cur确定当前位置 Node* parent = nullptr; // parent最后连接用 while (cur) // 当cur不为空的时候一直走 { if (kv.first > cur->_kv.first) // 如果插入值大于当前节点 向右移 { cur = cur->_right; parent = cur; } else if (kv.first < cur->_kv.first) // 如果插入值小于当前节点 向右移 { cur = cur->_left; parent = cur; } else // 到这里这种情况说明等于 则插入失败 返回false { return false; } } // 将待插入节点插入到树中 cur = new Node(kv); // 根据kv的key值来分辨插入的是左子树还是右子树 if (kv.first > parent->_kv.first) { parent->_right = cur; cur->_parent = parent; // 因为是三叉链 所以要更新父节点 } else // 因为走到这里了kv的key值不可能相等 所以说else就表示小于 { parent->_left = cur; cur->_parent = parent; // 因为是三叉链 所以要更新父节点 } // 更新平衡因子 while (cur != _root) // 最坏的情况 一直更新到根节点 但是cur不可能到根节点 { // 如果是右则平衡因子++ 反之则-- if (cur = parent->_left) { parent->_bf--; } else if (cur = parent->_right) { parent->_bf++; } // 平衡因子更新完毕 此时开始查看父亲节点的平衡因子是多少 是否结束 是否需要旋转 if (parent->_bf == 0) // 如果父亲的平衡因子是0 则停止更新 直接返回 { return true; } else if (parent->_bf == 1 || parent->_bf == -1) // 如果父亲的平衡因子是1或-1 则继续往上更新 { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) // 如果父亲的平衡因子是2或-2 则进行旋转操作 { // 旋转 } } }
省略了旋转操作的插入代码就在上面 接下来我们重点研究下AVL的旋转操作
AVL树的旋转
首先我们要明确一点 当parent节点的平衡因子是2或者-2时候 cur的平衡因子必然是1或者-1
因为如果cur的平衡因子是0 有两种情况
cur为新增节点 这个时候由于我们插入的是AVL树 所以其父节点只有可能是1 -1 或者0
cur为更新后的节点 此时cur为其子节点的父节点 其平衡因子更新到了0 不会继续向上更新 所以cur的父节点一定是有正常的平衡因子 1 -1 或者0
所以说我们这里就有四种情况
parent的平衡因子是2 cur的平衡因子是1
parent的平衡因子是2 cur的平衡因子是-1
parent的平衡因子是-2 cur的平衡因子是1
parent的平衡因子是-2 cur的平衡因子是-1
然后我们根据这四种情况来讨论如何旋转
左单旋
从上图我们可以观察发现 parent的平衡因子被更新为了2 此时肯定要触发旋转
旋转后的图片大概是这样子
经过旋转后 平衡因子全部恢复正常 并且此时将这颗二叉树作为一个整体 它的高度还是h+2
所以不用继续往上更新平衡因子了
那么我们具体来看看实现左单旋要分几步
1 让 subr 左子树 subrl 成为 parent 的右子树
2 让 parent 成为 subr 的左子树
3 让 subr 作为整个子树的根 （如果parent不是根节点的话）
4 更新平衡因子
此时 subr 和 parent 的平衡因子都更新为0
而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的
此外 观察第一张图我们可以知道
左单旋对应着 parent的平衡因子是2 cur的平衡因子是1 这种情况
我们左单旋的代码表示如下
void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* grandparent = parent->_parent; // 建立subR和parent的联系 subR->_left = parent; parent->_parent = subR; // 建立parent和subRL的联系 parent->_right = subRL; if (subRL) // 有可能subRL为空 { subRL->_parent = parent; } // 建立grandparent和sunR的联系 // 这里要分grandparent是否存在以及parent是grandparent的左还是右 if (grandparent) // 如果进去了 则说明grandparent存在 { // 如果存在 要分清楚parent在左边还是右边 if (grandparent->_left == parent) { grandparent->_left = subR; } else { grandparent->_right = subR; } subR->_parent = grandparent; } // 否则就是不存在 我们更新_root 并且将subR的父节点置空 else { _root = subR; subR->_parent = nullptr; } // 更新平衡因子 subR->_bf = 0; parent->_bf = 0; }
只要按照上面的步骤一行行写 应该是不难理解的
这里尤其要注意的是 我们使用的是不熟悉的三叉链结构
右单旋
从上图我们可以观察发现 parent的平衡因子被更新为了-2 此时肯定要触发旋转
旋转后的图片大概是这样子
经过旋转后 平衡因子全部恢复正常 并且此时将这颗二叉树作为一个整体 它的高度还是h+2
所以不用继续往上更新平衡因子了
那么我们具体来看看实现右单旋要分几步
1 让 subl 的右子树 sublr 成为 parent 的左子树
2 让 parent 成为 subl 的左子树
3 让 subr 作为整个子树的根 （如果parent不是根节点的话）
4 更新平衡因子
此时 subl 和 parent 的平衡因子都更新为0
而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的
此外 观察第一张图我们可以知道
右单旋对应着 parent 的平衡因子是-2 cur 的平衡因子是-1 这种情况
我们右单旋的代码表示如下
void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* grandparent = parent->_parent; // 建立subL和parent之间的联系 subL->_right = parent; parent->_parent = subL; // 建立parent和subLR之间的联系 parent->_left = subLR; if (subLR) // subLR可能不存在 { subLR->_parent = parent; } // 建立grandparent和subl之间的联系 // 这里要分grandparent是否存在以及parent是grandparent的左还是右 if (grandparent) { // 如果存在 要分清楚parent在左边还是右边 if (grandparent->_left == parent) { grandparent->_left = subL; } else { grandparent->_right = subL; } subL->_parent = grandparent; } else // 这里就是表示parent就是根节点 { _root = subL; subL->_parent = nullptr; } // 更新平衡因子 subL->_bf = 0; parent->_bf = 0; }
左右双旋
左右双旋一般分三步走 图片表示如下
第一步 插入新增节点 触发旋转机制
第二步 以30为旋转点进行左单旋
第三步 以90为旋转点进行右单旋
左右双旋的步骤如下
1 以subL为旋转点进行左单旋
2 以parent为旋转点进行右单旋
3 更新平衡因子
而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的
此外 观察第二张图我们可以知道
左右双旋对应着 parent 的平衡因子是-2 cur 的平衡因子是1 这种情况
左右双旋后 平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况
1 当sublr的平衡因子是-1时 左右双旋后parent subl sublr的平衡因子分别更新为 1 0 0
2 当sublr的平衡因子是 1时 左右双旋后parent subl sublr的平衡因子分别更新为 0 -1 0
3 当sublr的平衡因子是 0时 左右双旋后parent subl sublr的平衡因子分别更新为 0 0 0
产生这三种情况的原因分别是
插入的节点可能是sublr 的左子树 右子树 或者是sublr本身
代码表示如下
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = parent->_left->_right; int bf = subLR->_bf; // 以subL作为旋转点左单旋 RotateL(subL); // 以parent作为旋转点右单旋 RotateR(parent); // 平衡因子 if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == -1) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false); } }
右左单旋
右左双旋一般分三步走 图片表示如下
第一步 插入新增节点 触发旋转机制
第二步 以90作为节点进行右单旋
第三步 以30作为节点进行左单旋
右左双旋的步骤如下
1 以subR为旋转点进行右单旋
2 以parent为旋转点进行左单旋
3 更新平衡因子
而由于二叉搜索树的性质 所有的节点是从小到大排列的 我们这个旋转并没有改变这个性质 所以说这个旋转是完全合法的
此外 观察第二张图我们可以知道
右左双旋对应着 parent 的平衡因子是2 cur 的平衡因子是-1 这种情况
右左双旋后 平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况
1 当subrl的平衡因子是-1时 左右双旋后parent subr subrl的平衡因子分别更新为 1 0 0
2 当subrl的平衡因子是-1时 左右双旋后parent subr subrl的平衡因子分别更新为 0 -1
3 当subrl的平衡因子是-1时 左右双旋后parent subr subrl的平衡因子分别更新为 0 0 0
产生这三种情况的原因分别是
插入的节点可能是subrl 的左子树 右子树 或者是subrl本身
代码表示如下
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; // 以subR为轴进行右单旋 RotateR(subR); // 以parent为轴进行左单旋 RotateL(parent); // 更新平衡因子 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 if (bf == 0) { subRL->_bf = 0; parent->_bf = 0; subR->_bf = 0; } else { assert(false); } }
AVL树的验证
首先AVL树是一颗二叉搜索树 所以说它满足中序遍历后是有序的这个原则 我们可以使用中序遍历来验证
代码表示如下
void _Inorder(Node* root) { if (root == nullptr) { return; } _Inorder(root->_left); cout << root->_kv.first << " "; _Inorder(root->_right); } void Inorder() { _Inorder(_root); }
但是中序遍历只能证明这棵树是二叉搜索树 要证明它是AVL树我们必须还要证明它的平衡因子全部无异常
我们可以从根节点开始 往上遍历每个子树来判断它是否是AVL树 如果全部是AVL树 则可以验证
如果有一颗不是 则证明不是AVL树
//判断是否为AVL树 bool IsAVLTree() { int hight = 0; //输出型参数 return _IsBalanced(_root, hight); } //检测二叉树是否平衡 bool _IsBalanced(Node* root, int& hight) { if (root == nullptr) //空树是平衡二叉树 { hight = 0; //空树的高度为0 return true; } //先判断左子树 int leftHight = 0; if (_IsBalanced(root->_left, leftHight) == false) return false; //再判断右子树 int rightHight = 0; if (_IsBalanced(root->_right, rightHight) == false) return false; //检查该结点的平衡因子 if (rightHight - leftHight != root->_bf) { cout << "平衡因子设置异常：" << root->_kv.first << endl; } //把左右子树的高度中的较大值+1作为当前树的高度返回给上一层 hight = max(leftHight, rightHight) + 1; return abs(rightHight - leftHight) < 2; //平衡二叉树的条件 }
AVL树的查找
AVL树的查找方式与二叉搜索树相同
1 如果树为空树 则查找失败 返回nullptr
2 如果key值小于当前节点 则进入当前节点的子树查找
3 如果key值大于当前节点 则进入当前节点的子树查找
4 如果key值等于当前节点 则返回当前节点
代码表示如下
Node* find(const K& key) { Node* cur = _root; while (cur) // 一直查找到空为止 { if (key < cur->_kv.first) // 小于 { cur = cur->_left; } else if (key < cur->_kv.first) // 大于 { cur = cur->_right; } else // 等于 { return cur } } // 走到这里就是没找到 return nullptr; }
AVL树的修改
我们所说的修改一般是值对于value值的修改
一般步骤如下
1 找到对应的key值的结点
2 对其value值进行修改
代码表示如下
bool Modify(const K& key, const V& value) { Node* ret = find(key); // 有可能不存在 if (ret == nullptr) { return false; } ret->_kv.second = value; return true; }
AVL树的删除
AVL树的删除满足下面几个步骤
1遵循二叉搜索树的删除原则 找到待删除位置
2找到删除位置之后 删除节点
3更新平衡因子 如果平衡因子不满足AVL树的条件 则使之满足
由于我们学习AVL树主要是为了后面的红黑树做铺垫 需要重点掌握的是AVL树的插入
并且AVL树的删除在平时的笔试面试中考察的很少 或者说几乎没有考察 所以同学们可以跳过这一部分的学习
AVL树的性能
AVL树是一颗近乎完全二叉树的二叉搜索树 所以说它查询的时间复杂度非常低 为Log N
但是如果要对于AVL树做一些结构修改的操作 它的性能就会十分低下 比如在插入和删除时 可能要经过大量的旋转操作
因此 如果是需要一种查询高效的数据结构 AVL树是十分合适的
但是 如果它经常要被修改 AVL树的性能就可能不太匹配了
![[数据结构]-AVL树](https://ucc.alicdn.com/pic/developer-ecology/6v24jawhpy3hi_6852840861db4926b08602d40f80e75a.jpeg?x-oss-process=image/resize,h_160,m_lfit)
