目录
引入
AVL树也是搜索树，其被称为二叉平衡搜索树，AVL树实际上是对二叉树搜索树的一种优化。普通二叉搜索树可能出现极端情况——一端很长，如下，这种极端情况会导致二叉搜索树退化为单枝树，搜索效率急剧下降。
AVL树是基于二叉搜索树出现的，所以其也满足二叉搜索树的要求：左树小于节点，右树大于节点。关于普通二叉搜索树详细介绍课移至上方链接。
概念
AVL树基于普通二叉搜索树基础上，增加了一个要求：左右子树的高度差的绝对值不超过1。
左右子树的高度差又被称为平衡因子，高度差的绝对值不超过1也就意味着平衡因子只能是1，0，-1。
平衡因子的计算方法是：平衡因子=右树高度-左树高度。
下面展示的就是各个节点的平衡因子（以下两棵树非AVL树）。
AVL树也正是通过调节平衡因子时刻保持在正常范围内，使得树不会出现"一边长"的问题。
所以在每一次向二叉树种插入值后，多要进行平衡因子的检查，有平衡因子出错就及时进行调整。
总结AVL树的性质：1）每一个节点的左右子树是AVL树；2）左右子树的平衡因子的绝对值不超过1。
AVL树的实现
AVL树的每一个节点包含：左右子树，父节点，存储的数（数据用pair结构体存储），平衡因子。
template<class K,class V>
struct AVLTreeNode
{
//默认构造函数
AVLTreeNode(const pair<K,V>& kv=pair())
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
pair<K, V> _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf; //平衡因子
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
//默认构造
AVLTree()
:_root(nullptr)
{}
private:
Node* _root; //此处也可以使用缺省值代替默认构造： Node* _root=nullptr;
};插入实现
与普通二叉搜索树一样，AVL树的插入也是先找到合适位置插入。
插入包含3个步骤：1）找数据插入位置并将数据插入；2）向上更新平衡因子；3）当出现错误平衡因子时，对树进行调整。
找合适位置并插入
通过二叉搜索树的性质（左树小于节点，右树大于节点）找到合适位置，再将数据插入到合适位置即可。
//插入
bool Insert(const pair<K, V>& kv)
{
Node* newnode = new Node(kv);
if (_root == nullptr) //空树直接进行替代
{
_root = newnode;
return true;
}
//非空树先找节点插入位置
Node* pcur = _root; //寻找目标位置
Node* parent = nullptr; //保留目标位置的父节点
while (pcur)
{
if (pcur->_kv.first > kv.first)
{
parent = pcur;
pcur = pcur->_left;
}
else if (pcur->_kv.first < kv.first)
{
parent = pcur;
pcur = pcur->_right;
}
else //相等说明节点中已存在，不能再进行插入
{
return false;
}
}
//跳出循环，找到目标位置
//将新节点插入
if (parent->_kv.first > kv.first) //通过父节点与插入数据比较，找到新节点在左还是右
{
parent->_left = newnode;
}
else
{
parent->_right = newnode;
}
newnode->_parent = parent;
//进行平衡因子的调整
//......
}平衡因子更新
更新平衡因子方法：
1）不论如何新插入的节点没有左右子树，所以其平衡因子是0；
2）对于新插入的节点只会影响其所在节点的子树高度，因此只需要向上更新节点平衡因子即可。
3）根据平衡因子计算公式：平衡因子=右树高度-左树高度。当新节点插入到父节点的左树上：父节点平衡因子-1；当插入到父节点的右树上：父节点+1；
4）当向上更新时，父节点平衡因子调整后是0就不需要继续向上更新了。原因：当一个节点平衡因子变成0，不论是其+1还是-1都意味着：新增节点仅仅是使得当前节点的左右树平衡了，当前树的高度并没有发生变化，不需要继续向上调整。
//进行平衡因子的调整
Node* cur = newnode;
while (parent) //此处条件是parent不为空。到达根时，_root的父节点为空，停止调整
{
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
//检查平衡因子
if (parent->_bf == 1 || parent->_bf == -1)
{
//继续向上调整
cur = parent;
parent = cur->_parent;
}
else if (parent->_bf == 0)
{
return true; //插入完成，不用继续向上调整
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//平衡因子错误，对树进行调整
break;
}
else //添加额外的else保证在平衡因子不在预定范围内时即使报错。
{
perror("平衡因子不在范围内");
}
}
if (parent == nullptr)
{
return true;
}平衡因子出错
平衡因子出错分为4中情况，也就对应4种处理方法，依据平衡因子划分。
单旋（一侧高）：1）父节点平衡因子是2，子节点平衡因子是1；
2）父节点平衡因子是-2，子节点平衡因子是-1；
多旋：3）父节点平衡因子是2，子节点平衡因子是-1；
4）父节点平衡因子是-2，直子节点平衡因子是1；
对于平衡因子调整的方法是：
1）保持搜索树的结构；
2）变成平衡树并降低树的高度。
父节点为2，子节点为1
左旋：对于一边高的情况，才有单旋来实现。将父节点左旋，即减小了子树的高度也解决了平衡因子异常的问题。
此处需要调整的节点：parent的父节点和右节点；cur的父节点和右节点；curleft(cur的左节点)父节点。
void RotateL(Node* parent)
{
//调整parent的父节点，右节点
//调整cur的父节点，左节点
//调整curleft的父节点
//调整parent的父节点的指向
Node* pparent = parent->_parent;
Node* cur = parent->_right;
Node* curleft = cur->_left;
cur->_parent = pparent;
if (parent == _root) //注意：如果parent是根，在旋转后要对根进行更新
{
_root = cur;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = cur;
}
else
{
pparent->_right = cur;
}
}
parent->_right = curleft;
parent->_parent = cur;
if(curleft)
curleft->_parent = parent;;
cur->_left = parent;
//将平衡因子进行调整
cur->_bf = parent->_bf = 0;
}
if (parent->_bf == 2 && cur->_bf == 1)
{
//进行左旋
RotateL(parent);
}父节点为-2，子节点为-1
右旋：将父节点进行右旋。
//进行右旋
void RotateR(Node* parent)
{
//调整parent的父节点，左节点
//调整cur的父节点，右节点
//调整curright的父节点
//调整parent的父节点的指向
Node* pparent = parent->_parent;
Node* cur = parent->_left;
Node* curright = cur->_right;
cur->_parent = pparent;
if (parent == _root) //注意：如果parent是根，在旋转后要对根进行更新
{
_root = cur;
}
if (pparent)
{
if (pparent->_left == parent)
{
pparent->_left = cur;
}
else
{
pparent->_right = cur;
}
}
parent->_left = curright;
parent->_parent = cur;
cur->_right = parent;
if(curright)
curright->_parent = parent;
parent->_bf = cur->_bf = 0;
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
//进行右旋
RotateR(parent);
}父节点为2，子节点为-1
右左双旋：对于非单侧高的情况，就不能再仅仅使用单旋来达到结果了。此处需要使用双旋来实现。
采用右左双旋：先以cur为中心进行右旋，再以parent为中心进行左旋。
注意：双选相当于将curleft变成头，将curleft的左支给parent，将cur的右支给cur；因此平衡因子调整要看curleft的平衡因子。
1）curleft是0，parent和cur都是0；
2）curleft是1，parent是-1，cur是0；
3）culeft是-1，parent是0，cur是1；
else if (parent->_bf == 2 && cur->_bf == -1)
{
//右左双旋
//先对cur进行右旋，再对parent进行左旋
Node* curleft = cur->_left;
int bf = cur->_left->_bf;
RotateR(cur);
RotateL(parent);
if (bf == 0)
{
parent->_bf = cur->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
cur->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
cur->_bf = 1;
}
else
{
perror("平衡因子错误");
}
curleft->_bf = 0;
}父节点为-2，子节点为1
左右双旋：对cur进行左旋，对parent进行右旋。
else if (parent->_bf == -2 && cur->_bf == 1)
{
//进行左右双旋
Node* curright = cur->_right;
int bf = cur->_right->_bf;
RotateL(cur);
RotateR(parent);
if (bf == 0)
{
parent->_bf = cur->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
}
else
{
perror("平衡因子错误");
}
curright->_bf = 0;
}插入代码汇总
//插入
bool Insert(const pair<K, V>& kv)
{
Node* newnode = new Node(kv);
if (_root == nullptr) //空树直接进行替代
{
_root = newnode;
return true;
}
//非空树先找节点插入位置
Node* pcur = _root; //寻找目标位置
Node* parent = nullptr; //保留目标位置的父节点
while (pcur)
{
if (pcur->_kv.first > kv.first)
{
parent = pcur;
pcur = pcur->_left;
}
else if (pcur->_kv.first < kv.first)
{
parent = pcur;
pcur = pcur->_right;
}
else //相等说明节点中已存在，不能再进行插入
{
return false;
}
}
//跳出循环，找到目标位置
//将新节点插入
if (parent->_kv.first > kv.first) //通过父节点与插入数据比较，找到新节点在左还是右
{
parent->_left = newnode;
}
else
{
parent->_right = newnode;
}
newnode->_parent = parent;
//进行平衡因子的调整
//进行平衡因子的调整
Node* cur = newnode;
while (parent) //此处条件是parent不为空。到达根时，_root的父节点为空，停止调整
{
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
//检查平衡因子
if (parent->_bf == 1 || parent->_bf == -1)
{
//继续向上调整
cur = parent;
parent = cur->_parent;
}
else if (parent->_bf == 0)
{
return true; //插入完成，不用继续向上调整
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//平衡因子错误，对树进行调整
break;
}
else //添加额外的else保证在平衡因子不在预定范围内时即使报错。
{
perror("平衡因子不在范围内");
}
}
if (parent == nullptr)
{
return true;
}
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)
{
//右左双旋
//先对cur进行右旋，再对parent进行左旋
Node* curleft = cur->_left;
int bf = cur->_left->_bf;
RotateR(cur);
RotateL(parent);
if (bf == 0)
{
parent->_bf = cur->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
cur->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
cur->_bf = 1;
}
else
{
perror("平衡因子错误");
}
curleft->_bf = 0;
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
//进行左右双旋
Node* curright = cur->_right;
int bf = cur->_right->_bf;
RotateL(cur);
RotateR(parent);
if (bf == 0)
{
parent->_bf = cur->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
}
else
{
perror("平衡因子错误1");
}
curright->_bf = 0;
}
return true;
}函数检查
在写完AVL树后，需要对树进行检查，而如果通过调试窗口一次次对比效率太低了。此处可以使用函数来完成检查，AVL树的关键就是平衡因子是否正确，所以此处可以设计一个函数完成平衡因子的检测。通过得出左右子树的高度确定真实的平衡因子，再去与当前节点存储的平衡因子进行对比。
bool Isbance()
{
return Isbance(_root);
}
int Height(Node* root)
{
if (root == nullptr)
return 0;
int leHeight = Height(root->_left);
int riHeight = Height(root->_right);
if (leHeight > riHeight)
{
return leHeight + 1;
}
else
{
return riHeight + 1;
}
}
private:
bool Isbance(Node* root)
{
if (root==nullptr)
return true;
int leftheight = Height(root->_left); //得到树的高度进而确定平衡因子
int rightheight = Height(root->_right);
if (root->_bf < -1 || root->_bf>1)
{
perror("failed");
}
if (root->_bf!=rightheight-leftheight) //检查平衡因子是否正确
{
cout << root->_kv.first << " 平衡因子错误" << endl;
}
return Isbance(root->_left) && Isbance(root->_right);
}