当前位置：网站首页>Balanced binary tree AVL
Balanced binary tree AVL
2022-06-26 00:45:00 【Be nice 123】
Balanced binary trees
Right hand operation
// To p Do right-handed processing for binary sort tree of root
// After processing p Point to the new tree root , That is, the root node of the left subtree before rotation processing
void R_Rotate(BiTree &p){
BiTree L;
L=p->lchild;//L Point to p The root node of the left subtree of
p->lchild=L->rchild;//L The right branch of the tree is linked to p The left subtree
L->rchild=p;
p=L;//p Point to the new root node
}
Left hand operation
/* To p Make a left-handed treatment for the binary sorting tree of the root After processing p Point to the new tree root , That is, the root node of the right subtree before rotation processing */
void L_Rotate(BiTree &p){
BiTree R;
R=p->rchild;//R Point to P Root node of right subtree of
p->rchild=R->lchild;//R The left subtree of is connected to p The right subtree
R->lchild=p;
p=R;//p Point to the new root node
}
Left balance rotation processing
/* Pointer to T The binary tree with the node as the root should be left balanced and rotated At the end of this algorithm , The pointer T Point to the new root node */
void LeftBalance(BiTree &T){
BiTree L,Lr;
L=T->lchild;//L Point to T The root node of the left subtree of
switch(L->bf){
// Check T The balance degree of the left subtree of , And make corresponding balance treatment
case LH:// The new node is inserted in T On the left child's left tree , We need to do a single right turn
T->bf=L->bf=EH;
R_Rotate(T);
break;
case RH:// The new node is inserted in T On the right subtree of the left child , Double spin
Lr=L->rchild;//Lr Point to T The left child's right tree root
switch(Lr->bf)// modify T And the left child's balance factor
{
case LH:
T->bf=RH;
L->bf=EH;
break;
case EH:
T->bf=L->bf=EH;
break;
case RH:
T->bf=EH;
L->bf=LH;
break;
}
Lr->bf=EH;
L_Rotate(T->lchild);// Yes T The left subtree of is left-handed balanced
R_Rotate(T);// Yes T Do a right-handed balance
}
}
Right balance rotation processing
void RightBalance(BiTree &T){
BiTree R,Rl;
R=T->rchild;
switch(R->bf){
case RH:// Corresponding to RR
T->bf=R->bf=EH;
L_Rotate(T);
break;
case LH:// Corresponding to RL
Rl=R->lchild;
switch(Rl->bf){
case LH:
T->bf=EH;
R->bf=RH;
break;
case EH:
T->bf=R->bf=EH;
break;
case RH:
T->bf=LH;
R->bf=EH;
break;
}
Rl->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
}
}
Balanced binary tree insertion
/* If in balanced binary sort tree T There is no and e Nodes with the same keyword , Insert a The data element is e New node of , And back to true; Otherwise return to false; If the two forks are caused by insertion The sort tree is out of balance , Balance rotation is required , Boolean variables taller reflect T Is it tall or not */
bool InsertAVL(BiTree &T, int e,bool &taller){
if(!T){
// Insert new node , The trees grow tall , Set up taller=true;
T=(BiTree)malloc(sizeof(BiTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=true;
}
else{
if(e == T->data){
// Trees already exist and e Nodes with the same keyword are not inserted
taller=false;
return false;
}
if(e < T->data){
// Should continue in T Search in the left subtree of
if(!InsertAVL(T->lchild, e, taller))// Not inserted
return false;
if(taller){
// Inserted into T And the left subtree is tall
switch(T->bf){
// Check T The balance of
case LH:// Originally, the left subtree was higher than the right subtree , It needs to be left balanced
LeftBalance(T);
taller=false;
break;
case EH:// Originally left and right subtrees were equal in height , Now because the left sub tree is higher and the tree is higher
T->bf=LH;
taller=true;
break;
case RH:// Originally, the right subtree was higher than the left subtree , Now left and right subtrees are the same height
T->bf=EH;
taller=false;
break;
}
}
}
else{
// Should continue in T Search in the right subtree of
if(!InsertAVL(T->rchild, e, taller))// Not inserted
return false;
if(taller){
// Check T The balance of
switch(T->bf){
case LH:// Originally, the left subtree was higher than the right subtree , Now wait for height
T->bf=EH;
taller=false;
break;
case EH:// Originally left and right subtrees were equal in height , Now because the right subtree is higher and the tree is higher
T->bf=RH;
taller=true;
break;
case RH:// Originally, the right subtree was higher than the left subtree , Right balance is required
RightBalance(T);
taller = false;
break;
}
}
}
}
return true;
}
Complete test code
// Balanced binary trees , Balanced tree AVL Trees ,G.M.Adelson-Velsky and E.M.Landis
#include<stdio.h>
#include<stdlib.h>
#define ElemType int
#define LH 1// Left high
#define EH 0// Equal height
#define RH -1// Right high
// Balanced binary tree node
typedef struct BiTNode{
// Node structure
ElemType data;// Node data
int bf;// The equilibrium factor of the node
struct BiTNode *lchild,*rchild;// Left and right child pointer
}BiTNode,*BiTree;
// To p Do right-handed processing for binary sort tree of root
// After processing p Point to the new tree root , That is, the root node of the left subtree before rotation processing
void R_Rotate(BiTree &p){
BiTree L;
L=p->lchild;//L Point to p The root node of the left subtree of
p->lchild=L->rchild;//L The right branch of the tree is linked to p The left subtree
L->rchild=p;
p=L;//p Point to the new root node
}
/* To p Make a left-handed treatment for the binary sorting tree of the root After processing p Point to the new tree root , That is, the root node of the right subtree before rotation processing */
void L_Rotate(BiTree &p){
BiTree R;
R=p->rchild;//R Point to P Root node of right subtree of
p->rchild=R->lchild;//R The left subtree of is connected to p The right subtree
R->lchild=p;
p=R;//p Point to the new root node
}
/* Pointer to T The binary tree with the node as the root should be left balanced and rotated At the end of this algorithm , The pointer T Point to the new root node */
void LeftBalance(BiTree &T){
BiTree L,Lr;
L=T->lchild;//L Point to T The root node of the left subtree of
switch(L->bf){
// Check T The balance degree of the left subtree of , And make corresponding balance treatment
case LH:// The new node is inserted in T On the left child's left tree , We need to do a single right turn
T->bf=L->bf=EH;
R_Rotate(T);
break;
case RH:// The new node is inserted in T On the right subtree of the left child , Double spin
Lr=L->rchild;//Lr Point to T The left child's right tree root
switch(Lr->bf)// modify T And the left child's balance factor
{
case LH:
T->bf=RH;
L->bf=EH;
break;
case EH:
T->bf=L->bf=EH;
break;
case RH:
T->bf=EH;
L->bf=LH;
break;
}
Lr->bf=EH;
L_Rotate(T->lchild);// Yes T The left subtree of is left-handed balanced
R_Rotate(T);// Yes T Do a right-handed balance
}
}
void RightBalance(BiTree &T){
BiTree R,Rl;
R=T->rchild;
switch(R->bf){
case RH:// Corresponding to RR
T->bf=R->bf=EH;
L_Rotate(T);
break;
case LH:// Corresponding to RL
Rl=R->lchild;
switch(Rl->bf){
case LH:
T->bf=EH;
R->bf=RH;
break;
case EH:
T->bf=R->bf=EH;
break;
case RH:
T->bf=LH;
R->bf=EH;
break;
}
Rl->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
}
}
/* If in balanced binary sort tree T There is no and e Nodes with the same keyword , Insert a The data element is e New node of , And back to true; Otherwise return to false; If the two forks are caused by insertion The sort tree is out of balance , Balance rotation is required , Boolean variables taller reflect T Is it tall or not */
bool InsertAVL(BiTree &T, int e,bool &taller){
if(!T){
// Insert new node , The trees grow tall , Set up taller=true;
T=(BiTree)malloc(sizeof(BiTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=true;
}
else{
if(e == T->data){
// Trees already exist and e Nodes with the same keyword are not inserted
taller=false;
return false;
}
if(e < T->data){
// Should continue in T Search in the left subtree of
if(!InsertAVL(T->lchild, e, taller))// Not inserted
return false;
if(taller){
// Inserted into T And the left subtree is tall
switch(T->bf){
// Check T The balance of
case LH:// Originally, the left subtree was higher than the right subtree , It needs to be left balanced
LeftBalance(T);
taller=false;
break;
case EH:// Originally left and right subtrees were equal in height , Now because the left sub tree is higher and the tree is higher
T->bf=LH;
taller=true;
break;
case RH:// Originally, the right subtree was higher than the left subtree , Now left and right subtrees are the same height
T->bf=EH;
taller=false;
break;
}
}
}
else{
// Should continue in T Search in the right subtree of
if(!InsertAVL(T->rchild, e, taller))// Not inserted
return false;
if(taller){
// Check T The balance of
switch(T->bf){
case LH:// Originally, the left subtree was higher than the right subtree , Now wait for height
T->bf=EH;
taller=false;
break;
case EH:// Originally left and right subtrees were equal in height , Now because the right subtree is higher and the tree is higher
T->bf=RH;
taller=true;
break;
case RH:// Originally, the right subtree was higher than the left subtree , Right balance is required
RightBalance(T);
taller = false;
break;
}
}
}
}
return true;
}
void visit(BiTree T){
printf("%d ",T->data);
}
// Middle order traversal of binary trees
void InOrder(BiTree T){
if(T){
InOrder(T->lchild);// Recursively traverses the left subtree
visit(T);
InOrder(T->rchild);
}
}
void PreOrder(BiTree T){
if(T){
visit(T);
PreOrder(T->lchild);// Recursively traverses the left subtree
PreOrder(T->rchild);
}
}
// After the sequence traversal , Destroy the binary sort tree
bool DestroyBiTree(BiTree T){
// Delete without &
if(T==NULL){
printf(" Blank nodes #\n");
return false;
}
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild);
printf(" The destruction %d\n",T->data);
free(T);
T=NULL;// To prevent the generation of wild pointers
return true;
}
int main(){
int i;
int a[10]={
3,2,1,4,5,6,7,10,9,8};
BiTree T=NULL;
bool taller;
for(i=0;i<10;i++){
InsertAVL(T,a[i],taller);
}
printf(" In the sequence traversal :\n");
InOrder(T);
printf("\n\n The balanced binary tree can be drawn according to the output of preorder and inorder traversal \n And then verify the correctness of the results \n");
printf("\n\n The former sequence traversal :\n");
PreOrder(T);
printf("\n\n Remember to destroy it after use （ Traverse and destroy in sequence ）!\n");
DestroyBiTree(T);
return 0;
}
test result
边栏推荐
- "Method not allowed", 405 problem analysis and solution
- idea设置mapper映射文件的模板
- Analysis and comparison of common test methods for PCBA in SMT chip processing industry
- 实现异步的方法
- DPVS fullnat mode deployment
- 【OEM专场活动】清“芯”夏日，有奖征文
- Analyze the five root causes of product development failure
- What are AOI, X-ray and ICT in SMT industry? What does it do?
- SQL按某字段去重 保留按某个字段排序最大值
- [TSP problem] solving traveling salesman problem based on Hopfield neural network with matlab code
猜你喜欢
Redisson 3.17.4 release
SSL unresponsive in postman test
使用VS2022編譯Telegram桌面端(tdesktop)
![[image detection] vascular tracking and diameter estimation based on Gaussian process and Radon transform with matlab code](/img/1d/511dceb9decd73976d577af991afc9.png)
[image detection] vascular tracking and diameter estimation based on Gaussian process and Radon transform with matlab code
每日刷题记录 (四)
Performance leads the cloud native database market! Intel and Tencent jointly build cloud technology ecology
leetcode.14 --- 最长公共前缀
《SQL优化核心思想》
Mining pit record of modified field information in Dameng database
Ad20 (Altium designer) PCB highlight network
随机推荐
每日刷题记录 (四)
“Method Not Allowed“,405问题分析及解决
Things / phenomena / things / things / situations / appearances
Should group by be used whenever aggregate functions are used in SQL?
Why is it best to use equals for integer comparisons
学习识别对话式问答中的后续问题
Apache基金会正式宣布Apache InLong成为顶级项目
渗透工具-Burpsuite
Some basic uses of mongodb
After being trapped by the sequelae of the new crown for 15 months, Stanford Xueba was forced to miss the graduation ceremony. Now he still needs to stay in bed for 16 hours every day: I should have e
Drag the mouse to rotate the display around an object
性能领跑云原生数据库市场！英特尔携腾讯共建云上技术生态
[image detection] vascular tracking and diameter estimation based on Gaussian process and Radon transform with matlab code
Anti shake and throttling
Dynamic verification code
Ssl/tls, symmetric and asymmetric encryption, and tlsv1.3
Setting up a cluster environment under Linux (2) -- installing MySQL under Linux
Understanding of prototypes and prototype chains
Comprehensive introduction to Simulink solver
QT excellent open source project 9: qtox