一、前言
本文是基于二叉搜索树的知识前提下对于AVL树进行叙述的，主要叙述的方面在于AVL树的插入方面，因为AVL树同二叉搜索树的最大区别就在于插入的操作和删除操作，删除操作也是类似的，但是难就难在更新平衡因子，后续会补上。而对于其他的操作如：二叉搜索树的查找操作等等都是相似的，因此本文主要介绍AVL树的插入操作。
AVL树的概念
AVL树是一种自平衡二叉搜索树，它的特点是保证了每个节点的左右子树的高度差不超过1。它在插入和删除时会自动平衡，以保持树的高度始终在log N的范围内，从而保证了查找、插入、删除等操作的高效性。AVL树的名字来源于其发明者G.M.Adelson-Velsky和E.M.Landis的姓氏缩写。以下为一颗AVL树：
AVL树同二叉搜索树的异同
AVL树和二叉搜索树有很多相似之处，但也有许多不同之处。以下是它们的主要异同点：
相同点：
- 它们都是自平衡二叉搜索树，也就是说，在插入和删除节点后，它们能够保持一定的平衡性，从而保证查询操作的时间复杂度始终保持在O(logn)级别。
- 它们都遵循二叉搜索树的基本性质，即左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点。
不同点：
- 在AVL树中，除了左右子树高度差不能超过1之外，每个叶子节点还必须在左右子树的高度之间，而在二叉搜索树中则没有这样的限制。（AVL中通常定义一个bf值（balance factor）用于记录节点左右子树的高度差）
- 在AVL树中，任何路径上的节点数差异不能超过1，而在二叉搜索树中则没有这样的要求。
- 在插入和删除节点后，AVL树需要进行更多的旋转操作来恢复平衡，而二叉搜索树则不需要这样的步骤。
- AVL树更适合于查找操作，因为它通过严格的平衡性保证了查询操作的效率，而二叉搜索树更适合于插入和删除操作，因为它可以通过简单的旋转操作来快速调整树结构。
二、AVL树的实现
节点的定义
通过KV模型定义AVL树节点，定义三叉链的结构储存父节点以及左右子树节点的地址，定义了bf（平衡因子）用于记录节点右子树与左子树之差（右-左），通过构造函数初始化列表，特别要将bf置为0，如果不置0后续操作可能会出错（别问作者怎么知道的(〃＞皿＜)）。
vtemplate<class K, class V> struct AVLTreeNode { AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; pair<K, V> _kv; int _bf; // balance factor AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {} };
AVL树的初始化定义
// AVL: 二叉搜索树 + 平衡因子的限制 template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: // 在AVL树中插入节点 bool Insert(const pair<K, V>& kv); // AVL树的验证 bool _IsBalance(Node* root) { return _IsBalance(_root); } private: // 右单旋 void RotateR(Node* parent); // 左单旋 void RotateL(Node* parent); // 右左双旋 void RotateRL(Node* parent); // 左右双旋 void RotateLR(Node* parent); // 求高度 int _Height(Node* root ); // 根据AVL树的概念验证pRoot是否为有效的AVL树 bool _IsBalance(Node* root); private: Node* _root = nullptr; };
AVL树的插入（重点及难点！！！）
插入大致步骤
AVL树的插入操作可以分为以下几步：
- 向AVL树中插入一个新节点，首先找到该节点的位置。这可以通过比较新节点的值与当前节点的值来完成，直到找到一个空位置或者到达一个叶子节点为止。按照大往左，小往右，相等返回false的规则。
- 依次向下搜索直到找到相应的位置，就将新节点插入到这个位置，并且更新该节点的父节点和兄弟节点的指针。就将新节点插入到这个位置，然后向上更新节点的bf值。
- 插入完成后，需要检查新插入的节点是否破坏了AVL树的平衡性。如果破坏了平衡性，就需要执行一系列旋转操作来修复不平衡状态。具体来说，如果新插入的节点使得某个分支的深度增加了一级，那么可以执行一次相应的旋转操作：左旋、右旋、左右旋、右左旋，最后按要求更新各个节点的bf值。
以上就是AVL树的插入操作步骤。需要注意的是，每次插入操作都需要按照这些步骤来进行，才能保证AVL树的平衡性。
根据规则找节点
如果_root为空（即空树）则新建节点并返回。比较节点的值，如果插入节点大则往右子树遍历，小则往左子树遍历，如果与节点值相同则无需插入直接返回。后续找到相应的位置后就可跳出循环进行下一步操作。
if (_root == nullptr) { _root = new Node(kv); 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; } }
插入并且链接节点
更新节点信息，新插入节点的_parent值，以及父节点链接他在左子树还是右子树的判断，链入AVL树中。
cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; }
向上更新bf（平衡因子）的值
在插入之前，parent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
1. 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可。
2. 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可。
此时：parent的平衡因子可能有三种情况：0，正负1， 正负2
1. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功。
2. 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新。
3. 如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理。
while (parent) { if (cur == parent->_left)//根据在左还是右改变bf值 { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0)//bf=0则向上都无需变化 { break; } else if (parent->_bf == 1 || parent->_bf == -1)//bf变化向上遍历改变bf值 { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2)//破坏了bf值需要-1<=bf<=1的区间，需要旋转矫正 { if (parent->_bf == 2 && cur->_bf == 1)//左旋情况 { RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == -1)//右旋情况 { RotateR(parent); } else if (parent->_bf == 2 && cur->_bf == -1)//右旋再左旋情况 { RotateRL(parent); } else if (parent->_bf == -2 && cur->_bf == 1)//左旋再右旋情况 { RotateLR(parent); } // 1、旋转让这颗子树平衡了 // 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新 break; } else { assert(false);//其它情况的bf值表示这颗avl树本身就有问题 } }
左单旋
由于我们每次插入都会进行调整操作，对此AVL树在新的节点插入前都是合法的，也就是说bf值只会在-1~1之间波动。 当 parent->_bf == 2 && cur->_bf == 1时，我们需要进行左单旋的操作以确保AVL树的合法性（也就是当父节点的右子树高时需要进行左单旋），以下为对此以下为大致的操作图：
详细旋转过程：
对于左单旋操作，我们需要先记录几个节点，分别如下为parent、subR、subRL，因为我们主要是改变这三个的位置。在旋转完成后我们也通过图清晰可见，parent和subR的bf值都是0。
void RotateL(Node* parent)//左旋 { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; subR->_left = parent; Node* parentParent = parent->_parent; parent->_parent = subR; if (subRL)//判断节点subRL是否为空，防止出错 subRL->_parent = parent; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (parentParent->_left == parent) { parentParent->_left = subR; } else { parentParent->_right = subR; } subR->_parent = parentParent; } parent->_bf = subR->_bf = 0; }
右单旋
对于右单旋，操作同左单旋相似，也是需要记录三个节点：parent、subL、subLR,只不过此时我们是向右旋转。当 parent->_bf == -2 && cur->_bf == -1时，我们需要进行右单旋的操作以确保AVL树的合法性（也就是当父节点的左子树高时需要进行右单旋）。在旋转完成后我们也通过图清晰可见，parent和subR的bf值都是0。以下为对此以下为大致的操作图：
void RotateR(Node* parent)//右旋 { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* parentParent = parent->_parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (parentParent->_left == parent) { parentParent->_left = subL; } else { parentParent->_right = subL; } subL->_parent = parentParent; } parent->_bf = subL->_bf = 0; }
左右双旋
当parent->_bf == -2 && cur->_bf == 1时，也就意味着我们的插入操作在如下的b的位置，插入后的图为第二张图，对此我们仅仅只进行一次旋转是远远不够的，如下第三张图为以30为父节点（即subL）只进行了一次左单旋后所变化的图，如果我们仔细观察可以发现这非常符合需要右单旋的操作，因此，此时我们以90为父节点再进行一次右单旋操作。 当然双旋最重要的其实是bf值的确定，我们需要根据最开始的subLR的bf值来确定。
当bf == 0，则subLR自己就是新增因此
parent->_bf = subL->_bf = subLR->_bf = 0;
当bf==-1，则subLR的左子树新增
parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;
当bf==1，则subLR的右子树新增
subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;
void RotateLR(Node* parent) { //... Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 0) { // subLR自己就是新增 parent->_bf = subL->_bf = subLR->_bf = 0; } else if (bf == -1) { // subLR的左子树新增 parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1) { // subLR的右子树新增 subL->_bf = -1; parent->_bf = 0; subLR->_bf = 0; } else { assert(false); } }
右左双旋
当parent->_bf == 2 && cur->_bf == -1时，我们需要进行右左双旋操作，当然同左右双旋一样，只进行一次旋转肯定是不够的，我们也可以猜到先对subR作为一次父节点进行右单旋，在再对parent进行左单旋。
当然双旋最重要的其实是bf值的确定，我们需要根据最开始的subRL的bf值来确定。
当bf == 0，则subRL自己就是新增
parent->_bf = subR->_bf = subRL->_bf = 0;
当bf==-1，则subRL的左子树新增
parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;
当bf==1，则subRL的右子树新增
parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 0) { // subRL自己就是新增 parent->_bf = subR->_bf = subRL->_bf = 0; } else if (bf == -1) { // subRL的左子树新增 parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } else if (bf == 1) { // subRL的右子树新增 parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else { assert(false); } }
判断是否符合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 _IsBalance(Node* root) { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); }
三、整体代码
#pragma once #include<iostream> #include<assert.h> using namespace std; template<class K, class V> struct AVLTreeNode { AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; pair<K, V> _kv; int _bf; // balance factor AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {} }; template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); 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; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } while (parent) { if (cur == parent->_left)//根据在左还是右改变bf值 { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0)//bf=0则向上都无需变化 { break; } else if (parent->_bf == 1 || parent->_bf == -1)//bf变化向上遍历改变bf值 { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2)//破坏了bf值需要-1<=bf<=1的区间，需要旋转矫正 { if (parent->_bf == 2 && cur->_bf == 1)//左旋情况 { RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == -1)//右旋情况 { RotateR(parent); } else if (parent->_bf == 2 && cur->_bf == -1)//右旋再左旋情况 { RotateRL(parent); } else if (parent->_bf == -2 && cur->_bf == 1)//左旋再右旋情况 { RotateLR(parent); } // 1、旋转让这颗子树平衡了 // 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新 break; } else { assert(false);//其它情况的bf值表示这颗avl树本身就有问题 } } return true; } void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance() { return _IsBalance(_root); } private: void RotateL(Node* parent)//左旋 { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; subR->_left = parent; Node* parentParent = parent->_parent; parent->_parent = subR; if (subRL)//判断节点subRL是否为空，防止出错 subRL->_parent = parent; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (parentParent->_left == parent)//链接subR给父节点的父节点，需要判断是在左子树还是右子树 { parentParent->_left = subR; } else { parentParent->_right = subR; } subR->_parent = parentParent; } parent->_bf = subR->_bf = 0; } void RotateR(Node* parent)//右旋 { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; Node* parentParent = parent->_parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (parentParent->_left == parent) { parentParent->_left = subL; } else { parentParent->_right = subL; } subL->_parent = parentParent; } parent->_bf = subL->_bf = 0; } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 0) { // subRL自己就是新增 parent->_bf = subR->_bf = subRL->_bf = 0; } else if (bf == -1) { // subRL的左子树新增 parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } else if (bf == 1) { // subRL的右子树新增 parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else { assert(false); } } void RotateLR(Node* parent) { //... Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 0) { // subLR自己就是新增 parent->_bf = subL->_bf = subLR->_bf = 0; } else if (bf == -1) { // subLR的左子树新增 parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1) { // subLR的右子树新增 subL->_bf = -1; parent->_bf = 0; subLR->_bf = 0; } else { assert(false); } } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } 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 _IsBalance(Node* root) { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); if (rightHeight - leftHeight != root->_bf) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } private: Node* _root = nullptr; };
感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！
