个人主页: 起名字真南的CSDN博客
个人专栏:
【数据结构初阶】 ? 基础数据结构【C语言】 ? C语言编程技巧【C++】 ? 进阶C++【OJ题解】 ? 题解精讲
目录
前言1 AVL树的概念2 AVL树的实现2.1 AVL树的结构2.2 AVL树的插入2.2.1 插入的大概过程2.2.2 插入节点以及更新平衡因子的代码实现 2.3 AVL树的旋转**2.3.1 单旋调整****左旋 (RotateL)****右旋 (RotateR)** **2.3.2 双旋调整****左-右双旋 (RotateLR)****右-左双旋 (RotateRL)** **2.3.3 平衡因子调整总结**插入节点时的旋转调整：删除节点时的旋转调整： 2.3.4 **AVL 树平衡因子和旋转的核心点** 2.4 AVL树的查找2.5 AVL树平衡检测2.6 AVL树的删除
前言
AVL树是一种自平衡的二叉搜索树，它的名字来源于它的发明者G.M. Adelson-Velsky和E.M. Landis，两位前苏联的科学家在论文《An algorithm for the organization of information》中发表了它。
1 AVL树的概念
在AVL树中，任一节点的两棵子树的高度差不超过1，确保了树的高度始终保持在O(log n)范围内，从而提高了查找、插入和删除操作的效率。
主要特点：
平衡因子：每个节点的平衡因子定义为其右子树高度减去左子树高度。平衡因子的取值只能是-1、0或1。当插入或删除节点导致某个节点的平衡因子超出此范围时，需要通过旋转操作来恢复平衡。
旋转操作：为了维护AVL树的平衡性，主要采用以下四种旋转操作：
单右旋（LL旋转）：用于左子树的左子树插入导致的不平衡。单左旋（RR旋转）：用于右子树的右子树插入导致的不平衡。先左后右旋（LR旋转）：用于左子树的右子树插入导致的不平衡。先右后左旋（RL旋转）：用于右子树的左子树插入导致的不平衡。这些旋转操作通过调整节点的位置，重新平衡树结构，确保AVL树的高度保持在对数级别，从而保证操作的高效性。
AVL树在需要频繁查找、插入和删除操作的应用中表现出色，广泛应用于数据库和文件系统等领域。
如图所示，这是一课需要进行旋转的AVL树，需要旋转的点就是10，因为它的平衡因子绝对值大于一不满足平衡二叉搜索树的条件，没有节点上面的数字就是它的平衡因子(Balance factor)
2 AVL树的实现
我们想要实现AVL树就需要先清除AVL树的构成，它是由节点，和树一起构成的。
2.1 AVL树的结构
节点的定义： 需要包含关键字段，包括键值对(key , value)、左右节点的指针、父亲节点的指针、以及平衡因子(_bf) 示例代码#include<iostream>using namespace std;template<class K, class V>struct AVLTreeNode{pair<K,V> _kv;AVLTreeNode<K,V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _balance_factor;AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_balance_factor(0)};template<class K, class V>class AVLTree{typedef AVLTreeNode<K,V> Node;public://实现树的各种操作private:Node* _root = nullptr;};我们可以发现在这串代码中并没有构造函数，是因为树是由节点和根节点指针构成的，在构造时会调用节点的构造函数，并且我们给根节点nullptr的缺省值。
2.2 AVL树的插入
2.2.1 插入的大概过程
首先需要找到合适的插入位置，通过比较Key的大小，是向左还是向右找到当前为空的节点然后进行插入因为插入了新的节点所以会引起平衡因子的变化，如果新增节点在父亲节点的右侧则+1，反之则-1，然后继续向上调整如果父亲节点在爷爷节点的右侧则爷爷节点+1，反之则-1，一直到平衡因子为2/-2或者平衡因子为0，又或者平衡因子调整到的了根节点就不需要继续调整。其中如果平衡因子为2/-2则需要进一步的进行旋转。
1.：需要进行旋转调整，平衡因子绝对值为2
2： 不需要继续向上调整，平衡因子变为0
3： 不需要进行平衡调整，因为已经调整到的根节点在我们调节平衡因子的时候出现了不平衡需要旋转以后，旋转的本质就是调节平衡，降低子树的高度，所以不会影响上一层，插入结束，但是需要更新旋转以后子树各个节点的平衡因子。
2.2.2 插入节点以及更新平衡因子的代码实现
bool Insert(const pair<K,V>& kv){if(_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;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为nullptr节点，parent为它的父亲节点cur = new Node(kv);//我们链接的一直都是指针所以我们进行比较的时候都使用kvif(kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}//最后在将父亲节点互相链接cur->_parent = parent;}代码解释：
首先我们要先对树的根节点进行判断是否为空树，如果为空则直接构造一个根节点，如果不为空则进行下一步骤，根据插入节点Key的大小进行比较找到空指针，大于往右走，小于往左走，一直到找到最后一个叶子节点，此时的叶子节点为parent，接着继续比较kv对象和叶子节点的Key值，如果大于则插入在右边，小于则插入在左边。最后将新插入的节点与父亲节点链接起来。
接下来我们开始更新平衡因子
//因为此时的父亲节节点在插入之前是最后一层的节点，//插入之后变成了倒数第二层的节点所以需要对他的平衡因子进行修改while(parent){if(cur == parent->_left)parent->_balance_factor--;elseparent->_balance_factor++;//更新完成之后需要进行判断是否进行向上调整if(parent->_balance_factor == 0){//停止更新break;}else if(parent->_balance_factor == 1 || parent->_balance_factor == -1){//继续向上更新cur = parent;parent = cur->_parent;}else if(parent->_balance_factor == 2 || parent->_balance_factor == -2){//平衡因子为2/-2，不再进行向上调整，需要进行旋转//旋转代码,见下文}else{assert(false)}}return true;代码解释：在插入一个新的节点以后我们需要更新一下平衡因子，首先要进行判断，新插入的节点是在父亲的右边还是左边，如果右边+1反之**-1**。调整完成之后我们还需要进行判断更新后的平衡因子是否满足结束调节及平衡因子为0，以及是否到达了根节点(因为在向上调整的过程中当cur为根节点时根节点的父亲节点为nullptr，此时我们的while循环条件是parent不为空，所以我们在判断的时候不需要判断是否到达了根节点)。如果不满足结束条件就是parent的平衡因子为1/-1，继续向上调整，如果为2/-2则需要进行旋转。
2.3 AVL树的旋转
在 AVL 树中，平衡因子 是定义为 右子树高度减去左子树高度
平衡条件：AVL 树的每个节点的平衡因子必须保持在[-1, 0, 1] 之间。 BF = 0：左右子树高度相等。BF = -1：左子树比右子树高 1。BF = 1：右子树比左子树高 1。 当平衡因子超出范围（即 BF < -1 或 BF > 1）时，需要通过旋转操作来恢复平衡。
2.3.1 单旋调整
左旋 (RotateL)
触发条件：
当前节点（parent）的 平衡因子 BF == 2，即右子树高度比左子树高 2。且右子节点（subR）的平衡因子为 1。 旋转效果：
右子节点（subR）成为新的子树根。当前节点（parent）成为右子节点的左子树。平衡因子调整： 旋转后，parent._bf = 0，subR._bf = 0。 旋转前后示例：
插入导致失衡：
parent 10 \ subR 20 \ 30左旋后：
subR 20 / \ parent 10 30代码实现：
void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parnet;Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if(pParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if(parent == pParent->_right){pParent->_right = surR;}else{ pParent->_left = surR;}subR->_parent = pParent;}parent->_balance_factor = 0;subR->_balance_factor = 0;}
代码解释：
首先我们需要清楚在进行左单旋的时候的前置条件参数parent节点的平衡因子由1->2，它的右子树subR的平衡因子由0->1，这表明在插入节点之前他的右子树subR是平衡的也就是他可有一个左节点subRL，所以我们在开始进行旋转之前要提前记录好这些节点的指针，方便后续的调整，我们从全局的思维来看，旋转点是parent，我们首先要把subRL节点传到parent节点的右边，不要忘了链接subRL的父亲节点，为了避免对空指针进行访问所以我们需要进行判断，接下来我们要判断旋转因子是否为根节点，我们定义了一个pParent节点，如果他为nullptr则parent为根节点，所以我们需要进行更新，如果不为空我们需要判断parent是pParent的左节点还是右节点因为parent被旋转以后subR称为新的旋转子树的跟需要与pParent进行链接。
最后我们需要更新平衡因子如图所示我们可以直观的看出来更新以后的平衡因子parent，subR都为0。
右旋 (RotateR)
触发条件：
当前节点（parent）的 平衡因子 BF == -2，即左子树高度比右子树高 2。且左子节点（subL）的平衡因子为 -1。 旋转效果：
左子节点（subL）成为新的子树根。当前节点（parent）成为左子节点的右子树。平衡因子调整： 旋转后，parent._bf = 0，subL._bf = 0。 旋转前后示例：
插入导致失衡：
parent 30 / subL 20 / 10右旋后：
subL 20 / \ parent 10 30代码实现：
void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if(subLR)subLR->_parent = parent;Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if(pParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if(pParent->_right = parent){pParent->_right = subL;}else{pParent->_left = subL;}subL->_parent = parent;}parent->_balance_factor = 0;subL->_balance_factor = 0;}
代码解释：
首先我们需要清楚在进行右单旋的时候的前置条件参数parent节点的平衡因子由1->2，它的左子树subL的平衡因子由0->1，这表明在插入节点之前他的左子树subL是平衡的也就是他可有一个右节点subLR，所以我们在开始进行旋转之前要提前记录好这些节点的指针，方便后续的调整，我们从全局的思维来看，旋转点是parent，我们首先要把subLR节点传到parent节点的左边，不要忘了链接subLR的父亲节点，为了避免对空指针进行访问所以我们需要进行判断，接下来我们要判断旋转因子是否为根节点，我们定义了一个pParent节点，如果他为nullptr则parent为根节点，所以我们需要进行更新，如果不为空我们需要判断parent是pParent的左节点还是右节点因为parent被旋转以后subR称为新的旋转子树的跟需要与pParent进行链接。
最后我们需要更新平衡因子如图所示我们可以直观的看出来更新以后的平衡因子parent，subL都为0。
2.3.2 双旋调整
左-右双旋 (RotateLR)
触发条件：
当前节点（parent）的 平衡因子 BF == -2，即左子树高度比右子树高 2。且左子节点（subL）的 平衡因子 BF == 1，即左子树的右子树高度更高。 旋转效果：
第一步：对左子节点（subL）进行左旋。第二步：对当前节点（parent）进行右旋。平衡因子调整： 根据左旋后中间节点（subLR）的平衡因子进行分配。 旋转前后示例：
插入导致失衡：
parent 30 / subL 10 \ subLR 20左-右双旋后：
subLR 20 / \ subL parent 10 30void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bt = subLR->_balance_factor;RotateL(parent->_left);RotateR(parent);if(bf == 0){subL->_balance_factor = 0;parent->_balance_factor = 0;subLR->_balance_factor = 0;}else if(bf == 1){subL->_balance_factor = -1;parent->_balance_factor = 0;subLR->_balance_factor = 0;}else if(bf == -1){subL->_balance_factor = 0;parent->_balance_factor = 1;subLR->_balance_factor = 0;}else{assert(false);}}
代码解释：
我们在进行左右双旋的时候前置条件是当前子树的根节点平衡因子为-2，左子树的平衡因子为1，如图所示10为当前子树的根节点在8节点的后面插入一个元素为9的节点所以在左子树5的平衡因子变为1，这个时候我们需要将5节点作为一棵树此时我们需要把5节点进行左旋，8变成根节点5变成他的左节点，然后从整体来看又是一个需要右旋的场景这个时候我们的旋转因子就是10，将10右旋，8的右节点变成了10的左节点，其实从整体来看，左右双旋的本质就是将新增节点(9)的父亲节点(8)变成根节点8的父亲节点变成了它的左节点，pParent(10)变成了它的右节点，然后将8的左右节点分别变成了parent的右节点和pParent的左节点。最后注意在调节平衡因子的时候bf为新增节点的父亲节点的平衡因子，如图所示如果增加以后它的平衡因子为0则双方都不变，如果为1说明增加的是右节点，这个右节点会变成parent的左节点因为parent下降了两层但是右边有一个节点所以平衡因子变成了1但是因为又增加了一个左节点所以变成了0，subL本来右边两层节点，左边一层节点变成了只有左边一个节点，如果为-1，就说明新增的是左节点变成了subL的右节点因为subLR变成了根节点subL的右节点新增和减少抵消还是为0，因为parent没有新增节点并且左边降低了两层右边还是相对于有一层所以平衡因子变为1。
右-左双旋 (RotateRL)
触发条件：
当前节点（parent）的 平衡因子 BF == 2，即右子树高度比左子树高 2。且右子节点（subR）的 平衡因子 BF == -1，即右子树的左子树高度更高。 旋转效果：
第一步：对右子节点（subR）进行右旋。第二步：对当前节点（parent）进行左旋。平衡因子调整： 根据右旋后中间节点（subRL）的平衡因子进行分配。 旋转前后示例：
插入导致失衡：
parent 10 \ subR 30 / subRL 20右-左双旋后：
subRL 20 / \ subR parent 10 30void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_balance_factor;RotateR(parent->_right);RotateL(parent);if(bf == 0){subR->_balance_factor = 0;parent->_balance_factor = 0;subRL->_balance_factor = 0;}else if(bf == 1){subR->_balance_factor = 0;parent->_balance_factor = -1;subRL->_balance_factor = 0;}else if(bf == -1){subR->_balance_factor = 1;parent->_balance_factor = -1;subRL->_balance_factor = 0;}}
代码解释:
进行右左双旋的时候parent节点的平衡因子是2它的右子树节点subR的平衡因子为-1，此时进行右左双旋，结合图片原理同上。
2.3.3 平衡因子调整总结
插入节点时的旋转调整：
旋转后，平衡因子一般重置为0。如果旋转前中间节点的平衡因子为非零，需要根据其具体值调整相关节点的平衡因子。 删除节点时的旋转调整：
删除节点后需要更新平衡因子，并可能导致新的不平衡，需要重复旋转。2.3.4 AVL 树平衡因子和旋转的核心点
平衡因子范围：AVL 树中每个节点的平衡因子始终在[-1, 1] 之间。旋转的目标：调整平衡因子，确保子树高度差不超过 1。递归调整：插入或删除可能影响父节点，调整需要递归向上传播，直至根节点或满足平衡条件。 2.4 AVL树的查找
AVL树为平衡二叉树所以查找的效率是O(logN)
Node* Find(const K& key){Node* cur = _root;while(cur){if(cur->_kv.first < key){cur = cur->_right;}else if(cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}代码解释：
我们通过比较key值的大小，大的往右走，小的往左走找到了直接返回指针即可。
2.5 AVL树平衡检测
想验证我们实现的AVL树是否合格，我们通过检查左右子树的高度差进行反向验证即可，在这里我们使用递归的方式来计算左右子树的长度。
int _Height(Node* root){if(root == nullptr){return 0;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1: rightHeight + 1;}bool _IsBalanceTree(Node* root){if(root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;if(abs(diff) >= 2){return false;}if(diff != root->_balance_factor){return false;}return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}代码解释：
通过使用递归的方式计算出每颗子树的高度，通过比较两个子树的高度差来判断他是否是平衡的，并且用差值还可以判断根节点的平衡因子是否异常，两个子树的差值就应该是根节点的平衡因子，如果两棵树都是AVL树那么这整颗树就一定是AVL树
2.6 AVL树的删除
AVL树的删除和二叉搜索树的删除同理，只不过需要删除之后检查平衡因子如果平衡因子不符合则需要进行旋转，
链接: 二叉搜索树博客