移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——14.AVL树

1.AVL 树

1.1AVL 树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1.它的左右子树都是AVL树

2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(log_2 n)，搜索时间复杂度O(log_2 n)。

2.AVL树节点的定义 

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;//右子树高度-左子树高度,只有孩子发生变化，bf才有可能发生变化！！！！，若改变父亲，bf不变！！！！！！AVLtreenode(const pair<K, V>& _kv)    //初始化列表:_left(nullptr),_right(nullptr),_parent(nullptr),kv(_kv),bf(0){}
};

3.AVL树的插入！！！！！！！ 

3.1初步插入

初步插入与bst的插入一致，不过里面的数据类型是pair<first,second>,并且是根据first进行比较

if (root == nullptr)
{root = new node(_kv);return true;
}
node* parent = nullptr; //比bst多了一个parent
node* cur = root;       //while (cur)
{parent = cur;if (cur->kv.first < _kv.first){cur = cur->_right;}else if (cur->kv.first > _kv.first){cur = cur->_left;}else{return false;}
}
cur = new node(_kv);
if (parent->kv.first < _kv.first)
{parent->_right = cur;
}
else
{parent->_left = cur;
}
cur->_parent = parent;    //记得连接parent和cur

3.2调整平衡因子 

while (cur != root)
{if (cur == parent->_left)parent->bf--;//第一次！！！检查parent左边原来必为空else {parent->bf++;//第一次！！！检查parent右边原来必为空}if (parent->bf == 0) //相当于bf没改变，可直接退出{break;}else if (parent->bf == 1 || parent->bf == -1) //bf改变了继续向上找   {cur = parent;parent = parent->_parent;}else if(parent->bf == -2 || parent->bf == 2){          //-2||2,需要调整（旋转）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);//先左旋再右旋}//旋转让子树变得平衡//旋转降低了子树的高度，恢复到和插入前一样的高度，所以对上一层没有影响break;//1次旋转完成后不需要再调整了}
}

3.3旋转调整！！！！！！ 

1.新节点插入较高右子树的右侧---右右：左单旋

 

 由上述可知，c必定是x类型的avl树，如果是其他类型的，可能60这个节点的平衡因子就变成-2或2了，（当然，这只是单独举一个例子分析，便于分析代码，不代表所有情况）

void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）//   1.右右
{node* subr = parent->_right;node* subrl = subr->_left;parent->_right = subrl;subr->_left= parent;node* ppnode = parent->_parent;parent->_parent = subr;if (subrl) //subrl可能为空！！！！！！！！！！！！！！！{subrl->_parent = parent;}if (parent == root) // 即如果parent->_parent==nullptr{root = subr;subr->_parent = nullptr;}else{if (ppnode->_left == parent)   //需要再查找一下放左边还是右边{ppnode->_left = subr;}else if (ppnode->_right == parent){ppnode->_right = subr;}subr->_parent = ppnode;}parent->bf = subr->bf = 0;   //重置平衡因子
}

2.新节点插入较高左子树的左侧---左左：右单旋 

和左单旋分析方法一致

void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）//   2.左左
{node* subl = parent->_left;node* sublr = subl->_right;parent->_left = sublr;if (sublr)               //sublr可能为空！！！！！！！sublr->_parent = parent;node* ppnode = parent->_parent;subl->_right = parent;parent->_parent=subl;if (root == parent){root = subl;subl->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subl;}else if (ppnode->_right == parent){ppnode->_right = subl;}subl->_parent = ppnode;}subl->bf = parent->bf = 0;//重置平衡因子}

3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋

十分巧妙的是：经过一次左旋(parent->_left)后，就变成左左类型了，这样就能复用右单旋(parent)达成平衡 

void rotateLR(node* parent)//左旋一次，再右旋一次，还需要根据不同的_bf更新平衡因子
{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 = 0;subl->bf = -1;sublr->bf = 0;}else if (_bf == -1){//sublr的左子树新增parent->bf = 1;subl->bf = 0;sublr->bf = 0;}
}

4.新节点插入较高右子树的左侧---右左：先右单旋再左单旋  

与上方分析方法一致

void rotateRL(node* parent)   //右旋一次，再左旋一次，还需要根据不同的_bf更新平衡因子
{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;subr->bf = 1;subrl->bf = 0;}else if (_bf == 1){   //subrl的左子树新增parent->bf = -1;subr->bf = 0;subrl->bf = 0;}
}

总结：

假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR

当pSubR的平衡因子为1时，执行左单旋

当pSubR的平衡因子为-1时，执行右左双旋

2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL

当pSubL的平衡因子为-1是，执行右单旋

当pSubL的平衡因子为1时，执行左右双旋

旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。  

4.AVL树的判断 

 AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树

：如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2. 验证其为平衡树

（1）每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

（2）节点的平衡因子是否计算正确  

void inorder()
{_inorder(root);
}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 lh = _height(root->_left);int rh = _height(root->_right);return lh > rh ? lh + 1 : rh + 1;//记得+1
}bool isbalance()
{return _isbalance(root);
}bool _isbalance(node* root)
{if (root == nullptr)return true;int lh = _height(root->_left);int rh = _height(root->_right);if ((rh - lh) !=root->bf)//判断是否符合平衡因子计算公式{cout << "异常" << endl;return false;}return (rh - lh) <2 && (rh - lh)>-2 && _isbalance(root->_left) && _isbalance(root->_right);//递归判断左右子树
}

5.完整代码 

 AVL.h：

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;//右子树高度-左子树高度,只有孩子发生变化，bf才有可能发生变化！！！！，若改变父亲，bf不变！！！！！！AVLtreenode(const pair<K, V>& _kv):_left(nullptr),_right(nullptr),_parent(nullptr),kv(_kv),bf(0){}
};template<class K, class V>
class AVLtree
{
public:typedef AVLtreenode<K, V> node;bool insert(const pair<K,V>& _kv){if (root == nullptr){root = new node(_kv);return true;}node* parent = nullptr; //比bst多了一个parentnode* cur = root;       //while (cur){parent = cur;if (cur->kv.first < _kv.first){cur = cur->_right;}else if (cur->kv.first > _kv.first){cur = cur->_left;}else{return false;}}cur = new node(_kv);if (parent->kv.first < _kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//开始调整//调整平衡因子while (cur != root){if (cur == parent->_left)parent->bf--;//第一次！！！检查parent左边原来必为空else {parent->bf++;//第一次！！！检查parent右边原来必为空}if (parent->bf == 0) //相当于bf没改变，可直接退出{break;}else if (parent->bf == 1 || parent->bf == -1) //bf改变了继续向上找   {cur = parent;parent = parent->_parent;}else if(parent->bf == -2 || parent->bf == 2){          //-2||2,需要调整（旋转）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);//先左旋再右旋}//旋转让子树变得平衡//旋转降低了子树的高度，恢复到和插入前一样的高度，所以对上一层没有影响break;//1次旋转完成后不需要再调整了}}return true;}void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）//   1.右右{node* subr = parent->_right;node* subrl = subr->_left;parent->_right = subrl;subr->_left= parent;node* ppnode = parent->_parent;parent->_parent = subr;if (subrl) //subrl可能为空！！！！！！！{subrl->_parent = parent;}if (parent == root) //即如果parent->_parent==nullptr{root = subr;subr->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subr;}else if (ppnode->_right == parent){ppnode->_right = subr;}subr->_parent = ppnode;}parent->bf = subr->bf = 0;   //重置平衡因子}void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）//   2.左左{node* subl = parent->_left;node* sublr = subl->_right;parent->_left = sublr;if (sublr)               //sublr可能为空！！！！！！！sublr->_parent = parent;node* ppnode = parent->_parent;subl->_right = parent;parent->_parent=subl;if (root == parent){root = subl;subl->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subl;}else if (ppnode->_right == parent){ppnode->_right = subl;}subl->_parent = ppnode;}subl->bf = parent->bf = 0;}void rotateRL(node* parent)   //右旋一次，再左旋一次，还需要根据不同的_bf更新平衡因子{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;subr->bf = 1;subrl->bf = 0;}else if (_bf == 1){   //subrl的左子树新增parent->bf = -1;subr->bf = 0;subrl->bf = 0;}}void rotateLR(node* parent)//左旋一次，再右旋一次，还需要根据不同的_bf更新平衡因子{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 = 0;subl->bf = -1;sublr->bf = 0;}else if (_bf == -1){//sublr的左子树新增parent->bf = 1;subl->bf = 0;sublr->bf = 0;}}void inorder(){_inorder(root);}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 lh = _height(root->_left);int rh = _height(root->_right);return lh > rh ? lh + 1 : rh + 1;}bool isbalance(){return _isbalance(root);}bool _isbalance(node* root){if (root == nullptr)return true;int lh = _height(root->_left);int rh = _height(root->_right);if ((rh - lh) !=root->bf){cout << "异常" << endl;return false;}return (rh - lh) <2 && (rh - lh)>-2 && _isbalance(root->_left) && _isbalance(root->_right);}private:node* root = nullptr;
};

test.c:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<map>using namespace std;#include"AVL.h"int main()
{int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLtree<int, int> it;for (auto i : arr){it.insert(make_pair(i,i));}it.inorder();cout << endl<<it.isbalance() << endl;return 0;
}

6.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即$og_2 (N)。但是如果要对AVL树做一些结构修改的操 作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时， 有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数 据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。