为了保持搜索二叉树尽量平衡，设计出了AVL树，这种树得到比一般的搜索二叉树多了一个规则：任意节点的左右子树的高度差小于等于1。当我们进行搜索二叉树的插入时难免会出现违背这个规则的子树，那么我们就需要对这个子树进行旋转。不符合规则的子树一共有4种情况。
右单旋
情况一：本来就是左边高，新增的节点还在左子树的左边。
旋转方法如图所示，很好理解，因为左边比右边高两层，思路就是将左子树的最上面一层（左子树最上面就一个元素也就是左子树的根）向右旋。我们这样思考：先不做变动而将左子树的根看作整棵树的根（这样就是很简单的将左边高度-1，右边高度+1），那这个时候其实就平衡了，但是这个根有三个子树（图中a,b,c+原树的根)，然后可以发现原树的根正好缺失了左子树，而b子树正好可以放到原根的左边。然后整棵树就平衡且高度与没有插入新节点一致。
void RotateR(node* parent)
{
node* subL = parent->_left;
node* subLR = subL->_right;
subL->_right = parent;//先改变subL相应的指针
subL->_parent = parent->_parent;
if (parent == _root) _root = subL;
else
{
if (parent->_parent->_left == parent)//改parent->_parent得到指针
parent->_parent->_left = subL;
else parent->_parent->_right = subL;
}
parent->_parent = subL;//再改parent相应的指针
parent->_left = subLR;
if(subLR) subLR->parent = parent;//修改subLR的指针
parent->_bf = 0;//修改平衡因子
subL->_bf = 0;
}左单旋
情况二：本来就是右边高，新增的节点还在右子树的右边。（思路跟右单旋一样）
void RotateL(node* parent)
{
node* subR = parent->_right;
node* subRL = subR->_left;
//修改subR的相关指针
subR->_parent = parent->_parent;
subR->_left = parent;
if (parent == _root) _root = subR;
else
{
if (parent->_parent->_left == parent)
parent->_parent->_left = subR;
else parent->_parent->_right = subR;
}
if (subRL) subRL->_parent = parent;//修改subRL的相关指针
parent->_right = subRL;//修改parent相应的指针
parent->_parent = subR;//注意这里修改了parent的parent，因为原parent的parent也有指针需要修改，所以要么用变量记录一下，要么将paarent的parent的修改放到后面
subR->_bf = 0;
parent->_bf = 0;
}左右双旋
后面还剩的两种情况不像前面都是一边高新增的节点还在那一边。
情况三：本来是左边高，但是新增的节点在左子树的右边。
看图的话确实也很好理解。将subLR作为新的根，parent作为新根的右子树的根，subL作为新根的左子树的根，此时parent缺少一个左子树，subL缺少一个右子树，c和b两个子树正好能作为他们的子树。左右双旋的左右体现在：先将subLR左单旋，然后就发现这棵树变成了单纯的左边高的树接着将旋转后的subLR右单旋即可。
void RoateLR(node* parent)
{
node* subl = parent->_left;
node* sublr = subl->_right;
int bf = sublr->_bf;
RotateL(subl);
RotateR(parent);
if (bf == -1)
{
subl->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subl->_bf = -1;
parent->_bf = 0;
}
else
{
subl->_bf = 0;
parent->_bf = 0;
}
sublr->_bf = 0;
}右左双旋
情况四：本来是右边高，但是新增的节点在右子树的左边。
void RotateRL(node* parent)
{
node* subr = parent->_right;
node* subrl = subr->_left;
int bf = subrl->_bf;
RotateR(subr);
RotateL(parent);
if (bf == -1)
{
subr->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
subr->_bf = 0;
parent->_bf = -1;
}
else
{
subr->_bf = 0;
parent->_bf = 0;
}
subrl->_bf = 0;
}完整验证代码
#include<iostream>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<math.h>
#include<assert.h>
#include<stack>
#include<vector>
#include<set>
#include<unordered_map>
using namespace std;
template<class k,class v>
class avltreenode
{
public:
pair<k, v> _kv;
avltreenode* _left;
avltreenode* _right;
avltreenode* _parent;
int _bf;
avltreenode(const pair<k,v>& kv):
_kv(kv),
_left(nullptr),
_right(nullptr),
_parent(nullptr),
_bf(0)
{}
};
template <class k,class v>
class avltree
{
public:
typedef avltreenode<k,v> node;
bool insert(const pair<k,v>& kv)
{
node* newnode = new node(kv);
if (_root == nullptr) {
_root = newnode;
return true;
}
node* parent = nullptr;
node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else return false;
}
if (parent->_kv.first > kv.first)
parent->_left = newnode;
else
parent->_right = newnode;
newnode->_parent = parent;
cur = newnode;
//接下来进行更新平衡因子
while (parent != nullptr)
{
if (cur == parent->_right)
parent->_bf++;
else parent->_bf--;
if (parent->_bf == 0)
break;
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)//需要旋转，旋转之后子树的高度跟原来插入时子树的高度是相同的
{
if (parent->_bf == -2 && parent->_left->_bf == -1)
RotateR(parent);
else if (parent->_bf == 2 && parent->_right->_bf == 1)
RotateL(parent);
else if (parent->_bf == -2 && parent->_left->_bf == 1)//左右双旋
RotateLR(parent);
else if (parent->_bf == 2 && parent->_right->_bf == -1)
RotateRL(parent);
else assert(false);
break;
}
else assert(false);
}
return true;
}
void inorder()//中序遍历，关于树的很多函数都是要求从树的根部开始，但是根是私有的，在外面无法访问，所以可以套两层，这就是内层
{
inorder(_root);
}
private:
void inorder(node* cur)//中序遍历，关于树的很多函数都是要求从树的根部开始，但是根是私有的，在外面无法访问，所以可以套两层，这就是内层
{
if (cur == nullptr) return;
inorder(cur->_left); // 先递归遍历左子树
cout << cur->_kv.first << ':' << cur->_kv.second << endl; // 再输出当前节点值
inorder(cur->_right); // 最后递归遍历右子树
}
node* _root=nullptr;
void RotateR(node* parent)
{
node* subL = parent->_left;
node* subLR = subL->_right;
subL->_right = parent;//先改变subL相应的指针
subL->_parent = parent->_parent;
if (parent == _root) _root = subL;
else
{
if (parent->_parent->_left == parent)//改parent->_parent得到指针
parent->_parent->_left = subL;
else parent->_parent->_right = subL;
}
parent->_parent = subL;//再改parent相应的指针
parent->_left = subLR;
if (subLR) subLR->_parent = parent;//修改subLR的指针
parent->_bf = 0;//修改平衡因子
subL->_bf = 0;
}
// 调整后的左旋函数
void RotateL(node* parent)
{
node* subR = parent->_right;
node* subRL = subR->_left;
//修改subR的相关指针
subR->_parent = parent->_parent;
subR->_left = parent;
if (parent == _root) _root = subR;
else
{
if (parent->_parent->_left == parent)
parent->_parent->_left = subR;
else parent->_parent->_right = subR;
}
if (subRL) subRL->_parent = parent;//修改subRL的相关指针
parent->_right = subRL;//修改parent相应的指针
parent->_parent = subR;//注意这里修改了parent的parent，因为原parent的parent也有指针需要修改，所以要么用变量记录一下，要么将paarent的parent的修改放到后面
subR->_bf = 0;
parent->_bf = 0;
}
void RotateLR(node* parent)
{
node* subl = parent->_left;
node* sublr = subl->_right;
int bf = sublr->_bf;
RotateL(subl);
RotateR(parent);
if (bf == -1)
{
subl->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subl->_bf = -1;
parent->_bf = 0;
}
else
{
subl->_bf = 0;
parent->_bf = 0;
}
sublr->_bf = 0;
}
void RotateRL(node* parent)
{
node* subr = parent->_right;
node* subrl = subr->_left;
int bf = subrl->_bf;
RotateR(subr);
RotateL(parent);
if (bf == -1)
{
subr->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
subr->_bf = 0;
parent->_bf = -1;
}
else
{
subr->_bf = 0;
parent->_bf = 0;
}
subrl->_bf = 0;
}
};
int main()
{
avltree<int, string> avl1;
int ch[6] = { 2,3,1,4,6,5 };
vector<string> arr = { "aaa", "bbb", "ccc", "ddd", "eee", "fff" };
for (int i = 0; i < 6; i++)
{
pair<int, string> tmp(ch[i], arr[i]);
avl1.insert(tmp);
}
avl1.inorder();
return 0;
}