Árvore AVL

Nomeada pelos criadores Adelson-Velskii e Landis, é uma árvore de busca binária onde a complexidade de busca é O(log n) para n elementos.

É uma árvore balanceada por altura onde a diferença da altura das duas subárvores tenha modulo até 1.

Será considerado a seguinte estrutura para o nó:

struct nodeAVL {
	nodeData data;
	int fb, altura;
	struct nodeAVL *pai, *esq, *dir;
};

Balanceamento

O fator de balanceamento e um nó é a altura da subárvore da esquerda - altura da subárvore da direita (pode ser o contrário)

O nó é considerado desbalanceado quando o fator de balanceamento tem módulo maior que 1.

Manutenção do balanceamento

Sempre que é realizada um alteração em um nó, o nó afetado, ou os ascendentes podem sofrer alteração do fator de balanceamento. Quando o fb ultrapassa o limite, é necessário realizar uma ou duas operação(ões) de rotação para balancear o nó.

Rotação

Quando um nó está desbalanceando em uma direção e o seu filho dessa direção estiver desbalanceando na mesma, é realizada uma rotação simples onde o nó é rotacionado na direção contrária a qual está desbalanceando. Se o filho estiver desbalanceando na direção contraria,é preciso realizar uma rotação no filho na direção oposta antes de realizar no pai.

Exemplo de rotação para a esquerda: A árvore a seguir tem o nó A com fator de balanceamento -2, e o seu filho da direita está desbalanceando para o mesmo lado. (os nós marcados como possível não são considerados, estão apenas para ilustrar o que acontece com o filho de C).

graph
	A --- B[possível filho de A]
	A --- C
	C --- E[possível filho de C]
	C --- D

Após realizar o rotação terá a seguinte forma:

graph
	C --- A
	A --- B[possível filho de A]
	A --- E[possível filho de C]
	C --- D

Exemplo em C:

• Para realizar a rotação para a direção oposta, é preciso trocar onde está esquerda por direita e vice versa.
• As funções removeNodeFromPai e updatePaiNode, servem para retirar e colocar um ponteiro para para o nó em seu pai. A função atualizaBalanceamento atualiza a altura e o fator de balanceamento do nó.

void LL(nodeAVL* node) {
	nodeAVL* filhoDireita = node->dir;
	
	removeNodeFromPai(node);
	//pai de node vira pai de dir
	filhoDireita->pai = node->pai;
	updatePaiNode(filhoDireita);
	
	//troca filho da esquerda de filhoDireita com filho da direita de node
	node->dir = filhoDireita->esq;
	if (node->dir)
		node->dir->pai = node;

	//filhoDireita vira pai de node
	filhoDireita->esq = node;
	filhoDireita->esq->pai = filhoDireita;

	atualizaBalanceamento(filhoDireita);
	atualizaBalanceamento(node);
}

Inserção

Para realizar a inserção, é simples, basta inserir o nó na árvore como em qualquer arvore binária. Ápos a inserção é preciso atualizar o fator de balanceamento do nó inserido e de seus ascendentes.

Exemplo em c:

• O código a seguir cuida do caso de inserir o nó raiz através do ponteiro para o ponteiro da raiz, e ignora elementos repetidos.
• A função mantemBalanceamento atualiza o balanceamento dos nós até chegar na raiz, e se necessário realiza o balanceamento.
• O balanceamento pode alterar a raiz, nesse caso o pai do nó que era a raiz é a nova raiz.

nodeAVL* insertNode(nodeAVL** rootPtr, nodeData data) {
	nodeAVL* root = *rootPtr;
	if (root != NULL) {
		nodeAVL* pai = searchPos(root, data);
		bool alreadyExists = pai->data == data;
		if (alreadyExists)
			return pai;

		nodeAVL* newNode = aloca();
		newNode->data = data;

		newNode->pai = pai;
		updatePaiNode(newNode);

		mantemBalanceamento(newNode);

		//atualiza raiz
		if (root->pai != NULL)
			*rootPtr = root = root->pai;
		return newNode;
	} else {
		*rootPtr = aloca();
		(*rootPtr)->data = data;
		return *rootPtr;
	}
}

Remoção

A remoção é um pouco mais complicada, é preciso lidar com alguns casos. Se o nó removido possuir nenhum ou um filho, esse entra em seu lugar. Se o nó possuir dois filhos, é preciso encontrar o maior elemento da sua subárvore da esquerda, seu antecessor, e colocá-lo no lugar do nó removido.

Exemplo em c:

A primeira parte do código encontra o elemento a ser removido, se esse existir, se não ignora. Também verifica se existem filhos no nó, e remove o nó da árvore.

void removeNode(nodeAVL** rootPtr, nodeData data) {
	nodeAVL* const root = *rootPtr;
	if (root == NULL) return;
	nodeAVL *toRemove = search(root, data),
			*substituto = NULL;
	if (toRemove == NULL)
		return;
	bool hasEsq = toRemove->esq != NULL,
		 hasDir = toRemove->dir != NULL,
		 isLeaf = !hasEsq && !hasDir;
	removeNodeFromPai(toRemove);

A proxima parte lida com o caso de remover a folha e caso remova a raiz:

	if (isLeaf) {
		if (toRemove == root)
			*rootPtr = NULL;
		else if (toRemove->pai)
			mantemBalanceamento(toRemove->pai);
	} 

As próximas duas partes lidam com os casos de remover quando há um ou dois filho(s).

Quando há dois, é utilizado o antecessor. O antecessor é retirado da árvore, e se possuir um filho, este vira filho de seu avô. Após obter o antecessor, o nó é removido da árvore e seus filhos são inseridos em seu antecessor.

	else if (hasEsq && hasDir) {
		substituto = antecessor(toRemove);
		nodeAVL *paiDoAntecessor = substituto->pai,
				*filhoAntecessor = substituto->esq;
		removeNodeFromPai(substituto);
		if (filhoAntecessor != NULL) {
			filhoAntecessor->pai = paiDoAntecessor;
			updatePaiNode(filhoAntecessor);
		}
		substituto->pai = toRemove->pai;
		updatePaiNode(substituto);
		substituto->dir = toRemove->dir;
		substituto->esq = toRemove->esq;
		substituto->dir->pai = substituto;
		if (substituto->esq)  //caso o antecessor seja filho do nó
			substituto->esq->pai = substituto;
		mantemBalanceamento(paiDoAntecessor);
	} 

No caso de haver apenas um filho, esse vira filho do pai do nó removido.

	else {
		if (hasEsq)
			substituto = toRemove->esq;
		else
			substituto = toRemove->dir;
		removeNodeFromPai(substituto);
		substituto->pai = toRemove->pai;
		updatePaiNode(substituto);
		mantemBalanceamento(substituto);
	}

Por fim a função verifica se uma duas partes acima alteraram a raiz e desaloca o nó

	bool substitutoIsNewRoot = substituto != NULL && substituto->pai == NULL;
	if (substitutoIsNewRoot)
		*rootPtr = substituto;
	desaloca(toRemove);
}

implementação

Segue a implementação completa:

avl.c e avl.h