目录
AVL树概念
AVL树的实现
AVL树的节点
AVL树的插入
AVL树的平衡调整
右单旋
左单旋
左右双旋
右左双旋
完整的插入函数
AVL树的查找
AVL树的验证
验证有序
验证平衡
完整代码
AVL树概念
AVL树是一种具有特殊性质的二叉搜索树，AVL树的左右子树也都是AVL树，且左右子树的高度差的绝对值不超过1，超过1就说明AVL树失衡，需要调整。AVl树是一颗高度平衡的二叉搜索树，通过高度控制高度差去控制平衡。
AVL树对比二叉搜索树多引入了一个平衡因子的概念，每个节点都有一个平衡因子，任何节点的平衡因子等于右子树的高度减去左子树的高度，所以说平衡因子的取值是0、1和-1。
AVL树整体节点和分布与完全二叉树类似，高度控制在logN范围内，那么增删查改的效率也可以控制在O(logN)，相比二叉搜索树有了本质提升。
以下这棵树就是AVL树。
AVL树的实现
AVL树的节点
由于在调整失衡的AVL树时，需要频繁访问父节点，所以我们在定义节点时也需要引入parent指针。
template<class K, class V>struct AVLTreeNode{pair<K, V > _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;AVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};AVL树的插入
向AVL树插入新节点的过程与二叉搜索树的插入类似，但有区别的是，插入新节点后需要更新平衡因子，然后根据平衡因子的情况判断AVL树是否失衡，失衡就对AVL树进行调整。
按照平衡因子的计算公式，如果新节点插入到了父亲节点的左边，那么父亲的平衡因子-1，反之，如果插入到右边，父亲的平衡因子+1。
更新后的平衡因子的情况，可以分为两种：1.平衡因子（从1/-1）变成0。 2.平衡因子（从0）变成1/-1。
情况1就说明已经完成平衡因子的更新了，情况2就还得继续更新，因为当父亲的平衡因子为1/-1时，说明以父亲为根节点的子树高度发生了变化，这样会影响父亲的父亲的平衡因子，所以需要继续往上更新平衡因子。
template<class K, class V>class AVLTree{typedef AVLTreeNode 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){parent = cur;if (kv.first > cur->_kv.first)cur = cur->_right;else if (kv.first < cur->_kv.first)cur = cur->_left;elsereturn false;}cur = new Node(kv);//将父节点与新节点链接//判断新节点插入到parent的左边还是右边if (kv.first > parent->_kv.first) //新节点插入到parent的右边parent->_right = cur;elseparent->_left = cur;//更改新节点的父亲指针cur->_parent = parent;//更新平衡因子while (parent){//插入节点后除了对父节点造成影响还可能对祖宗节点造成影响//随着循环进行，cur不一定为新节点//更新父节点的平衡因子if (cur == parent->_left)parent->_bf--;elseparent->_bf++;//检查更新后父亲的平衡因子//_bf为0，说明树还是AVL树，退出循环if (parent->_bf == 0)break;//_bf == 1/-1,说明需要继续向上更新平衡因子else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}//_bf == 2/-2，说明AVL树失衡，需要进行旋转操作else if (parent->_bf == 2 || parent->_bf == -2){//插入后AVl树失衡，需要进行平衡调整}}return true;}private:Node* _root = nullptr;;};AVL树的平衡调整
AVL树的调整其实就是对失衡的AVl树进行旋转操作，旋转操作必须保持搜索树的规则，让失衡的AVL树变平衡。
旋转操作可以分为4种：右单旋、左单旋、左右双旋和右左双旋。
右单旋
当parent->_bf == -2 && cur->_bf == -1时说明AVL树往左倾斜，需要进行右单旋操作。
右单旋其实就是从树的右边将树顺时针旋转。 
void RotataR(Node* parent){//subL为parent的左孩子节点Node* subL = parent->_left;//subLR为subL的右子节点Node* SubLR = subL->_right;// 将parent与subLR节点进行链接parent->_left = SubLR;//在SubLR的情况下更改，让其指向正确的父亲if (SubLR)SubLR->_parent = parent;//提前记录祖父节点Node* pParent = parent->_parent;//链接subL与parentsubL->_right = parent;parent->_parent = subL;//根据parent是否是根节点进行不同处理if (parent == _root){_root = subL;subL->_parent = nullptr;}else {//将pParent和subL链接//但得先判断parent是pParent的左节点还是右节点if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;//修改subL的parent指针，让其指向正确的父亲subL->_parent = pParent;}//更新平衡因子subL->_bf = parent->_bf = 0;}左单旋
当parent->_bf == 2 && cur->_bf == 1时说明AVL树往右倾斜，需要进行左单旋操作。
左单旋其实就是从树的左边将树逆时针旋转。
void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;subR->_parent = pParent;}subR->_bf = parent->_bf = 0;}左右双旋
当parent->_bf == -2 && cur->_bf == 1时，即新节点插入到较高左子树的右侧：先左单旋然后再右单旋。
左右双旋情况比较复杂，如下图。
void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//记录subLR的bf，根据其取值更新左右双旋后各个节点的bfint bf = subLR->_bf;RotateL(subL);RotateR(parent);subLR->_bf = 0;if (bf == -1){subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subL->_bf = 0;parent->_bf = 0;}elseassert(false);}右左双旋
当parent->_bf == 2 && cur->_bf == -1时，即新节点插入到较高右子树的左侧：先右单旋然后再左单旋。
右左双旋其实就是左右双旋的另一种情况，我们直接上图解。
void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == 0){subR->_bf = 0;parent->_bf = 0;}elseassert(false);}完整的插入函数
bool Insert(const pair<K, V>& kv){//空树的情况特殊处理if (_root == nullptr){_root = new Node(kv);return true;}//不是空树的情况Node* parent = nullptr;Node* cur = _root;//查找新节点的插入位置while (cur){parent = cur;if (kv.first > cur->_kv.first)cur = cur->_right;else if (kv.first < cur->_kv.first)cur = cur->_left;elsereturn false;}cur = new Node(kv);//将父节点与新节点链接//判断新节点插入到parent的左边还是右边if (kv.first > parent->_kv.first) //新节点插入到parent的右边parent->_right = cur;elseparent->_left = cur;//更改新节点的父亲指针cur->_parent = parent;//更新平衡因子while (parent){//插入节点后除了对父节点造成影响还可能对祖宗节点造成影响//随着循环进行，cur不一定为新节点//更新父节点的平衡因子if (cur == parent->_left)parent->_bf--;elseparent->_bf++;//检查更新后父亲的平衡因子//_bf为0，说明树还是AVL树，退出循环if (parent->_bf == 0)break;//_bf == 1/-1,说明需要继续向上更新平衡因子else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}//_bf == 2/-2，说明AVL树失衡，需要进行旋转操作else if (parent->_bf == 2 || parent->_bf == -2){//插入后AVl树失衡，需要进行平衡调整if (parent->_bf == -2 && cur->_bf == -1)//右单旋RotateR(parent);else if (parent->_bf == 2 && cur->_bf == 1)//左单旋RotateL(parent);else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋RotateLR(parent);else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋RotateRL(parent);elseassert(false);break;}elseassert(false);}return true;}AVL树的查找
AVL树的查找与二叉搜索树是一摸一样的。
Node* Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first)cur = cur->_right;else if (key > cur->_kv.first)cur = cur->_left;elsereturn cur;}return nullptr;}AVL树的验证
验证有序
我们首先需要写一个中序遍历来看看插入的数据是否符合预期。
void InOrder(){ _InOrder(_root); cout << endl;} void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}我们来跑个测试用例。
void test_AVLTree1(){AVLTree<int, int> avlT1;AVLTree<int, int> avlT2;int a1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a2[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a1){avlT1.Insert({ e, e });}for (auto e : a2){avlT2.Insert({ e, e });}avlT1.InOrder();avlT2.InOrder();}
可以看到结果是没问题的。
验证平衡
int Height(){return _Height(_root);}int _Height(Node* root){if (root == nullptr)return 0;int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);return (LeftHeight > RightHeight ? LeftHeight : RightHeight) + 1;}bool IsBalanceTree(){return _IsBalanceTree(_root);}bool _IsBalanceTree(Node* root){// 空树也是AVL树if (root == nullptr)return true;// 计算pRoot结点的平衡因子：即Root左右子树的高度差int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);int diff = RightHeight - LeftHeight;// 如果计算出的平衡因子与Root的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);我们用大量数据来测试下。
void test_AVLTree2(){const int N = 1000000;vector<int> v;v.reserve(N);srand((unsigned int)time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}if (t.IsBalanceTree())cout << "是AVL树" << endl;elsecout << "不是AVL树" << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;}
完整代码
#include<iostream>#include<assert.h>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 _bf;AVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr),_right(nullptr),_parent(nullptr),_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){parent = cur;if (kv.first > cur->_kv.first)cur = cur->_right;else if (kv.first < cur->_kv.first)cur = cur->_left;elsereturn false;}cur = new Node(kv);//将父节点与新节点链接//判断新节点插入到parent的左边还是右边if (kv.first > parent->_kv.first) //新节点插入到parent的右边parent->_right = cur;elseparent->_left = cur;//更改新节点的父亲指针cur->_parent = parent;//更新平衡因子while (parent){//插入节点后除了对父节点造成影响还可能对祖宗节点造成影响//随着循环进行，cur不一定为新节点//更新父节点的平衡因子if (cur == parent->_left)parent->_bf--;elseparent->_bf++;//检查更新后父亲的平衡因子//_bf为0，说明树还是AVL树，退出循环if (parent->_bf == 0)break;//_bf == 1/-1,说明需要继续向上更新平衡因子else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}//_bf == 2/-2，说明AVL树失衡，需要进行旋转操作else if (parent->_bf == 2 || parent->_bf == -2){//插入后AVl树失衡，需要进行平衡调整if (parent->_bf == -2 && cur->_bf == -1)//右单旋RotateR(parent);else if (parent->_bf == 2 && cur->_bf == 1)//左单旋RotateL(parent);else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋RotateLR(parent);else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋RotateRL(parent);elseassert(false);break;}elseassert(false);}return true;}void RotateR(Node* parent){//subL为parent的左孩子节点Node* subL = parent->_left;//subLR为subL的右子节点Node* subLR = subL->_right;// 将parent与subLR节点进行链接parent->_left = subLR;//在SubLR的情况下更改，让其指向正确的父亲if (subLR)subLR->_parent = parent;//提前记录祖父节点Node* pParent = parent->_parent;//链接subL与parentsubL->_right = parent;parent->_parent = subL;//根据parent是否是根节点进行不同处理if (parent == _root){_root = subL;subL->_parent = nullptr;}else {//将pParent和subL链接//但得先判断parent是pParent的左节点还是右节点if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;//修改subL的parent指针，让其指向正确的父亲subL->_parent = pParent;}//更新平衡因子subL->_bf = parent->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;subR->_parent = pParent;}subR->_bf = parent->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//记录subLR的bf，根据其取值更新左右双旋后各个节点的bfint bf = subLR->_bf;RotateL(subL);RotateR(parent);subLR->_bf = 0;if (bf == -1){subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subL->_bf = 0;parent->_bf = 0;}elseassert(false);}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == 0){subR->_bf = 0;parent->_bf = 0;}elseassert(false);}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}bool IsBalanceTree(){return _IsBalanceTree(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first)cur = cur->_right;else if (key > cur->_kv.first)cur = cur->_left;elsereturn cur;}return nullptr;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_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 : RightHeight) + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}bool _IsBalanceTree(Node* root){// 空树也是AVL树if (root == nullptr)return true;// 计算pRoot结点的平衡因子：即Root左右子树的高度差int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);int diff = RightHeight - LeftHeight;// 如果计算出的平衡因子与Root的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}private:Node* _root = nullptr;};拜拜，下期再见?
摸鱼ing?✨?
