# Data structure_ Balanced binary tree (C language)

2022-06-24 09:56:28

# Balanced binary trees

Balanced binary trees （ English names are also called AVL Trees ）, Is in Sort binary trees A binary tree optimized on the basis of the structure of , The nature of the tree is The height difference between the left and right subtrees of any node is no more than 1

## 1. Graphic analysis

In balanced binary tree , It is mainly divided into four situations that need to adjust the balance state
（1）A The equilibrium factor of the node = 【A The height of the left subtree of the node 】 - 【A The height of the right subtree of the node 】 = 2, There's an imbalance , And the newly inserted node is the left child （A）, Rotate the subtree to the right , And update the node height after rotation . （2）A The equilibrium factor of the node = 【A The height of the left subtree of the node 】 - 【A The height of the right subtree of the node 】 = -2, There's an imbalance , And the newly inserted node is the right child （C）, Rotate the subtree to the left , And update the node height after rotation . （3）A The equilibrium factor of the node = 【A The height of the left subtree of the node 】 - 【A The height of the right subtree of the node 】 = 2, There's an imbalance , And the newly inserted node is the right child （B）, Rotate left first p node , Again right node node , Complete the balancing operation . （4）A The equilibrium factor of the node = 【A The height of the left subtree of the node 】 - 【A The height of the right subtree of the node 】 = -2, There's an imbalance , And the newly inserted node is the left child （B）, Rotate right first p node , Then left rotation node node , Complete the balancing operation . ## 2. Source code

``````#include<stdio.h>
#include<stdlib.h>
#define max(a,b) ((a>b)?(a):(b))

typedef char DataType;
typedef struct AVLNode
{

DataType data;          //  Data fields
struct AVLNode *lchild; //  Pointer to the domain , Point to the left child node
struct AVLNode *rchild; //  Pointer to the domain , Point to the right child node
int height;             //  Indicates the height of the current node as the root node subtree
}AVLNode, *AVLTree;

//  initialization
void InitAVLTree(AVLTree *T)
{

(*T) = NULL;   //  The initialization root node is empty
printf(" Binary tree initialized !\n");
}

//  Get subtree height
int getHeight(AVLNode *node)
{

return node == NULL ? 0: node->height;
}

//  Right rotation
AVLNode* Rotate_R(AVLNode *node)
{

AVLNode *p = node->lchild;
node->lchild = p->rchild;
p->rchild = node;

//  Update height （ Order of attention ）
node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
p->height = max(getHeight(p->lchild), getHeight(p->rchild)) + 1;

return p;
}

//  Left rotation
AVLNode* Rotate_L(AVLNode *node)
{

AVLNode *p = node->rchild;
node->rchild = p->lchild;
p->lchild = node;

//  Update height （ Order of attention ）
node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
p->height = max(getHeight(p->lchild), getHeight(p->rchild)) + 1;

return p;
}

//  First left rotation , Again right
AVLNode* Rotate_LR(AVLNode *node)
{

AVLNode *p = node->lchild;
node->lchild = Rotate_L(p);
return Rotate_R(node);
}

//  First right rotation , Then left rotation
AVLNode* Rotate_RL(AVLNode *node)
{

AVLNode *p = node->rchild;
node->rchild = Rotate_R(p);
return Rotate_L(node);
}

//  Calculate the equilibrium factor
int getBalance(AVLNode *node)
{

if (node == NULL)
{

return 0;
}
return getHeight(node->lchild) - getHeight(node->rchild);
}

//  Insert operation of sorting binary tree
void AVLTreeInsert(AVLTree *T, DataType x)
{

if ((*T) == NULL)
{

//  If the current binary tree node is empty ,  That is, the insertion position , Then a new node space is allocated
(*T) = (AVLNode *)malloc(sizeof(AVLNode));
(*T)->data = x;
(*T)->height = 1;
(*T)->lchild = (*T)->rchild = NULL;
}
else if (x < (*T)->data)
{

//  Recursive left subtree to find the insertion position
AVLTreeInsert(&(*T)->lchild, x);
}
else if(x > (*T)->data)
{

//  Recursive right subtree to find the insertion position
AVLTreeInsert(&(*T)->rchild, x);
}
else
{

printf(" Insert the failure ! The same data exists !\n");
return;
}

//  Update the height of the parent node during recursive insertion
(*T)->height = max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;

//  Get the balance factor
int balance = getBalance((*T));

printf(" node :%c,  Height  = %d,  Balance factor  = %d\t",(*T)->data, (*T)->height, balance);

//  Select according to the balance factor   Rotating way
if (balance > 1 && x < (*T)->lchild->data)
{

printf(" Right hand ");
(*T) = Rotate_R((*T));
}
else if (balance < -1 && x > (*T)->rchild->data)
{

printf(" left-handed ");
(*T) = Rotate_L((*T));
}
else if (balance > 1 && x > (*T)->lchild->data)
{

printf(" Left right rotation ");
(*T) = Rotate_LR((*T));
}
else if (balance < -1 && x < (*T)->rchild->data)
{

printf(" Right left ");
(*T) = Rotate_RL((*T));
}
printf("\n");
}

//  The first sequence traversal
void PreOrderTraverse(AVLTree T)
{

if (T)
{

printf("%c ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

int main()
{

AVLTree T;
InitAVLTree(&T);
DataType x;
while (1)
{

printf(" Input insert data :");
fflush(stdin);
scanf("%c", &x);
if (x == '#')
{

break;
}
AVLTreeInsert(&T, x);
printf(" The first sequence traversal :");
PreOrderTraverse(T);
printf("\n");
}
system("pause");
return 0;
}
``````

## 3. test result

Right rotation Left rotation First left rotation , Again right First right rotation , Rotate left 