1.AVL树的特性二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。一棵AVL树是空树或者是具有以下性质的二叉搜索树-它的左右子树都是AVL树-左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)用右子树减左子树高度表示左右子树高度之差平衡因子下图用蓝色表示节点的平衡因子如图为一棵AVL树因为要控制平衡因子AVL树节点相比于普通二叉树节点增加了平衡因子、父节点指针便于找到父节点控制平衡因子模拟AVL树节点的定义如下templateclass T struct AVLTreeNode { AVLTreeNode(const T val) : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr) , _val(val), _bf(0) {} AVLTreeNodeT* _pLeft;// 该节点的左孩子 AVLTreeNodeT* _pRight; // 该节点的右孩子 AVLTreeNodeT* _pParent; // 该节点的双亲 T _val; // 该节点储存的数据 int _bf; // 该节点的平衡因子 };2.AVL插入时如何维持平衡AVL树插入时首先要遵循二叉搜索树的规则找到对应插入位置注意节点_pParent的链接2.1找到插入位置插入并链接Node* newnode new Node(x); Node* cur _root; Node* parent nullptr; if (_root nullptr) { _root newnode; return true; } //使用cur找到插入位置 while (cur) { if (cur-_val x) { return false; } else if (cur-_val x) { parent cur; cur cur-_pRight; } else if (cur-_val x) { parent cur; cur cur-_pLeft; } } //链接节点 if (x parent-_val) { parent-_pLeft newnode; } else { parent-_pRight newnode; } newnode-_pParent parent; cur newnode;在插入前这棵树就是一块AVL树遵循AVL树的规则在插入后可能会破坏规则就要继续向祖先更新、查看平衡因子。2.2更新平衡因子在插入后parent节点平衡因子存在3种情况有的情况发现此子树的高度不变就不必向上继续更新若parent的平衡因子用一个循环实现向上更新更新后平衡因子存在以下几种情况1.平衡因子 0说明parent插入前不平衡插入在短的那边插入后平衡了插入后高度不变不需要往上更新2.平衡因子 1或-1说明parent插入前平衡插入后不左右子树高度差改变的那parent所在树高度更新需继续往上更新3.parent的平衡因子 2或-2说明parent插入前平衡因子 1 或 -1插入在长的那边了加剧了parent的不平衡此时已经违反规则需要旋转处理调整while (parent) { //使用循环向上更新 //更新平衡因子 if (cur parent-_pLeft) { parent-_bf--; } else if (cur parent-_pRight) { parent-_bf; } //继续向上更新 //若已经更新到根停止 if (parent nullptr) { break; } //1.若此时parent已经平衡(0)说明插入节点使子树平衡并没有增加子树高度不用往上更新 if (parent-_bf 0) { break; } //2.若此时parent为弱平衡(_bf -1/1),说明插入节点使原本平衡的树高度更新需继续往上更新 else if (parent-_bf -1 || parent-_bf 1) { } //3.若此时parent已经失衡(_bf -2/2),说明插入节点使原本弱平衡的树加剧失衡需要旋转处理、调整 else if (parent-_bf -2 || parent-_bf 2) { //单独的一边高subLL、subRR高单旋 if (parent-_bf -2 parent-_pLeft-_bf -1) { RotatoR(parent); } else if (parent-_bf 2 parent-_pRight-_bf 1) { RotatoL(parent); } //subRL、subLR高双旋。例先将subR子树旋转为subRR高的情况再使用单次左旋 else if (parent-_bf -2 parent-_pLeft-_bf 1) { RotatoLR(parent); } else if (parent-_bf 2 parent-_pRight-_bf -1) { RotatoRL(parent); } //旋转后这棵子树高度并没有增加不向上继续更新 break; } else { assert(false); } //迭代继续向上更新 cur parent; parent parent-_pParent; }旋转最后得到的结果1.遵循搜索树的规则2.控制平衡降低高度而旋转时分为以下几种情况2.3旋转调整2.1.1.subRR/subLL长的时候树的旋转调整如图若插入在subRR处parent节点的平衡因子违反了规则需要调整此子树使之符合规则。若插入在subLL处与插入在subRR处类似下图中a、b、c为抽象的树h为抽象的树的高度h 0时表示空思想将parent及其左子树链接到subR的左边使parent子树高度与subRL一样高具体操作为将parent链接到subR的左边将subRL链接到parent的右边代码实现如下记得要更新平衡因子//单次左旋适用于subRR长的情况 //思想将原来根放到subR的左边使parent子树高度与subRL一样高 void RotatoL(Node* parent) { Node* subR parent-_pRight; Node* subRL subR-_pLeft; Node* parentParent parent-_pParent; //先链接节点 if (subRL ! nullptr) subRL-_pParent parent; parent-_pRight subRL; parent-_pParent subR; subR-_pLeft parent; subR-_pParent parentParent; if (parentParent nullptr) { //若parentParent为空则原Parent为整个树的根 _root subR; } else { if (subR-_val parentParent-_val) { parentParent-_pLeft subR; } else if (subR-_val parentParent-_val) { parentParent-_pRight subR; } } //再更新平衡因子 parent-_bf subR-_bf 0; }2.1.2.subRL/subLR长的时候的调整如图插入节点后subRL长此时无法像上面那样使用左旋使subRR与subRL链接到parent右边树一样高若插入在subLR处调整方法类似图1.subRL长时的插入这时我们可以想办法旋转使subRR变长我们将subRL再具体细分h为抽象树的高度h 0 时表示40为新插入节点这时我们可以先调整 subR为根的子树使用一次旋转使得subR所在子树较长变为subRR长的情况可以单次旋转调整最后再单次右旋整体旋转方法如下图记得更新平衡因子若初始为b长parent最后平衡因子为0subR最后平衡因子为1若初始为c长parent最后平衡因子为-1subR最后平衡因子为0若subRL为新插入节点则h 0则a、b、c、d都为空parent和subR最后平衡因子都为0代码如下//先右旋再左旋适用于subRL高的情况 //思想先将subR子树旋转为subRR高的情况再使用单次左旋 void RotatoRL(Node* parent) { Node* subR parent-_pRight; Node* subRL subR-_pLeft; //可能subRLL长或subRLR长通过记录subRL原来的bf调整最后bf int bf subRL-_bf; //两次旋转旋转后平衡因子有误 RotatoR(subR); RotatoL(parent); //再更新平衡因子 subRL-_bf 0; if (bf 1) { subR-_bf 0; parent-_bf -1; } else if (bf -1) { subR-_bf 1; parent-_bf 0; } else { subR-_bf 0; parent-_bf 0; } }3.插入的整体代码bool Insert(T x) { Node* newnode new Node(x); Node* cur _root; Node* parent nullptr; if (_root nullptr) { _root newnode; return true; } //使用cur找到插入位置 while (cur) { if (cur-_val x) { return false; } else if (cur-_val x) { parent cur; cur cur-_pRight; } else if (cur-_val x) { parent cur; cur cur-_pLeft; } } //链接节点 if (x parent-_val) { parent-_pLeft newnode; } else { parent-_pRight newnode; } newnode-_pParent parent; cur newnode; while (parent) { //使用循环向上更新 //更新平衡因子 if (cur parent-_pLeft) { parent-_bf--; } else if (cur parent-_pRight) { parent-_bf; } //继续向上更新 //若已经更新到根停止 if (parent nullptr) { break; } //1.若此时parent已经平衡(0)说明插入节点使子树平衡并没有增加子树高度不用往上更新 if (parent-_bf 0) { break; } //2.若此时parent为弱平衡(_bf -1/1),说明插入节点使原本平衡的树高度更新需继续往上更新 else if (parent-_bf -1 || parent-_bf 1) { } //3.若此时parent已经失衡(_bf -2/2),说明插入节点使原本弱平衡的树加剧失衡需要旋转处理、调整 else if (parent-_bf -2 || parent-_bf 2) { //单独的一边高subLL、subRR高单旋 if (parent-_bf -2 parent-_pLeft-_bf -1) { RotatoR(parent); } else if (parent-_bf 2 parent-_pRight-_bf 1) { RotatoL(parent); } //subRL、subLR高双旋。例先将subR子树旋转为subRR高的情况再使用单次左旋 else if (parent-_bf -2 parent-_pLeft-_bf 1) { RotatoLR(parent); } else if (parent-_bf 2 parent-_pRight-_bf -1) { RotatoRL(parent); } //旋转后这棵子树高度并没有增加不向上继续更新 break; } else { assert(false); } //迭代继续向上更新 cur parent; parent parent-_pParent; } return true; } //单次左旋适用于subRR长的情况 //思想将原来根放到subR的左边使parent子树高度与subRL一样高 void RotatoL(Node* parent) { Node* subR parent-_pRight; Node* subRL subR-_pLeft; Node* parentParent parent-_pParent; //先链接节点 if (subRL ! nullptr) subRL-_pParent parent; parent-_pRight subRL; parent-_pParent subR; subR-_pLeft parent; subR-_pParent parentParent; if (parentParent nullptr) { //若parentParent为空则原Parent为整个树的根 _root subR; } else { if (subR-_val parentParent-_val) { parentParent-_pLeft subR; } else if (subR-_val parentParent-_val) { parentParent-_pRight subR; } } //再更新平衡因子 parent-_bf subR-_bf 0; } //单次右旋与左旋思想类似 void RotatoR(Node* parent) { Node* subL parent-_pLeft; Node* subLR subL-_pRight; Node* parentParent parent-_pParent; if (subLR ! nullptr) subLR-_pParent parent; parent-_pLeft subLR; parent-_pParent subL; subL-_pRight parent; subL-_pParent parentParent; if (parentParent nullptr) { _root subL; } else { if (parent parentParent-_pLeft) { parentParent-_pLeft subL; } else if (parent parentParent-_pRight) { parentParent-_pRight subL; } } //再更新平衡因子 parent-_bf subL-_bf 0; } //先右旋再左旋适用于subRL高的情况 //思想先将subR子树旋转为subRR高的情况再使用单次左旋 void RotatoRL(Node* parent) { Node* subR parent-_pRight; Node* subRL subR-_pLeft; //可能subRLL长或subRLR长通过记录subRL原来的bf调整最后bf int bf subRL-_bf; //两次旋转旋转后平衡因子有误 RotatoR(subR); RotatoL(parent); //再更新平衡因子 subRL-_bf 0; if (bf 1) { subR-_bf 0; parent-_bf -1; } else if (bf -1) { subR-_bf 1; parent-_bf 0; } else { subR-_bf 0; parent-_bf 0; } } //先左旋再右旋 void RotatoLR(Node* parent) { Node* subL parent-_pLeft; Node* subLR subL-_pRight; int bf subLR-_bf; //两次旋转旋转后平衡因子有误 RotatoL(subL); RotatoR(parent); //再更新平衡因子 subLR-_bf 0; if (bf 1) { subL-_bf -1; parent-_bf 0; } else if (bf -1) { subL-_bf 0; parent-_bf 1; } else { subL-_bf 0; parent-_bf 0; } }在实现后可以中序遍历整棵树检查是否为二叉搜索树。并且检查其平衡因子是否符合规则确定其为平衡树。//获取高度 int Height() { return _Height(_root); } //判断是否为平衡树 bool IsBalanceTree() { return _IsBalanceTree(_root); } //判断是否为平衡树 bool _IsBalanceTree(Node* root) { // 空树也是AVL树 if (root nullptr) { return true; } int leftTreeHeight _Height(root-_pLeft); int rightTreeHeight _Height(root-_pRight); int diff rightTreeHeight - leftTreeHeight; //验证root是不是平衡树 if (root-_bf diff diff -1 diff 1) { //验证其左右子树是不是平衡树 return _IsBalanceTree(root-_pLeft) _IsBalanceTree(root-_pRight); } else { return false; } } //获取高度 int _Height(Node* root) { if (root nullptr) { return 0; } int leftTreeHeight _Height(root-_pLeft); int rightTreeHeight _Height(root-_pRight); return (leftTreeHeight rightTreeHeight) ? leftTreeHeight 1 : rightTreeHeight 1; }