平衡二叉搜索树之 AVL 树的模拟实现【C++】
文章目录
AVL树的简单介绍
我上一篇文章提到的普通二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
AVL树就可以解决上述问题，让搜索树的查找效率在任何情况下都能稳定是O(logN)
AVL树解决上述问题的方法是：
保证每个结点的左右子树高度之差的绝对值不超过1
这样就能保证树中的节点分布接近满二叉树，高度非常接近logN【N为树中节点的个数】，进而让一次查找的效率为O(logN)
为什么是保证每个结点的左右子树高度之差的绝对值不超过1，而不是保证左右子树高度一样呢？
其实很简单：
因为在一些情况下绝对不可能做到左右子树高度一样，例如：
此时无论如何改变树的形态，都不可能做到每个结点的左右子树高度相等
综上：
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1
全部的实现代码放在了文章末尾
准备工作
创建两个文件，一个头文件AVLTree.hpp，一个源文件test.cpp
【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件AVLTree.hpp中】
- AVLTee.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义
- test.cpp：存放main函数，以及测试代码
包含头文件
- iostream：用于输入输出
- cmath:提供数学函数
类的成员变量
实现AVL树最主要的就是保证树中节点的左右子树高度差不超过1
而维护这一条件的方法并不是唯一的，我使用的是平衡因子来维护
平衡因子时每个节点都有的，它的值就是这个节点的左右子树高度之差【一般是右子树高度-左子树高度】
构造函数和拷贝构造
构造函数没什么好说的，默认构造就行了
AVLTree():_root(nullptr){ }拷贝构造：
因为节点都是从堆区new出来的，所以要深拷贝
使用递归实现深拷贝：
因为拷贝构造不能有多余的参数，但是递归函数又必须使用参数记录信息
然后在拷贝构造里面调用一下这个函数就行了
AVLTree(const AVLTree& obj){ 根节点的父亲节点是nullptr _root =Copy(obj._root,nullptr);}swap和赋值运算符重载
交换两颗二叉搜索树的本质就是交换两颗数的资源（数据），而它们的资源都是从堆区申请来的，然后用指针指向这些资源
并不是把资源存储在了二叉搜索树对象中
所以资源交换很简单，直接交换_root指针的指向即可
voidSwap(AVLTree& obj){ std::swap(_root, obj._root);}赋值运算符重载
AVLTree&operator=(AVLTree obj){ this->Swap(obj);return*this;}为什么上面的两句代码就可以完成深拷贝呢？
这是因为：
使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去
赋值运算符的左操作数，*this再与传入的临时对象obj交换，就直接完成了拷贝
在函数结束之后，存储在栈区的obj再函数结束之后，obj生命周期结束
obj调用析构函数，把指向的从*this那里交换来的不需要的空间销毁
析构函数
使用递归遍历，把所有从堆区申请的节点都释放掉：
因为析构函数不能有多余的参数，但是递归函数又必须使用参数记录信息
所以再封装一个成员函数，专门用来递归释放：
然后在拷贝构造里面调用一下这个函数就行了
~AVLTree(){ Destroy(_root); _root =nullptr;}find
具体流程：
从根节点开始，将目标值（传入的key）与当前节点的key进行比较。
如果目标值小于当前节点值，则在左子树中继续查找；
如果目标值大于当前节点值，则在右子树中继续查找。
这个过程一直进行，直到找到与目标值或者到达空节点为止。
把上述过程转成代码：
insert[重要]
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。
那么AVL树的插入过程可以分为两步：
- 先按照二叉搜索树的方式插入新节点
- 再调整节点的平衡因子
因为新节点一定是插在叶子节点或者只有一个孩子节点的节点上
所以插入节点后一定会影响新节点的父亲节点的平衡因子，可能会影响祖先节点
插入节点后具体分以下3种情况：
- 插入节点的父亲节点（以下简称parent）的平衡因子
等于2/-2此时parent的左右子树高度差已经超过1，已经违反了AVL树的规则需要旋转进行处理
插入节点的父亲节点（以下简称parent）的平衡因子等于1/-1
那么就说明插入之前parent的平衡因子一定是0【如果插入前是2/-2的话，一定早就被旋转了】
所以parent在插入之前是叶子节点
即以parent为根的子树插入之前的高度就是1，插入之后高度就变成了2
所以插入前后以parent为根的子树的高度增加了，自然就会影响parent的祖先的平衡因子
所以需要再向上继续更新祖先节点的平衡因子
插入节点的父亲节点（以下简称parent）的平衡因子等于0
那么就说明插入之前parent的平衡因子一定是1/-1
所以parent在插入之前是只有一个孩子节点的节点
即以parent为根的子树插入之前的高度就是2，插入之后高度还是2
所以插入前后以parent为根的子树的高度没有改变，自然就不会影响parent的祖先的平衡因子
所以不需要再向上取跟新祖先节点的平衡因子
直接插入结束
当parent的平衡因子为1/-1时，如何向上更新祖先节点的平衡因子呢？
其实也简单：
就是把原来的parent当做新的cur，把parent的父节点作为新的parent
再判断新的cur是父亲节点的左还是右，据此再更新新的parent的平衡因子
即
cur = parent; parent = parent->_parent; 因为以之前的parent为根的子树，高度增加了1 右因为平衡因子=右子树高度-左子树高度 所以： if(cur==parent->_left){ parent->_bf--;}else{ parent->_bf++;}然后，再重复判断一下新的parent的平衡因子的3种情况，进行处理
- 新的parent的平衡因子
变成了0,插入就结束 - 新的parent的平衡因子
变成了1/-1,就再重复这个过程，继续向上更新祖先节点的平衡因子 - 新的parent的平衡因子
变成了2/-2,就旋转
怎么旋转？
旋转分以下4种：
左单旋
所有的需要左单旋的情况，都可以画成下图的抽象图
具体情况描述：
- 插入前paernt的平衡因子为1，并且它的右边（PR）的平衡因子为0
- 新插入的节点
插在子树c上，并使子树c的高度增加1 - 插入后并向上跟新后：
paernt的平衡因子变成2，并且它的右边（PR）的平衡因子变成了1
此时就使用左单旋：
把（下图中的）PRL链接在parent的右子树上，再把parent连接在PR的左子树上
把PR作为这颗子树新的根
这样就可以做到：在不违反搜索树规则【所有左子树上的值<根<右子树】的基础上，尽可能地让树平衡
将上述过程转换成代码：
右单旋
所有的需要右单旋的情况，都可以画成下图的抽象图
具体情况描述：
- 插入前paernt的平衡因子为-1，并且它的左边（PL）的平衡因子为0
- 新插入的节点
插在子树a上，并使子树a的高度增加1 - 插入后并向上跟新后：
paernt的平衡因子变成-2，并且它的左边（PL）的平衡因子变成了-1
此时就使用左单旋：
把（下图中的）PLR链接在parent的左子树上，再把parent连接在PL的右子树上
把PL作为这颗子树新的根
这样就可以做到：在不违反搜索树规则【所有左子树上的值<根<右子树】的基础上，尽可能地让树平衡
将上述过程转换成代码：
左右双旋
所有的需要左右双旋的情况，都可以画成下图的抽象图
具体情况描述：
- 插入前paernt的平衡因子为
-1，并且它的左边（PL）的平衡因子为0 - 新插入的节点插在子树
b或者c上，并使子树b或者c的高度增加1 - 插入后并向上跟新后：
paernt的平衡因子变成-2，并且它的左边（PL）的平衡因子变成了1
此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为2/-2的节点
但是如果我们对PL进行左单旋之后，就可以发现可以对parent使用右旋来使树，在不违反搜索树规则【所有左子树上的值<根<右子树】的基础上，尽可能地接近平衡
即
RotateL(parent->_left);RotateR(parent);右左双旋
所有的需要右左双旋的情况，都可以画成下图的抽象图
具体情况描述：
- 插入前paernt的平衡因子为
1，并且它的右边（PR）的平衡因子为0 - 新插入的节点插在子树
b或者c上，并使子树b或者c的高度增加1 - 插入后并向上跟新后：
paernt的平衡因子变成2，并且它的右边（PR）的平衡因子变成了-1
此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为2/-2的节点
但是如果我们对PR进行右单旋之后，就可以发现可以对parent使用左单旋来使树，在不违反搜索树规则【所有左子树上的值<根<右子树】的基础上，尽可能地接近平衡
即
RotateR(parent->_right);RotateL(parent);旋转的平衡因子更新
左单旋和右单旋
因为插入的情况都只有一种，所以平衡因子的更新很简单，看上面画的示意图就行
即parent和PR(PL)的平衡因子最后都变成0，其他节点的平衡因子没有变化
左右双旋和右左双旋
因为左右双旋和右左双旋的新节点既可以插在子树b上，又可以插在子树c上
而插在这两颗子树上的平衡因子更新是不同的
例
下图是左右双旋新节点插在子树b上的
最后：parent的平衡因子=1，PL的平衡因子=0，PLR的平衡因子=0
下图是左右双旋新节点插在子树c上的
最后：parent的平衡因子=0，PL的平衡因子=-1，PLR的平衡因子=0
而且当h=0时，还有一种情况：
下图是左右双旋的h=0的旋转图
最后：parent的平衡因子=0，PL的平衡因子=0，PLR的平衡因子=0
综上：左右双旋代码
右左双旋同理
insert的全部代码
boolInsert(const T& data){ if(_root ==nullptr) 树为空，则直接新增节点 { 赋值给二叉搜索树的成员变量`_root`指针 _root =newNode(data);returntrue; 返回true，代表插入成功 } Node* cur = _root; 从根节点开始 定义parent来保存cur的父亲节点 假设根节点的父亲节点为nullptr Node* parent =nullptr;while(cur){ 
