一、平衡二叉树（ AVL树 ）
1、定义：AVL树又称为高度平衡的二叉搜索树，是1962年有俄罗斯的数学家G.M.Adel'son-Vel'skii和E.M.Landis提出来的。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。
2、出现原因：搜索二叉树若出现严重退化，查找或使用时会造成资源浪费。
3、特性：
AVL树是一个三叉链；
左、右子树的 | 高度之差| 不超过 1；
左右子树都是AVL树；
每个节点的平衡因子 = 右子树高度 - 左子树高度；（平衡因子：-1,1,0）
4、效率：
一棵AVL树有N个节点，其高度可以保持在log2N，插入/删除/查找的时间复杂度：log2N，即 O(lgN)。
二、AVL相关
1、右单旋
2、左单旋
3、右左单旋及左右单旋
根据左单旋、右单旋及树的情况进行选择，旋转后需要更新平衡因子，以防失误。
4、节点平衡因子的更新：
（1）插入节点的右孩子，及平衡因子bf++;左孩子，bf--;
（2）若插入节点后，计算得bf==0,则平衡，不需更新平衡因子；bf==1或-1，则需向上查看是否需要平衡因子；bf==2或-2,则根据情况进行旋转，并更新平衡因子。
5、判断AVL树：
（1）计算左、右子树高度，平衡因子；
（2）若平衡因子 < 2,即其子树为AVL树；
三、源代码
1、节点
计算
安全
数据库
网络和加速
企业服务
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode<K,V> *_left;
AVLTreeNode<K,V> *_right;
AVLTreeNode<K,V> *_parent;
K _key;//权值
V _value;
int _bf;//平衡因子
AVLTreeNode(const K& key,const V& value)
:_key(key)
,_value(value)
,_left(NULL)
,_right(NULL)
,_parent(NULL)
{}
};2、AVL树及相关实现
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K,V> Node;
public:
AVLTree()
:_root(NULL)
{}
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
int Height()
{
return _Height(_root);
cout<<endl;
}
void RotateR(Node *parent)//右旋
{
Node *subL=parent->_left;
Node *subLR=subL->_right;
parent->_left=subLR;
if(subLR)
subLR->_parent=parent;
subL->_right=parent;
Node *ppNode=parent->_parent;
parent->_parent=subL;
if(ppNode == NULL)
{
_root=subL;
subL->_parent=NULL;
}
else
{
if(ppNode->_left == parent)
ppNode->_left=subL;
else
ppNode->_right=subL;
subL->_parent=ppNode;
}
}
void RotateL(Node *parent)//左旋转
{
Node *subR=parent->_right;
Node *subRL=subR->_left;
parent->_right=subR;
if(subRL)
subRL->_parent=parent;
subRL->_left=parent;
Node *ppNode=parent->_parent;
parent->_parent=subR;
if(ppNode == NULL)
{
_root=subR;
subR->_parent=NULL;
}
else
{
if(ppNode->_left == parent)
ppNode->_left=subR;
else
ppNode->_right=subR;
subR->_parent=ppNode;
}
}
void RotateRL(Node *parent)//右左旋转
{
Node *subR=parent->_right;
Node *subRL=subR->_left;
int bf=subR->_bf;
RotateR(parent->_right);
RotateL(parent);
//更正平衡因子
if(bf == 1)
{
parent->_bf=-1;
subR->_bf=0;
}
else if(bf == -1)
{
parent->_bf=0;
subR->_bf=1;
}
else // 0
{
subR->_bf=parent->_bf=0;
subRL->_bf=0;
}
}
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=-1;
subL->_bf=0;
}
else if(bf == -1)
{
parent->_bf=0;
subL->_bf=1;
}
else // 0
{
subL->_bf=parent->_bf=0;
subLR=0;
}
}
bool Insert(const K& key,const V& value)
{
if(_root == NULL)
{
_root=new Node(key,value);
return true;
}
Node *cur=_root;
Node *parent=NULL;
while(cur)
{
if(cur->_key > key)
{
parent=cur;
cur=cur->_left;
}
else if(cur->_key < key)
{
parent=cur;
cur=cur->_right;
}
else
return false;
}
cur=new Node(key,value);
if(parent->_key < key)
parent->_right=new Node(key,value);
else
parent->_left=new Node(key,value);
//更新平衡因子
while(parent)
{
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=cur->_parent;
}
else // -2或2
{
//旋转
if(parent->_bf == -2)
{
if(cur->_bf == -1)
RotateR(parent);//右旋转
else // -2
RotateLR(parent);//左右旋转
}
else // 2
{
if(cur->_bf == 1)
RotateL(parent);//左旋转
else
RotateRL(parent);//右左旋转
}
break;
}
}
return false;
}
protected:
void _InOrder(Node *root)
{
if(_root == NULL) return;
_InOrder(_root->_left);
cout<<_root->_key<<" ";
_InOrder(_root->_right);
}
int _Height(Node *root)
{
if(root == NULL) return 0;
int left=_Height(root->_left);
int right=_Height(root->_right);
return left > right ? left+1 : right+1;
}
protected:
Node *_root;
};3、总结：
AVL树是对搜索二叉树的进一步优化，根据平衡因子使搜索二叉树高度平衡。其的插入、删除、查找都和搜索二叉树类似，只是需要注意平衡因子的问题。
AVL树解决了搜索二叉树的退化问题，需要注意树的旋转问题及平衡因子的更新问题。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
