一、AVL树的概念
AVL树是最先发明的自平衡二叉查找树，AVL是⼀颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
易错点1：
最后插入的元素不一定是叶结点。因为新节点插入后，为了保证其平衡性，可能还要对树进行旋转处理，旋转之后，就不一定在叶子的位置。
易错点2：
平衡因子不是必须要维护的，在操作时也可以直接通过高度函数来算，只不过比较麻烦。
易错点3：
删除时，只要某个节点的平衡因子不满足特性时 ，只需要对该棵子树进行旋转，就可以使AVL树再次平衡。
错误，可能需要旋转多次，子树旋转后，其高度降低了一层，其上层可能也需要跟着旋转。
插入时，AVL树最多只需要旋转两次，即双旋。
二、AVL树的结构
template<class K, class V> struct AVLTreeNode { // 需要parent指针，后续更新平衡因⼦可以看到 pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; int _bf; // balance factor 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: //... private: Node* _root = nullptr; };
三、AVL树的实现
Insert分析：
平衡因子分析：
parent平衡因子更新分析：
1）插入后平衡因子为0，说明原来是-1或1（不可能是-2或2变来的，因为那样在之前就不是AVL树了），一边高一边低，插入到低的那边了，左右子树一样高了，停止更新。
2）插入后平衡因子为-1或1，说明原来是0（不可能是-2或2变来的，因为那样在之前就不是AVL树了），两边一样高，插入在左边或右边了，会影响上层节点，要向上更新。
（特例：parent已经是根了，停止更新）
3）插入后平衡因子为-2或2，说明原来是-1或1，一边高一边低，插入到高的那边了，需要旋转，旋转完后停止更新。
前两种情况易处理，关键就是第三种情况。
旋转的本质就是为了让新的根的平衡因子变为0，达到降树高的作用，不用往上更新。
第三种情况根据cur和parent的平衡因子取值分为四种情况讨论：
1.parent的bf为-2，cur的bf为-1（右单旋）
2.parent的bf为2，cur的bf为1（左单旋）
1和2情况为单纯的一边高情况，可以通过右单旋/左单旋解决
图示为右单旋操作：
分析：subL成为新的根，parent成为subL的右子树，subL的右子树给parent的左。
右单旋完了之后subL和parent的平衡因子都变为0，达到了降树高的作用。
右单旋代码如下：
//右单旋 void rotateR(Node* parent) { Node* grandparent = parent->_pParent; Node* subL = parent->_pLeft; Node* subLR = subL->_pRight; //1.判断parent是否是根，链接grandparent与subL if (grandparent == nullptr) { _pRoot = subL; } else { if (grandparent->_pLeft == parent) { grandparent->_pLeft = subL; } else { grandparent->_pRight = subL; } } subL->_pParent = grandparent; //2.链接subL和parent subL->_pRight = parent; parent->_pParent = subL; //3.链接subLR和parent,subLR不为空,subLR的parent要链接parent parent->_pLeft = subLR; if(subLR) subLR->_pParent = parent; //4.修改平衡因子 subL->_bf = parent->_bf = 0; }实现步骤：
1.链接grandparent和subL
2.链接subL和parent
3.链接parent和subLR
4.把subL和parent的平衡因子改为0
易错点：
1）grandparent可能为空，此时parent为根，需要将树的根修改为subL
2）subLR可能为空，需要判断。如果不为空，需要将subLR的parent指向parent；如果为空，则不需要。
左右双旋和友左双旋
3.parent的bf为-2，cur的bf为1（左右双旋）
4.parent的bf为2，cur的bf为-1（右左双旋）
左右双旋的抽象案例及情况划分：
1.h>=1，新节点插入到subLR的左子树，此时subL的bf为0，parent的bf为1。
2.h>=1，新节点插入到subLR的右子树，此时subL的bf为-1，parent的bf为0
3.h=0，新节点就是subLR，此时subL的bf为0，parent的bf为0
综上所述，左右双旋有三种情况：
1.h>=1，新节点插入到subLR的左子树，此时subL的bf为0，parent的bf为1。
2.h>=1，新节点插入到subLR的右子树，此时subL的bf为-1，parent的bf为0
3.h=0，新节点就是subLR，此时subL的bf为0，parent的bf为0
根subLR最后的bf都是0。
转化成对应的subLR的bf判断：
1）subLR的bf为-1，第一种情况
2）subLR的bf为1，第二种情况
3）subLR的bf为0，第三种情况
分析：先对subL进行左单旋，使模型变为纯粹的左边高，再对parent进行右单旋，subLR成为新的根。
左右双旋代码如下：
//左右双旋 void rotateLR(Node* parent) { Node* subL = parent->_pLeft; Node* subLR = subL->_pRight; //提前记录subLR的bf，以便后续分类 int bf = subLR->_bf; //先对subL进行左单旋，再对parent进行右单旋 rotateL(subL); rotateR(parent); //分情况更新平衡因子 if (bf == -1) { subL->_bf = 0; parent->_bf = 1; subLR->_bf = 0; } else if (bf == 1) { subL->_bf = -1; parent->_bf = 0; subLR->_bf = 0; } else if (bf == 0) { subL->_bf = 0; parent->_bf = 0; subLR->_bf = 0; } else { cout << "balance factor error!" << endl; assert(false); } }右左单旋与左右单旋极其类似，只画一张图：
三种情况：
1.h>=1，subRL的bf为1，subR的bf为0，parent的bf为-1
2.h>=1，subRL的bf为-1，subR的bf为1，parent的bf为0
3.h=0，subRL的bf为0，subR的bf为0，parent的bf为0
插入代码：
// 在AVL树中插入值为data的节点 bool Insert(const T& data) { //空树 if (_pRoot == nullptr) { _pRoot = new Node(data); return true; } Node* cur = _pRoot; Node* parent = nullptr; while (cur) { //小于根结点，往左走 if (data < cur->_data) { parent = cur; cur = parent->_pLeft; } //大于根结点，往右走 else if (data > cur->_data) { parent = cur; cur = parent->_pRight; } //相等不插入，返回false else { return false; } } cur = new Node(data); cur->_pParent = parent; //比parent小，插入左边 if (data < parent->_data) { parent->_pLeft = cur; } //比parent大，插入右边 else if (data > parent->_data) { parent->_pRight = cur; } //调整平衡因子 //循环条件parent非空 while (parent) { if (cur == parent->_pLeft) { parent->_bf--; } else { parent->_bf++; } //parent的平衡因子变为0， // 说明树现在已经平衡了，不需要向上调整 if (parent->_bf == 0) { break; } //现在调整为一边高一边低，高度增加了，要向上调整 else if (parent->_bf == -1 || parent->_bf == 1) { //parent已经是根了，不用调整 if (parent == _pRoot) { break; } //parent不是根，需要往上调整 else { cur = parent; parent = cur->_pParent; } } //需要旋转解决 else if (parent->_bf == -2 || parent->_bf == 2) { //纯粹左边高，右单旋 if (parent->_bf == -2 && cur->_bf == -1) { rotateR(parent); break; } //单纯右边高，左单旋 else if (parent->_bf == 2 && cur->_bf == 1) { rotateL(parent); break; } else if (parent->_bf == -2 && cur->_bf == 1) { rotateLR(parent); break; } else if (parent->_bf == 2 && cur->_bf == -1) { rotateRL(parent); break; } else { cout << "balance fator error!" << endl; assert(false); } } else { cout << "Tree is not AVLTree!" << endl; assert(false); } } return true; }
判断一棵树是否是平衡二叉树以及计算高度
// 根据AVL树的概念验证pRoot是否为有效的AVL树 bool _IsBalanceTree(Node* pRoot) { if (pRoot == nullptr) return true; int gap = _Height(pRoot->_pRight) - _Height(pRoot->_pLeft); if (abs(gap) >= 2) { cout << "not balanceTree!" << endl; assert(false); } if (pRoot->_bf != gap) { cout << "balance factor error!" << endl; assert(false); } return _IsBalanceTree(pRoot->_pLeft) && _IsBalanceTree(pRoot->_pRight); }size_t _Height(Node* pRoot) { if (pRoot == nullptr) return 0; size_t left = _Height(pRoot->_pLeft); size_t right = _Height(pRoot->_pRight); return left > right ? left + 1 : right + 1; }
LCR 176. 判断是否为平衡二叉树 - 力扣（LeetCode）
后序遍历优化：
class Solution { public: size_t height(TreeNode* root) { if(root==nullptr) return 0; size_t left = height(root->left); size_t right = height(root->right); return left>right ? left+1 : right+1; } bool isBalanced(TreeNode* root) { if(root==nullptr) return true; if(isBalanced(root->left) && isBalanced(root->right)) { int left = height(root->left); int right = height(root->right); return abs(left-right)<=1 ; } else { return false; } } };
测试AVL树插入和查找的性能：
测试代码：
// 插入一堆随机值，测试平衡，顺便测试高度和性能等 void TestAVLTree2() { const int N = 1000000; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; i++) { v.push_back(rand() + i); } size_t begin2 = clock(); AVLTree<int> t; for (auto e : v) { t.Insert(e); } size_t end2 = clock(); cout << "Insert:" << end2 - begin2 << endl; cout << "Height:" << t.height() << endl; cout << "IsBalanceTree:"<<t.IsBalanceTree() << endl; size_t begin1 = clock(); // 随机值 for (size_t i = 0; i < N; i++) { t.find((rand() + i)); } size_t end1 = clock(); cout << "Find:" << end1 - begin1 << endl; }
可以看到，数据量为100万，在release下，find的效率极高，至于Insert，new节点的效率比较大。
AVL树的左单旋和右左双旋代码实现：
//左单旋 void rotateL(Node* parent) { Node* grandparent = parent->_pParent; Node* subR = parent->_pRight; Node* subRL = subR->_pLeft; //1.判断parent是否是根，链接grandparent与subR if (grandparent == nullptr) { _pRoot = subR; } else { if (grandparent->_pLeft == parent) { grandparent->_pLeft = subR; } else { grandparent->_pRight = subR; } } subR->_pParent = grandparent; //2.链接subR和parent subR->_pLeft = parent; parent->_pParent = subR; //3.链接subRL和parent parent->_pRight = subRL; if(subRL) subRL->_pParent = parent; //4.修改平衡因子 subR->_bf = parent->_bf = 0; } //右左双旋 void rotateRL(Node* parent) { Node* subR = parent->_pRight; Node* subRL = subR->_pLeft; int bf = subRL->_bf; rotateR(subR); rotateL(parent); //分情况更新平衡因子 if (bf == -1) { subR->_bf = 1; parent->_bf = 0; subRL->_bf = 0; } else if (bf == 1) { subR->_bf = 0; parent->_bf = -1; subRL->_bf = 0; } else if (bf == 0) { subR->_bf = 0; parent->_bf = 0; subRL->_bf = 0; } else { cout << "balance factor error!" << endl; assert(false); } }
最后是AVL树所有代码：
#pragma once #include<iostream> #include<assert.h> using namespace std; template<class T> struct AVLTreeNode { AVLTreeNode(const T& data = T()) : _pLeft(nullptr) , _pRight(nullptr) , _pParent(nullptr) , _data(data) , _bf(0) {} AVLTreeNode<T>* _pLeft; AVLTreeNode<T>* _pRight; AVLTreeNode<T>* _pParent; T _data; int _bf; // 节点的平衡因子 }; // AVL: 二叉搜索树 + 平衡因子的限制 template<class T> class AVLTree { public: typedef AVLTreeNode<T> Node; public: AVLTree() : _pRoot(nullptr) {} // 在AVL树中插入值为data的节点 bool Insert(const T& data) { //空树 if (_pRoot == nullptr) { _pRoot = new Node(data); return true; } Node* cur = _pRoot; Node* parent = nullptr; while (cur) { //小于根结点，往左走 if (data < cur->_data) { parent = cur; cur = parent->_pLeft; } //大于根结点，往右走 else if (data > cur->_data) { parent = cur; cur = parent->_pRight; } //相等不插入，返回false else { return false; } } cur = new Node(data); cur->_pParent = parent; //比parent小，插入左边 if (data < parent->_data) { parent->_pLeft = cur; } //比parent大，插入右边 else if (data > parent->_data) { parent->_pRight = cur; } //调整平衡因子 //循环条件parent非空 while (parent) { if (cur == parent->_pLeft) { parent->_bf--; } else { parent->_bf++; } //parent的平衡因子变为0， // 说明树现在已经平衡了，不需要向上调整 if (parent->_bf == 0) { break; } //现在调整为一边高一边低，高度增加了，要向上调整 else if (parent->_bf == -1 || parent->_bf == 1) { //parent已经是根了，不用调整 if (parent == _pRoot) { break; } //parent不是根，需要往上调整 else { cur = parent; parent = cur->_pParent; } } //需要旋转解决 else if (parent->_bf == -2 || parent->_bf == 2) { //纯粹左边高，右单旋 if (parent->_bf == -2 && cur->_bf == -1) { rotateR(parent); break; } //单纯右边高，左单旋 else if (parent->_bf == 2 && cur->_bf == 1) { rotateL(parent); break; } else if (parent->_bf == -2 && cur->_bf == 1) { rotateLR(parent); break; } else if (parent->_bf == 2 && cur->_bf == -1) { rotateRL(parent); break; } else { cout << "balance fator error!" << endl; assert(false); } } else { cout << "Tree is not AVLTree!" << endl; assert(false); } } return true; } // 平衡树的验证 bool IsBalanceTree() { return _IsBalanceTree(_pRoot); } //中序遍历 void InOrder() { _inOrder(_pRoot); cout << endl; } //查找 Node* find(const T& x) { Node* cur = _pRoot; while (cur) { if (x < cur->_data) { cur = cur->_pLeft; } else if (x > cur->_data) { cur = cur->_pRight; } else { return cur; } } return nullptr; } //高度 size_t height() { return _Height(_pRoot); } private: //左右双旋 void rotateLR(Node* parent) { Node* subL = parent->_pLeft; Node* subLR = subL->_pRight; //提前记录subLR的bf，以便后续分类 int bf = subLR->_bf; //先对subL进行左单旋，再对parent进行右单旋 rotateL(subL); rotateR(parent); //分情况更新平衡因子 if (bf == -1) { subL->_bf = 0; parent->_bf = 1; subLR->_bf = 0; } else if (bf == 1) { subL->_bf = -1; parent->_bf = 0; subLR->_bf = 0; } else if (bf == 0) { subL->_bf = 0; parent->_bf = 0; subLR->_bf = 0; } else { cout << "balance factor error!" << endl; assert(false); } } //右左双旋 void rotateRL(Node* parent) { Node* subR = parent->_pRight; Node* subRL = subR->_pLeft; int bf = subRL->_bf; rotateR(subR); rotateL(parent); //分情况更新平衡因子 if (bf == -1) { subR->_bf = 1; parent->_bf = 0; subRL->_bf = 0; } else if (bf == 1) { subR->_bf = 0; parent->_bf = -1; subRL->_bf = 0; } else if (bf == 0) { subR->_bf = 0; parent->_bf = 0; subRL->_bf = 0; } else { cout << "balance factor error!" << endl; assert(false); } } //右单旋 void rotateR(Node* parent) { Node* grandparent = parent->_pParent; Node* subL = parent->_pLeft; Node* subLR = subL->_pRight; //1.判断parent是否是根，链接grandparent与subL if (grandparent == nullptr) { _pRoot = subL; } else { if (grandparent->_pLeft == parent) { grandparent->_pLeft = subL; } else { grandparent->_pRight = subL; } } subL->_pParent = grandparent; //2.链接subL和parent subL->_pRight = parent; parent->_pParent = subL; //3.链接subLR和parent,subLR不为空,subLR的parent要链接parent parent->_pLeft = subLR; if(subLR) subLR->_pParent = parent; //4.修改平衡因子 subL->_bf = parent->_bf = 0; } //左单旋 void rotateL(Node* parent) { Node* grandparent = parent->_pParent; Node* subR = parent->_pRight; Node* subRL = subR->_pLeft; //1.判断parent是否是根，链接grandparent与subR if (grandparent == nullptr) { _pRoot = subR; } else { if (grandparent->_pLeft == parent) { grandparent->_pLeft = subR; } else { grandparent->_pRight = subR; } } subR->_pParent = grandparent; //2.链接subR和parent subR->_pLeft = parent; parent->_pParent = subR; //3.链接subRL和parent parent->_pRight = subRL; if(subRL) subRL->_pParent = parent; //4.修改平衡因子 subR->_bf = parent->_bf = 0; } void _inOrder(Node* root) { if (root == nullptr) return; _inOrder(root->_pLeft); cout << root->_data << " "; _inOrder(root->_pRight); } // 根据AVL树的概念验证pRoot是否为有效的AVL树 bool _IsBalanceTree(Node* pRoot) { if (pRoot == nullptr) return true; int gap = _Height(pRoot->_pRight) - _Height(pRoot->_pLeft); if (abs(gap) >= 2) { cout << "not balanceTree!" << endl; assert(false); } if (pRoot->_bf != gap) { cout << "balance factor error!" << endl; assert(false); } return _IsBalanceTree(pRoot->_pLeft) && _IsBalanceTree(pRoot->_pRight); } size_t _Height(Node* pRoot) { if (pRoot == nullptr) return 0; size_t left = _Height(pRoot->_pLeft); size_t right = _Height(pRoot->_pRight); return left > right ? left + 1 : right + 1; } private: Node* _pRoot; };