苗火 Nicholas

[Data structures]Balance binary search tree (AVL)

2019-7-9 萧 写技术

#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");
}

标签: Data Structures data_structures