#include <stdio.h>
#include <stdlib.h>
typedef struct _BinaryTree{
int key;
int bf;
struct _BinaryTree *left;
struct _BinaryTree *right;
}BinaryTree;
void R_Rotate(BinaryTree **T)
{
BinaryTree *lc;
lc = (*T)->left;
(*T)->left = lc->right;
lc->right = (*T);
(*T) = lc;
}
void L_Rotate(BinaryTree **T)
{
BinaryTree *lc;
lc = (*T)->right;
(*T)->right = lc->left;
lc->left = (*T);
(*T) = lc;
}
void LeftBalance(BinaryTree **T)
{
BinaryTree *lc = (*T)->left;
BinaryTree *rd = NULL;
switch(lc->bf){
case 1:
(*T)->bf = lc->bf = 0;
R_Rotate(T);
break;
case -1:
rd = lc->right;
switch(rd->bf){
case 1:
(*T)->bf = -1;
lc->bf = 0;
break;
case 0:
(*T)->bf = lc->bf = 0;
break;
case -1:
(*T)->bf = 0;
lc->bf = 1;
break;
}
rd->bf = 0;
L_Rotate(&(*T)->left);
R_Rotate(T);
break;
}
}
void RightBalance(BinaryTree **T)
{
BinaryTree *rc = (*T)->right;
BinaryTree *ld = NULL;
switch(rc->bf){
case 1:
ld = rc->left;
switch(ld->bf){
case 1:
(*T)->bf = 0;
rc->bf = -1;
break;
case 0:
(*T)->bf = rc->bf = 0;
break;
case -1:
(*T)->bf = 1;
rc->bf = 0;
break;
}
ld->bf = 0;
R_Rotate(&(*T)->right);
L_Rotate(T);
break;
case -1:
(*T)->bf = rc->bf = 0;
L_Rotate(T);
break;
}
}
int InsertAVL(BinaryTree **T, int key, int *taller)
{
if(*T == NULL){
(*T) = (BinaryTree *)malloc(sizeof(BinaryTree));
(*T)->key = key;
(*T)->left = (*T)->right = NULL;
(*T)->bf = 0;
*taller = 1;
return 1;
}else if((*T)->key == key){
*taller = 0;
return 0;
}else if( key < (*T)->key){
if( !InsertAVL( &(*T)->left, key, taller) ){
return 0;
}
if(*taller){
switch((*T)->bf){
case 1:
LeftBalance(T);
*taller = 0;
break;
case 0:
(*T)->bf = 1;
*taller = 1;
break;
case -1:
(*T)->bf = 0;
*taller = 0;
break;
}
}
}else{
if( !InsertAVL( &(*T)->right, key, taller) ){
return 0;
}
if(*taller){
switch((*T)->bf){
case 1:
(*T)->bf = 0;
*taller = 0;
break;
case 0:
(*T)->bf = -1;
*taller = 1;
break;
case -1:
RightBalance(T);
*taller = 0;
break;
}
}
}
}
void printTree(BinaryTree *T){
if(T == NULL){
return;
}
printf(" %d", T->key );
printf("(");
if(T->left != NULL){
printTree(T->left);
}
printf(",");
if(T->right != NULL){
printTree(T->right);
}
printf(")");
}
void main()
{
int seq[] = { 0, 13, 24, 37, 90, 53 };
int n = sizeof(seq)/sizeof(int);
int i;
BinaryTree *T = NULL;
int taller;
printf("Original data:\n");
for (i=0; i<n; i++) {
printf("%d\t", seq[i]);
}
printf("\n");
printf("Insert balance binary search tree:\n");
for(i=1;i<n;i++){
InsertAVL(&T, seq[i], &taller);
}
printf("\n");
printf("Print the tree:\n");
printTree(T);
printf("\n");
}