Método de inserção de uma árvore binária;
Ajuste dos fatores de balanceamento;
Verificação do equilíbrio da árvore;
Execução de rotações em nós desbalanceados;
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct tree{
struct tree* left;
struct tree* right;
int value;
int height;
}tree;
static void insert(tree** node, int value);
static int height(tree* node);
static int max(int a, int b);
static int getBalance(tree* node);
static void rotacaoSimplesDireita(tree** node);
static void rotacaoSimplesEsquerda(tree** node);
static void dell(tree** node, int value);
static tree** find_max(tree** node);
static void preOrdem(tree* node);
static void emOrdem(tree* node);
static void posOrdem(tree* node);
int main(){
int item, i=0;
tree* root = NULL;
srand(time(NULL));
printf("Os números inseridos na árvore são:\n");
for(; i<20; i++){
item = rand()%100;
printf("%d ", item);
insert(&root, item);
}
printf("\n\n- Pré-ordem:\n");
preOrdem(root);
printf("\n- Em ordem:\n");
emOrdem(root);
printf("\n- Pós-ordem:\n");
posOrdem(root);
printf("\n\nQual node quer deletar? ");
scanf("%d", &item);
dell(&root, item);
printf("\n- Pré-ordem:\n");
preOrdem(root);
printf("\n- Em ordem:\n");
emOrdem(root);
printf("\n- Pós-ordem:\n");
posOrdem(root);
return 0;
}
/**
* retorna 1 se inseriu, 0 se já havia inserido.
*/
void insert(tree** node, int value)
{
int balance;
if(*node == NULL){
*node = malloc(sizeof(tree));
(*node)->left = (*node)->right = NULL;
(*node)->value = value;
}
else if(value < (*node)->value)
insert(&(*node)->left, value);
else if(value > (*node)->value)
insert(&(*node)->right, value);
else
return;
//Atualizando a altura do node
(*node)->height = max(height((*node)->left), height((*node)->right)) + 1;
/* Fase de balanceamento */
balance = getBalance(*node);
if(balance > 1){
/* Left Left */
if(getBalance((*node)->left) >= 0)
rotacaoSimplesDireita(node);
/* Left Right */
else{
rotacaoSimplesEsquerda(&(*node)->left);
rotacaoSimplesDireita(node);
}
}
else if(balance < -1){
/* Right Right */
if(getBalance((*node)->right) <= 0)
rotacaoSimplesEsquerda(node);
/* Right Left */
else{
rotacaoSimplesDireita(&(*node)->right);
rotacaoSimplesEsquerda(node);
}
}
}
int height(tree* node)
{
if(node == NULL)
return 0;
return node->height;
}
int max(int a, int b)
{
return a < b? b : a;
}
int getBalance(tree* node)
{
if(node == NULL)
return 0;
return height(node->left) - height(node->right);
}
void rotacaoSimplesDireita(tree** node)
{
tree* y = *node;
*node = y->left;
y->left = (*node)->right;
(*node)->right = y;
y->height = max(height(y->left), height(y->right)) + 1;
(*node)->height = max(height((*node)->left), height((*node)->right)) + 1;
}
void rotacaoSimplesEsquerda(tree** node)
{
tree* y = (*node)->right;
(*node)->right = y->left;
y->left = *node;
(*node)->height = max(height((*node)->left), height((*node)->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
*node = y;
}
/**
* retorna 1 se deletou, 0 se não havia o que deletar.
*/
void dell(tree** node, int value)
{
int balance;
tree *to_dell, *max_left, **max_left_ptr;
if(*node == NULL)
return;
else if(value < (*node)->value)
dell(&(*node)->left, value);
else if(value > (*node)->value)
dell(&(*node)->right, value);
else{
if((*node)->left == NULL && (*node)->right == NULL){
free(*node);
*node = NULL;
}
else if((*node)->right == NULL){
//Então (*node)->left != NULL
to_dell = *node;
*node = (*node)->left;
free(to_dell);
}
else if((*node)->left == NULL){
//Então (*node)->right != NULL
to_dell = *node;
*node = (*node)->right;
free(to_dell);
}
else{
//Então (*node)->right != NULL && (*node)->left != NULL
to_dell = *node;
max_left_ptr = find_max(&to_dell->left);
max_left = *max_left_ptr;
//Modificando o maior nó da subárvore esquerda
*max_left_ptr = max_left->left;
//Atualizando o valor do nó atual
max_left->left = to_dell->left;
max_left->right = to_dell->right;
*node = max_left;
free(to_dell);
}
}
if(*node == NULL)
return;
//Atualizando a altura do node
(*node)->height = max(height((*node)->left), height((*node)->right)) + 1;
/* Fase de balanceamento */
balance = getBalance(*node);
if(balance > 1){
/* Left Left */
if(getBalance((*node)->left) >= 0)
rotacaoSimplesDireita(node);
/* Left Right */
else{
rotacaoSimplesEsquerda(&(*node)->left);
rotacaoSimplesDireita(node);
}
}
else if(balance < -1){
/* Right Right */
if(getBalance((*node)->right) <= 0)
rotacaoSimplesEsquerda(node);
/* Right Left */
else{
rotacaoSimplesDireita(&(*node)->right);
rotacaoSimplesEsquerda(node);
}
}
}
/**
* retorna o maior nó de uma subárvore
*/
tree** find_max(tree** node)
{
if((*node)->right != NULL)
return find_max(&(*node)->right);
return node;
}
/**
* Centro, Esquerda, Direita
*/
void preOrdem(tree* node)
{
if(node != NULL){
printf("%d\n", node->value);
preOrdem(node->left);
preOrdem(node->right);
}
}
/**
* Esquerda, Centro, Direita
*/
void emOrdem(tree* node)
{
if(node != NULL){
emOrdem(node->left);
printf("%d\n", node->value);
emOrdem(node->right);
}
}
/**
* Esquerda, Direita, Centro
*/
void posOrdem(tree* node)
{
if(node != NULL){
posOrdem(node->left);
posOrdem(node->right);
printf("%d\n", node->value);
}
}