文章目录
函数结点定义树的高度计算树高和平衡因子LL旋转RR旋转LR旋转RL旋转AVL树的插入与旋转调整
测试测试代码测试输入测试输出动图演示相关文章
函数
结点定义
typedef struct TreeNode
{
int val
;
TreeNode
* left
;
TreeNode
* right
;
int balance
;
int height
;
TreeNode(int x
):val(x
), left(nullptr), right(nullptr), balance(0), height(0){}
}*AVLTree
;
树的高度
int getHeight(AVLTree t
)
{
return ( t
==nullptr ? -1:t
->height
);
}
计算树高和平衡因子
void AVL_Cal(AVLTree root
)
{
int hl
= getHeight(root
->left
);
int hr
= getHeight(root
->right
);
root
->height
= max(hl
, hr
) + 1;
root
->balance
= hl
- hr
;
}
LL旋转
void LL_rotation(AVLTree
& A
)
{
AVLTree t
= A
;
AVLTree B
= A
->left
;
AVLTree BR
= B
->right
;
B
->right
= t
;
t
->left
= BR
;
A
= B
;
AVL_Cal(A
->right
);
AVL_Cal(A
);
}
RR旋转
void RR_rotation(AVLTree
& A
)
{
AVLTree t
= A
;
AVLTree B
= A
->right
;
AVLTree BL
= B
->left
;
B
->left
= t
;
t
->right
= BL
;
A
= B
;
AVL_Cal(A
->left
);
AVL_Cal(A
);
}
LR旋转
void LR_rotation(AVLTree
& A
)
{
RR_rotation(A
->left
);
LL_rotation(A
);
}
RL旋转
void RL_rotation(AVLTree
& A
)
{
LL_rotation(A
->right
);
RR_rotation(A
);
}
AVL树的插入与旋转调整
bool AVL_Insert(AVLTree
& root
, int& x
)
{
if( !root
)
{
root
= new TreeNode(x
);
return true;
}
else if( x
< root
->val
)
{
AVL_Insert(root
->left
, x
);
AVL_Cal(root
);
if( root
->balance
> 1 )
{
if( x
< root
->left
->val
)
LL_rotation(root
);
else
LR_rotation(root
);
}
}
else if( x
> root
->val
)
{
AVL_Insert(root
->right
, x
);
AVL_Cal(root
);
if( root
->balance
< -1 )
{
if( x
> root
->right
->val
)
RR_rotation(root
);
else
RL_rotation(root
);
}
}
return true;
}
测试
测试代码
#include<bits/stdc++.h>
using namespace std
;
typedef struct TreeNode
{
int val
;
TreeNode
* left
;
TreeNode
* right
;
int balance
;
int height
;
TreeNode(int x
):val(x
), left(nullptr), right(nullptr), balance(0), height(0){}
}*AVLTree
;
int getHeight(AVLTree t
)
{
return ( t
==nullptr ? -1:t
->height
);
}
void AVL_Cal(AVLTree root
)
{
int hl
= getHeight(root
->left
);
int hr
= getHeight(root
->right
);
root
->height
= max(hl
, hr
) + 1;
root
->balance
= hl
- hr
;
}
void LL_rotation(AVLTree
& A
)
{
AVLTree t
= A
;
AVLTree B
= A
->left
;
AVLTree BR
= B
->right
;
B
->right
= t
;
t
->left
= BR
;
A
= B
;
AVL_Cal(A
->right
);
AVL_Cal(A
);
}
void RR_rotation(AVLTree
& A
)
{
AVLTree t
= A
;
AVLTree B
= A
->right
;
AVLTree BL
= B
->left
;
B
->left
= t
;
t
->right
= BL
;
A
= B
;
AVL_Cal(A
->left
);
AVL_Cal(A
);
}
void LR_rotation(AVLTree
& A
)
{
RR_rotation(A
->left
);
LL_rotation(A
);
}
void RL_rotation(AVLTree
& A
)
{
LL_rotation(A
->right
);
RR_rotation(A
);
}
bool AVL_Insert(AVLTree
& root
, int& x
)
{
if( !root
)
{
root
= new TreeNode(x
);
return true;
}
else if( x
< root
->val
)
{
AVL_Insert(root
->left
, x
);
AVL_Cal(root
);
if( root
->balance
> 1 )
{
if( x
< root
->left
->val
)
LL_rotation(root
);
else
LR_rotation(root
);
}
}
else if( x
> root
->val
)
{
AVL_Insert(root
->right
, x
);
AVL_Cal(root
);
if( root
->balance
< -1 )
{
if( x
> root
->right
->val
)
RR_rotation(root
);
else
RL_rotation(root
);
}
}
return true;
}
void visit(TreeNode
* p
)
{
cout
<< p
->val
<< " ";
}
void preOrder(AVLTree root
)
{
if( root
)
{
visit(root
);
preOrder(root
->left
);
preOrder(root
->right
);
}
}
void inOrder(AVLTree root
)
{
if( root
)
{
inOrder(root
->left
);
visit(root
);
inOrder(root
->right
);
}
}
void postOrder(AVLTree root
)
{
if( root
)
{
postOrder(root
->left
);
postOrder(root
->right
);
visit(root
);
}
}
int main( )
{
AVLTree root
= nullptr;
int n
, t
;
int value
[] = {};
cin
>>n
;
for(int i
=0;i
<n
;i
++)
{
cin
>>t
;
AVL_Insert(root
, t
);
}
cout
<< "根结点：" << root
->val
;
cout
<< "\n" << "先序遍历：";
preOrder(root
);
cout
<< "\n" << "中序遍历：";
inOrder(root
);
cout
<< "\n" << "后序遍历：";
postOrder(root
);
return 0;
}
测试输入
第一行输入插入结点的个数，第二行按顺序输入插入结点的值。
9
8 4 10 2 1 3 11 6 5
测试输出
输出根结点和遍历的结果。
根结点：4
先序遍历：4 2 1 3 10 6 5 8 11
中序遍历：1 2 3 4 5 6 8 10 11
后序遍历：1 3 2 5 8 6 11 10 4
动图演示
相关文章
AVL树（1）——简介 AVL树（2）——插入与旋转调整 AVL树（3）——C++实现
