AVL tree 是一个“加上了额外平衡条件”的二叉搜索树，其平衡条件的建立是为了保证整棵树的深度为O(logN)。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)AVL树节点的定义
template<class T> struct AVLTreeNode { AVLTreeNode(const T& data) : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr) , _data(data), _bf(0) {} AVLTreeNode<T>* _pLeft; // 该节点的左孩子 AVLTreeNode<T>* _pRight; // 该节点的右孩子 AVLTreeNode<T>* _pParent; // 该节点的双亲 T _data; int _bf; // 该节点的平衡因子 };AVL树的插入
按照二叉搜索树的方式插入新节点 调整节点的平衡因子AVL树的旋转
新节点插入较高左子树的左侧—左左：右单旋
新节点插入较高右子树的右侧—右右：左单旋
新节点插入较高左子树的右侧—左右：先左单旋再右单旋
新节点插入较高右子树的左侧—右左：先右单旋再左单旋
总结： 假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR 当pSubR的平衡因子为1时，执行左单旋 当pSubR的平衡因子为-1时，执行右左双旋pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL 当pSubL的平衡因子为-1是，执行右单旋 当pSubL的平衡因子为1时，执行左右双旋 旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。模拟avl tree的插入
#include<iostream> #include<stack> using namespace std; template<class Type> class AVLTree; //avl node template<class Type> class AVLNode { friend class AVLTree<Type>; public: AVLNode(Type d = Type(), AVLNode<Type>*left = nullptr, AVLNode<Type>*right = nullptr) : data(d), leftChild(left), rightChild(right), bf(0) {} ~AVLNode() {} private: Type data; AVLNode<Type> *leftChild; AVLNode<Type> *rightChild; int bf; //平衡因子 }; //avl tree template<class Type> class AVLTree { public: AVLTree() :root(nullptr) {} public: bool Insert(const Type &x) { return Insert(root, x); } bool Remove(const Type &key) { return Remove(root, key); } protected: bool Insert(AVLNode<Type> *&t, const Type &x); bool Remove(AVLNode<Type> *&t, const Type &key); void RotateR(AVLNode<Type> *&ptr); void RotateLR(AVLNode<Type> *&ptr); void RotateL(AVLNode<Type> *&ptr); void RotateRL(AVLNode<Type> *&ptr); private: AVLNode<Type> *root; }; //1 调整平衡 2更改bf template<class Type> void AVLTree<Type>::RotateR(AVLNode<Type> *&ptr) { AVLNode<Type> *subR = ptr; ptr = subR->leftChild; subR->leftChild = ptr->rightChild; ptr->rightChild = subR; ptr->bf = subR->bf = 0; } template<class Type> void AVLTree<Type>::RotateLR(AVLNode<Type> *&ptr) { AVLNode<Type> *subL = ptr->leftChild; AVLNode<Type> *subR = ptr; ptr = subL->rightChild; subL->rightChild = ptr->leftChild; ptr->leftChild = subL; //更新 subL->bf if (ptr->bf <= 0) subL->bf = 0; else subL->bf = -1; subR->leftChild = ptr->rightChild; ptr->rightChild = subR; //更新 subR->bf if (ptr->bf >= 0) subR->bf = 0; else subR->bf = 1; ptr->bf = 0; } template<class Type> void AVLTree<Type>::RotateL(AVLNode<Type> *&ptr) { AVLNode<Type> *subL = ptr; ptr = subL->rightChild; subL->rightChild = ptr->leftChild; ptr->leftChild = subL; ptr->bf = subL->bf = 0; } template<class Type> void AVLTree<Type>::RotateRL(AVLNode<Type> *&ptr) { AVLNode<Type> *subL = ptr; AVLNode<Type> *subR = ptr->rightChild; ptr = subR->leftChild; subR->leftChild = ptr->rightChild; ptr->rightChild = subR; //更新subR->bf if (ptr->bf >= 0) subR->bf = 0; else subR->bf = 1; subL->rightChild = ptr->leftChild; ptr->leftChild = subL; //更新subL->bf if (ptr->bf == 1) subL->bf = -1; else subL->bf = 0; ptr->bf = 0; } template<class Type> bool AVLTree<Type>::Insert(AVLNode<Type> *&t, const Type &x) { //1 按照BST的规则插入节点 AVLNode<Type> *pr = nullptr; AVLNode<Type> *p = t; stack<AVLNode<Type>*> st; while (p != nullptr) { //用于查找x的插入位置 if (x == p->data) return false; pr = p; st.push(pr); if (x < p->data) p = p->leftChild; else p = p->rightChild; } p = new AVLNode<Type>(x); if (pr == nullptr) { t = p; return true; } //链接新建节点 if (x < pr->data) pr->leftChild = p; else pr->rightChild = p; //2 如果发生不平衡，需要调整平衡 while (!st.empty()) { pr = st.top(); st.pop(); if (p == pr->leftChild) pr->bf--; else pr->bf++; if (pr->bf == 0) break; if (pr->bf == 1 || pr->bf == -1) // |bf| == 1 向上回溯 p = pr; else { //|bf| == 2 发生不平衡 调整平衡 if (p == pr->leftChild) //左分支 { if (p->bf < 0) // / { RotateR(pr); //cout<<"RotateR."<<endl; } else // < { RotateLR(pr); //cout<<"RotateLR."<<endl; } } else //右分支 { if (p->bf > 0) // \ { RotateL(pr); //cout<<"RotateL."<<endl; } else // > { RotateRL(pr); //cout<<"RotateRL."<<endl; } } break; } } //重新链接 if (st.empty()) t = pr; else { AVLNode<Type> *ppr = st.top(); if (ppr->data > pr->data) ppr->leftChild = pr; else ppr->rightChild = pr; } return true; }