tysm/árvoreAVL_EDA_2017.1.md

## árvoreAVL_EDA_2017.1.md

      
    Raw
  

              árvoreAVL_EDA_2017.1.md
            
          
    Árvore AVL


Tipo de árvore balanceada pela altura.
O nome AVL vem das iniciais de seus criadores: Adelson Velsky e Landis.

Balanceamento


Está balanceada quando, para cada nó da árvore, a diferença entre as alturas das subárvores (direita e esquerda) não é maior que 1.

Fator de Balanceamento


É dado por: altura da subárvore esquerda - altura da subárvore direita.
Corolário: nós balanceados possuem fator de balanceamento = 1, 0 ou -1.
Corolário: um nó com fator de balanceamento = 2 ou -2 requer um balanceamento.
Corolário: Fator de balanceamento = 1 indica que a subárvore da esquerda é maior que a da direita.
Corolário: Fator de balanceamento = -1 indica que a subárvore da direita é maior que a da esquerda.
Corolário: Fator de balanceamento = 0 indica que as duas subárvores possuem a mesma altura.
Caso ocorra desbalanceamento, podemos balancear um nó a partir de algoritmos rotação.

Inserção na AVL


Sempre se dá numa folha e pode causar desbalanceamento.
Procedimentos:

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;
Remoção na AVL


Semelhante à remoção na árvore binária e pode causar desbalanceamento.

Código

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