当前位置：网站首页>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
边栏推荐
- Summary of common terms and knowledge in SMT chip processing industry
- 渗透工具-Burpsuite
- SQL按某字段去重 保留按某个字段排序最大值
- Learn to identify follow-up questions in dialogue Q & A
- CaMKIIa和GCaMP6f是一樣的嘛？
- 毕业季 | 在不断探索中拟合最好的自己
- Use Coe_ load_ sql_ profile. SQL fixed execution plan
- Ffmpeg version switching
- Redisson 3.17.4 release
- mysql cluster
猜你喜欢
每日刷题记录 (四)
Compile the telegraph desktop side (tdesktop) using vs2022
【超能云终端创领先机】如何在48小时内交付一座方舱医院？
Wireshark's analysis of IMAP packet capturing
No executorfactory found to execute the application
"Seamless" deployment of paddlenlp model based on openvinotm development kit
![[advanced ROS] Lecture 1 Introduction to common APIs](/img/25/85e8c55605f5cc999a8e85f0a05f93.jpg)
[advanced ROS] Lecture 1 Introduction to common APIs
The development context of Ba Kong Yuan universe industry
Stream data
Atlas200dk brush machine
随机推荐
Display unassigned virtual address after easyconnect connection
How product managers control the progress of product development
Redux workflow + complete code of small examples
Comprehensive introduction to Simulink solver
使用VS2022編譯Telegram桌面端(tdesktop)
使用VS2022编译Telegram桌面端(tdesktop)
Compile the telegraph desktop side (tdesktop) using vs2022
Simulink求解器综合介绍
Farsync simple test
EBS r12.2.0 to r12.2.6
[TSP problem] solving traveling salesman problem based on Hopfield neural network with matlab code
Cloud rendering and Intel jointly create the "core" era of cloud rendering
SQL to retain the maximum value sorted by a field
Megacli common command collation
Use js to obtain the last quarter based on the current quarter
Things / phenomena / things / things / situations / appearances
Types of feeder and how to work
Atlas200dk刷机
Learn to identify follow-up questions in dialogue Q & A
Phoenix index