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;
}

这两个都过了说明你的树就没问题了