和普通的二叉搜索树的区别：
普通的二叉搜索树 只满足左子树小于个根，右子树大于根，不会进行平衡（降低高度）这就导致可能退化，这样查找插入数据的时间复杂度就是o（n）
而为了防止二叉搜索树退化，AVL树引入了 平衡因子 的概念，使树的每一层都是满的，只有树的一层满后才插入下一层，利用 平衡因子就可以达成这样的效果
平衡因子：
右子树高度减去左子树高度，范围在【-1，1】，
在进行插入的时候，先找到要插入的位置，然后更新被插入节点的祖宗的 平衡因子
平衡因子的更新
插在父节点的左边，父节点的平衡因子自减1，插在左边自增1，接着向上更新
插入后父节点平衡因子的大小
正负1 之前父节点的平衡因子为0，父节点的父节点的平衡因子 加或减 1
为 0 之前父节点的平衡因子为 正负1，停止更新平衡因子
为+-2 需要旋转节点，使平衡因子小于2
旋转方法
左旋
右边节点高，进行左旋
grandpa
parent
cur
parent是grandpa的右孩子，cur是parent的右孩子，这种情况要左旋
grandpa
parent
cur
parent是grandpa的右孩子，cur是parent的左孩子，先右旋，在左旋
先将 parent 以parent为旋转点 ，进行右·旋
cur
得到 grandpa 以cur为旋转点，进行左旋
cur
parent
右旋
左边节点高，进行右旋
代码部分
#pragma once
#include<iostream>
using namespace std;
template<class K,class V >
class AVLNode
{
public:
typedef AVLNode<K, V>Node;
Node* _left;
Node* _right;
Node* _parent;
int _bf;
pair<K, V>_kv;
public:
AVLNode(pair<K,V>kv)
:_left(nullptr)
,_right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
template<class K,class V>
class AVLTree
{
public:
typedef AVLNode<K, V> Node;
private:
Node* _root=nullptr;
public:
//构造函数
AVLTree()
:_root(nullptr)
{}
//析构函数
void _Destory(Node*root)
{
if (root == nullptr)
return;
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
~AVLTree()
{
_Destory(_root);
}
//拷贝构造函数
Node* _Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* left = _Copy(root->_left);
Node* right = _Copy(root->_right);
Node* newnode = new Node;
newnode->_left = left;
newnode->_right = right;
newnode->_bf = root->_bf;
newnode->_kv = root->_kv;
return newnode;
}
AVLTree(const Node& t)
{
_Copy(&t);
}
//赋值
AVLTree<K, V>operator=(AVLTree<K,V>t)
{
swap(_root, t._root);
return *this;
}
//左旋
void RotateL(Node* cur)
{
Node* parent = cur->_parent;
Node* curL = cur->_left;
cur->_parent = curL;
cur->_left = cur->_right;
curL->_right = cur;
if (parent->_left == cur)
parent->_left = curL;
else
parent->_right = curL;
curL->_bf = cur->_bf = 0;
}
//右旋
void RotateR(Node*cur)
{
Node* parent = cur->_parent;
Node* curR = cur->_right;
if (parent->_left == cur)
{
parent->_left = curR;
}
else
{
parent->_right = curR;
}
cur->_right = curR->_left;
cur->_parent = curR;
curR->_parent = parent;
curR->_left = cur;
cur->_bf = curR->_bf = 0;
}
//插入
bool Insert(pair<K, V>kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return 1;
}
Node* cur = _root;
//找到要插入的位置
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
Node* newnode = new Node(kv);
if (parent->_kv.first > kv.first)
{
parent->_left = newnode;
parent->_bf--;
}
else
{
parent->_right = newnode;
parent->_bf++;
}
//更新平衡因子
cur = parent;
if (parent != nullptr)
{
parent = parent->_parent;
}
else
return true;
while (parent)
{
if (cur->_bf == 0)
{
return true;
}
else if (abs(cur->_bf) == 1)
{
if (parent->_left == cur)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
cur = parent;
parent = parent->_parent;
}
else if (abs(cur->_bf) == 2)
{
if (cur->_bf == -2)
{
Node* curL = cur->_left;
if (curL->_bf == -1)
{
RotateR(cur);
}
else
{
RotateL(cur);
RotateR(cur);
}
}
else
{
Node* curR = cur->_right;
if (curR->_bf == 1)
{
RotateL(cur);
}
else
{
RotateR(cur);
RotateL(cur);
}
}
}
}
}
//中序遍历
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << " _bf:"<<root->_bf<<endl;
_Inorder(root->_right);
}
void Inorder()
{
_Inorder(_root);
}
};