AVL树的旋转
目录
1.平衡因子
2.旋转
a.节点定义
b.插入
插入
平衡因子更新
旋转
左单旋
右单旋
右左双旋
左右双旋
3.AVL树的验证
1.平衡因子
我们知道搜索二叉树有缺陷，就是不平衡，比如下面的树
什么是搜索树的平衡？就是每个节点的左右子树的高度差不超过1，称平衡的搜索树为AVL树， 那我们怎么控制搜索树的平衡呢？
给出了平衡因子，每个节点的平衡因子=节点右子树的高度-节点左子树的高度（或者反过来，我们用前面那种）平衡因子=[-1,1],当超出这个范围，搜索树就不平衡了
树的平衡因子可以这样表示：
2.旋转
a.节点定义
template<class K,class V>
class AVLNode
{
public:typedef AVLNode<K,V> Node;AVLNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}Node* _left;Node* _right;Node* _parent;pair<K, V> _kv;//库里面提供的结构体，表示key和valueint _bf;//平衡因子};
b.插入
插入
左边小插左边，右边大插右边
template<class K,class V>
class AVLTree
{
public:typedef AVLNode<K, V> Node;bool insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv .first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//更新平衡因子//...............return true;}protected:
//........
private:Node* _root=nullptr；
};平衡因子更新
前面都好理解插入一个节点，那插入节点后平衡因子怎么更新呢？
//更新平衡因子while (parent){if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 1 || parent->_bf == -1){//继续更新parent = parent->_parent;cur =cur->_parent;}else if (parent->_bf == 0){//已经平衡break;}else if (parent->_bf == 2 || parent->_bf == -2){//进行旋转//...........}else{assert(false);//有可能不会出现上面的情况，出现大问题了，立马断死}break;//直接跳出了}旋转
有四种情况需要旋转
else if (parent->_bf == 2 || parent->_bf == -2){// 进行旋转处理 -- 1、让这颗子树平衡 2、降低这颗子树的高度if(parent->_bf==2&&cur->_bf==1){ }else if (parent->_bf == 2 && cur->_bf == -1){}else if (parent->_bf == -2 && cur->_bf == 1){}else if (parent->_bf == -2 && cur->_bf == -1){}else{assert(false);//有可能不会出现上面的情况，出现大问题了，立马断死}}
左单旋
代码怎么写呢？
是不是感觉这样就链接上了，其实不对的，每个节点的父亲也要更新的
你以为又结束了吗？
protected:void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)//有可能subRL是空subRL->_parent = parent;//记录父亲的父亲节点Node* pparent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (pparent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}//更新平衡因子parent->_bf = subR->_bf = 0; }总结：更新节点指向是一定要更新他的父亲节点的指向
右单旋
和左单旋是类似的，读者可以模仿上面来分析，自己把它写出来
void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subR->_right;parent->_left = subLR;if (subLR) //有可能subLR是空subLR->_parent = parent;//记录父亲的父亲节点Node* pparent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (pparent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}//更新平衡因子parent->_bf = subL->_bf = 0;}右左双旋
代码怎么写呢？
我们可以对单旋进行复用
这样就可以了吗？不是，单旋会把平衡因子都置为0，所以还要更新平衡因子
void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//记录平衡因子int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);//更新平衡因子if (bf == 1){subRL->_bf = 0;subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subRL->_bf = 0;subR->_bf = 1;parent->_bf = 0;}else if (bf == 0){subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else{assert(false);}}左右双旋
类似的，读者自行分析
void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1){parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else if (bf == -1){parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf== 0){parent->_bf = 0;subLR->_bf = 0;subL->_bf = 0;}else{assert(false);}}else if (parent->_bf == 2 || parent->_bf == -2){// 进行旋转处理 -- 1、让这颗子树平衡 2、降低这颗子树的高度if(parent->_bf==2&&cur->_bf==1){ RotateL(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else{assert(false);//有可能不会出现上面的情况，出现大问题了，立马断死}break;//直接跳出}3.AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1. 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)，节点的平衡因子是否计算正确
第一点很简单啦！！！！
void Inorder(){_Inorder(_root);cout << endl;}
void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_kv.first << ' ';_Inorder(root->_right);}怎么验证平衡树呢？
bool Isbalance(){return _Isbalance(_root);}bool _Isbalance(Node* root){if (root == nullptr)return true;int leftH = _Height(root->_left);int rightH = _Height(root->_right);//用于快速判断哪个节点错误if (rightH - leftH != root->_bf){cout << root->_kv.first << "节点平衡因子异常" << endl;return false;}//不只检查本节点左右子树的平衡，其他节点的子树也要检查return abs(leftH - rightH) < 2&& _Isbalance(root->_left)&& _Isbalance(root->_right);}int Height(){return _Height(_root);}int _Height(Node* root){if (root == nullptr){return 0;}int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH+ 1;}你们可以用这两个用例
void testAVLtree1()
{/*int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };*/int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTree<int, int> av;for (auto e : a){if (e == 14){int a = 0;}av.Insert(make_pair(e, e));}av.Inorder();cout << av.Isbalance()<<endl;
}也要用随机数验证
void testAVLtree2()
{srand(time(0));const size_t N = 500000;AVLTree<int, int> t;for (size_t i = 0; i < N; ++i){size_t x = rand() + i;t.Insert(make_pair(x, x));//cout << t.IsBalance() << endl;}//t.Inorder();cout << t.Isbalance() << endl;cout << t.Height() << endl;
}
这两个都过了说明你的树就没问题了