O que é uma árvore AVL?

Uma árvore AVL é um tipo de árvore binária de busca. Nomeada em homenagem aos seus criadores, Adelson-Velsky e Landis, as árvores AVL possuem a propriedade de autobalanceamento dinâmico, além de todas as outras propriedades mostradas pelas árvores binárias de busca.

Uma árvore binária de busca, ou BST (do inglês, binary search tree), é uma estrutura de dados compostas de nós. Ela tem as seguintes garantias:

1. Cada árvore possui um nó raiz (no topo)
2. O nó raiz tem zero, um ou dois filhos
3. Cada nó filho tem zero, um ou dois nós filhos.
4. Cada nó tem até dois filhos
5. Para cada nó, seus descendentes da esquerda são menores que o nó atual, que é menor que o descendentes da direita

As árvores AVL têm uma garantia adicional:

1. A diferença entre as profundidade das camadas do lado direito e esquerdo não pode ser maior que um. Essa diferença é chamada de fator de balanço.
   
   Para manter essa garantia, a implementação de uma AVL incluirá um algoritmo para balanceamento da árvore quando a adição de um elemento prejudicar essa garantia.  

As árvores AVL têm uma complexidade de tempo de busca, inserção e exclusão, no pior dos casos, de O(log n), onde n é o número de nós na árvore. A complexidade de espaço de pior caso é O(n).

Processo de inserção na AVL

A inserção em uma árvore AVL é similar à inserção em uma árvore binária de busca.  Depois de inserir um elemento, no entanto, você precisa ajustar as propriedades da AVL utilizando rotações para esquerda ou para a direita:

• Se houver um desbalanceamento na subárvore da direita do filho da esquerda do nó, faça uma rotação dupla à direita.
• Se houver um desbalanceamento na subárvore da esquerda do filho da esquerda do nó, faça uma rotação simples à direita.
• Se houver um desbalanceamento na subárvore da direita do filho da direita do nó, faça uma rotação simples à esquerda.
• Se houver um desbalanceamento  na subárvore da esquerda do filho da direita do nó, faça uma rotação dupla à esquerda.  

Rotações da árvore AVL

Nas árvores AVL, após cada operação, como inserção e exclusão, o fator de balanceamento de cada nó precisa ser verificado. Se cada nó satisfizer a condição do fator de balanceamento, a operação pode ser concluída. Caso contrário, a árvore precisa ser rebalanceada utilizando as operações de rotação.

Existem quatro rotações e elas são classificadas em dois tipos:

Rotação simples à esquerda (rotação SE)

Na rotação simples à esquerda, cada nó se move uma posição para a direita da posição atual.

Rotação simples à direita (rotação SD)

Na rotação simples à direita, cada nó se move uma posição para a direita da posição atual.

Rotação dupla à direita (rotação DD)

As rotações duplas à direita são uma combinação de uma única rotação para a esquerda seguida de uma rotação para a direita.

Primeiro, cada nó se move uma posição para a esquerda. Depois, se move uma posição para a direita da posição atual.

Rotação dupla à esquerda (rotação DE)

As rotações duplas à esquerda são uma combinação de uma única rotação para a direita seguida de uma rotação para a esquerda.

Primeiro, cada nó se move uma posição para a direita. Depois, se move uma posição para a esquerda da posição atual.

Aplicação das árvores AVL

As árvores AVL são benéficas em casos de bancos de dados, onde inserções e exclusões não são frequentes, mas onde você confere as entradas com frequência.

O que é uma árvore binária de busca?

Uma árvore é uma estrutura de dados composta de nós, com as seguintes características:

1. Cada árvore tem um nó raiz em seu ponto superior (também conhecido como Nó Pai) contendo algum valor (com qualquer tipo de dados).
2. O nó raiz tem zero ou mais "nós filhos".
3. Cada nó filho tem zero ou mais "nós filhos" e assim por diante. Isso cria uma subárvore interna à árvore. Cada nó tem sua própria subárvore feita dos filhos e dos filhos dos filhos e assim por diante. Isso quer dizer que cada nó pode ser uma árvore por si só.

Uma árvore binária de busca (ou BST, do inglês binary search tree) tem, além disso, as duas características abaixo:

1. Cada nó pode ter, no máximo, dois filhos.
2. Para cada nó, os valores de seus descendentes da esquerda são inferiores ao valor do nó atual, que, por sua vez, é inferior aos nós descendentes da direita (se existirem).

As BST tem como base a ideia do algoritmo de busca binária, que permite uma procura, inserção e remoção rápidas dos nós. A maneira como estão configurados representa, em média, que cada comparação permite que as operações evitem passar por cerca de metade da árvore. Assim, cada procura, inserção ou remoção  leva um tempo proporcional ao logaritmo do número de itens armazenados na árvore, O(log n). Entretanto, em algumas situações, podemos ter o pior dos casos, em que a árvore não está balanceada e a complexidade de tempo passa a ser O(n)  para essas três funções. É por isso que árvores autobalanceadas (AVL, rubro-negra etc.) são muito mais eficazes que a BST básica.

Exemplo de cenário com o pior caso:  isso pode acontecer quando você segue adicionando nós que são sempre maiores do que o nó anterior (seu pai). A mesma situação pode acontecer quando você sempre adiciona nós com valores inferiores aos de seus nós pai.

Operações básicas em uma BST

• Criar: cria uma árvore vazia.
• Inserir: insere um nó na árvore.
• Pesquisar: pesquisa por um nós na árvore.
• Excluir: exclui um nó da árvore.
• Travessia em ordem: faz a travessia da árvore na ordem.
• Travessia pré-ordem: faz a travessia da árvore pré-ordem.
• Travessia pós-ordem:  faz a travessia da árvore pós-ordem.

Criar

Inicialmente, uma árvore vazia e sem nós é criada. A variável/identificador que deve apontar para o nó raiz é inicializado com o valor NULL.

Pesquisar

Sempre começamos a pesquisa em uma árvore pelo nó raiz e descemos a partir dele. Você compara os dados em cada nó com o valor que você está buscando. Se o nó comparado não corresponder, seguimos para o nó filho da direita ou da esquerda, dependendo do resultado da comparação seguinte: se o nó que buscamos for inferior àquele com o qual estamos comparando, seguimos para o filho da esquerda. Do contrário (se for maior) vamos para o filho da direita. Por quê? Porque a BST é estruturada (por definição) de modo que o filho da direita sempre seja maior que o pai e que o filho da esquerda sempre seja menor.

Busca em largura (BFS, do inglês breadth-first search)

A busca em largura é um algoritmo usado para fazer a travessia de uma BST. Ela começa no nó raiz e viaja de modo lateral (de um lado para outro), buscando pelo nó desejado. Este tipo de busca pode ser descrito como O(n), dado que cada nó é visitado uma vez e que o tamanho da árvore está correlacionado diretamente com o  tamanho da busca.

Busca em profundidade (DFS, do inglês depth-first search)

Com a abordagem da busca em profundidade, começamos com o nó raiz e viajamos para baixo em uma única ramificação. Se o nó desejado for encontrado naquela ramificação, ótimo. Do contrário, continuamos subindo e pesquisando por nós não visitados. Esse tipo de busca também tem uma notação big O de O(n).

Inserir

É muito semelhante à função de pesquisar. Novamente, começamos do nó raiz da árvore e descemos de modo recursivo, procurando pelo local certo para inserir o novo nó, do mesmo modo que explicamos na função de pesquisar. Se um nó com o mesmo valor já existir na árvore, é possível escolher inserir a duplicata ou não. Algumas árvores permitem duplicatas, outras não. Isso depende da implementação.

Excluir

Há 3 casos que podem acontecer quando você tenta excluir um nós. Ele pode,

1. não ter uma subárvore (não ter filhos): esse é o caso mais fácil. Você pode simplesmente excluir o nó, sem precisar realizar outras ações.
2. Uma subárvore (um filho): você precisa se certificar de que, após o nó ser excluído, seu filho é, então, conectado ao pai do nó excluído.
3. Duas subárvores (dois filhos): você precisa encontrar e substituir o nó que você quer excluir pelo seu sucessor em ordem (o nó mais à esquerda na subárvore à direita).

A complexidade de tempo para a criação de uma árvore é O(1). A complexidade de tempo para a pesquisa, inserção ou exclusão de um nó depende da altura h da árvore, portanto o pior caso é O(h) no caso de árvores que vão apenas em uma direção (esquerda ou direita).

Tipos especiais de árvore binária

• Heap
• Árvore rubro-negra
• Árvore B (B-Tree)
• Árvore play
• Árvore n-ária
• Trie (árvore de prefixos)

Tempo de execução

Estrutura de dados: BST (binary search tree)

• Desempenho no pior caso:  O(n)
• Desempenho no melhor caso:  O(1)
• Desempenho médio:  O(log n)
• Complexidade de espaço no pior caso:  O(1)

Onde n  é o número de nós da BST. O pior caso é O(n), já que a BST pode não estar balanceada.

Implementação da BST

Aqui temos uma definição para um nó da BST com alguns dados, referenciando seus nós filhos da esquerda e da direita.

struct node {
   int data;
   struct node *leftChild;
   struct node *rightChild;
};

Operação de pesquisa

Sempre que um elemento precisa ser pesquisado, comece a pesquisa a partir do nó raiz. Depois, se os dados forem menores do que o valor-chave, pesquise o elemento na subárvore da esquerda. Do contrário, pesquise o elemento na subárvore da direita. Siga o mesmo algoritmo para cada nó.

struct node* search(int data){
   struct node *current = root;
   printf("Elementos visitados: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //vá para a subárvore da esquerda
         if(current->data > data){
            current = current->leftChild;
         }//senão, vá para a subárvore da direita
         else {                
            current = current->rightChild;
         }
			
         //não encontrado
         if(current == NULL){
            return NULL;
         }
      }			
   }
   return current;
}

Operação de inserção

Sempre que um elemento precisar ser inserido, primeiro encontre seu local adequado. Comece pesquisando a partir do nó raiz. Então, se os dados forem menores que o valor-chave, pesquise o local vazio na subárvore da esquerda e insira o dado. Do contrário, pesquise o local vazio na subárvore da direita e insira o dado.

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //se a árvore estiver vazia
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //vá para a esquerda da árvore
         if(data < parent->data) {
            current = current->leftChild;                
            //insira à esquerda
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }//vá para a direita da árvore
         else {
            current = current->rightChild;
            
            //insira à direita
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}        

Operação de exclusão

void deleteNode(struct node* root, int data){

    if (root == NULL) root=tempnode; 

    if (data < root->key) 
        root->left = deleteNode(root->left, key); 
  

    else if (key > root->key) 
        root->right = deleteNode(root->right, key); 

    else
    { 
        if (root->left == NULL) 
        { 
            struct node *temp = root->right; 
            free(root); 
            return temp; 
        } 
        else if (root->right == NULL) 
        { 
            struct node *temp = root->left; 
            free(root); 
            return temp; 
        } 
  
        struct node* temp = minValueNode(root->right); 
 
        root->key = temp->key; 

        root->right = deleteNode(root->right, temp->key); 
    } 
    return root; 

}

As árvores binárias de busca (BSTs) também nos dão acesso rápido aos predecessores e sucessores.

Predecessor de um nó

Predecessores podem ser descritos como os nós que vêm logo antes do nó em que você se encontra no momento. Para encontrar o predecessor do nó atual, olhe para o maior nó folha/mais à direita na subárvore esquerda.

Sucessor de um nó

Sucessores podem ser descritos como os nós que vêm logo após o nó atual. Para encontrar o sucessor do nó atual, olhe para o menor nó folha/mais à esquerda na subárvore da direita.

Vamos examinar alguns procedimentos de operação em árvores

Como as árvores são definidas recursivamente, é muito comum escrevermos rotinas que operam nas árvores que sejam recursivas.

Por exemplo, se quisermos calcular a altura de uma árvore, ou seja, a altura de um nó raiz, podemos fazer isso recursivamente, percorrendo a árvore. Podemos dizer assim:

• Se tivermos uma árvore vazia, sua altura é 0.
• Do contrário, estamos a 1 mais a maior altura entre a da árvore filha à esquerda e a da árvore filha à direita.
• Se olharmos para uma folha, por exemplo, essa altura seria 1, pois a altura do filho à esquerda é 0, e a altura do filho da direita também é 0. Assim, como o máximo dentre os dois é 0, então 1 mais 0 = 1.

Algoritmo da altura - Height(tree)

if tree = nil:
    return 0
return 1 + Max(Height(tree.left),Height(tree.right))

Este é o código em C++

int maxDepth(struct node* node)
{
    if (node==NULL)
        return 0;
   else
   {
       int rDepth = maxDepth(node->right);
       int lDepth = maxDepth(node->left);

       if (lDepth > rDepth)
       {
           return(lDepth+1);
       }
       else
       {
            return(rDepth+1);
       }
   }
}  

Também podemos calcular o tamanho de uma árvore, que é o seu número de nós.

• Mais uma vez, se tivermos uma árvore vazia, temos 0 nós.
• Do contrário, temos o número de nós no filho à esquerda mais 1 mais o número de nós no filho à direita. Assim 1 mais o tamanho da árvore da esquerda mais o tamanho da árvore da direita.

Algoritmo do tamanho - Size(tree)

if tree = nil
    return 0
return 1 + Size(tree.left) + Size(tree.right)

Este é o código em C++

int treeSize(struct node* node)
{
    if (node==NULL)
        return 0;
    else
        return 1+(treeSize(node->left) + treeSize(node->right));
}

Travessias

Há 3 tipos de travessias que são feitas tipicamente em uma árvore binária de busca. Todas elas têm um modo bastante comum de percorrer os nós de uma árvore.

Em ordem (in-order traversal)

Essa travessia primeiro percorre a subárvore da esquerda do nó raiz, acessa o nó atual, seguido da subárvore da direita do nó atual. O código abaixo representa o caso de base, também, que diz que uma árvore vazia também é uma árvore binária de busca.

void inOrder(struct node* root) {
        // Caso de base
        if (root == null) {
                return;
        }
        // Percorre primeiro a subárvore da esquerda.
        inOrder(root.left);
        // Imprime o valor do nó atual.
        printf("%d ", root.data);
        // Percorre em seguida a subárvore da direita.
        inOrder(root.right);
}

Pré-ordem (pre-order traversal)

Essa travessia primeiro acessa o valor do nó atual, faz a travessia pela subárvore da esquerda e, depois, pela subárvore da direita, respectivamente.

void preOrder(struct node* root) {
        if (root == null) {
                return;
        }
        // Imprime o valor do nó atual.
        printf("%d ", root.data);
        // Percorre a subárvore da esquerda.
        preOrder(root.left);
        // Percorre a subárvore da direita.
        preOrder(root.right);
}

Pós-ordem (post-order traversal)

Essa travessia coloca o valor do nó raiz no fim, percorrendo primeiro a subárvore da esquerda e depois a da direita. A ordem relativa das subárvores da esquerda e da direita permanece a mesma. Somente a posição do nó raiz muda em relação às travessias anteriores.

void postOrder(struct node* root) {
        if (root == null) {
                return;
        }
        // Percorre primeiro a subárvore da esquerda.
        postOrder(root.left);
        // Percorre em seguida a subárvore da direita.
        postOrder(root.right);
        // Imprime o valor do nó atual.
        printf("%d ", root.data);
}

Vídeos do freeCodeCamp relevantes no canal do YouTube

Binary Search Tree: Traversal and Height (Árvore binária de busca: travessia e altura)

A seguir, temos tipos comuns de árvores binárias:

Árvore totalmente binária/árvore binária estrita: uma árvore é totalmente binária ou estrita se todo nó tiver exatamente 0 ou 2 nós filhos.

          18
         /   \
       /       \  
     15         30  
    /  \       /  \
  40    50   100   40

Na árvore totalmente binária, o número de nós folha é igual ao número de nós internos mais um.

Árvore binária completa: uma árvore binária é completa se todos os níveis estiverem completamente preenchidos, exceto, possivelmente, o último nível e se o último nível tiver todas as chaves o mais à esquerda possível.

           18
         /    \
       /        \  
     15         30  
    /  \       /  \
  40    50   100   40
 /  \   /
8    7 9 

Árvore binária perfeita: uma árvore binária é perfeita se todos os nós internos tiverem dois nós filhos e se todas as folhas estiverem no mesmo nível.

          18
         /  \
       /      \  
     15        30  
    /  \      /  \
  40    50  100   40

Aumentando uma BST

Às vezes, precisamos armazenar algumas informações adicionais com as estruturas de dados tradicionais para tornar nossas tarefas mais fáceis. Por exemplo, considere um cenário onde você deve encontrar o i-ésimo menor número de um conjunto. É possível usar a força bruta aqui, mas queremos reduzir a complexidade do problema para O(lg n) aumentando uma árvore rubro-negra ou qualquer árvore autobalanceada (onde n é o número de elementos do conjunto). Também podemos calcular a classificação de qualquer elemento no tempo O(lg n). Vamos considerar um caso onde aumentamos uma árvore rubro-negra para que armazene as informações necessárias. Além dos atributos normais, podemos armazenar um certo número de nós internos na subárvore com a raiz x (tamanho da subárvore com raiz em x incluindo o próprio nó). Considere x como sendo qualquer nó arbitrário de uma árvore.

x.size = x.left.size + x.right.size + 1

Quando aumentamos a árvore, levamos em consideração que devemos ser capazes de manter as informações adicionadas, bem como fazer outras operações, como inserção, exclusão e atualização em um tempo O(lg n).

Assim, sabemos que o valor de x.left.size (subárvore do lado esquerdo de x) nos dará o número de nós que vêm após x na travessia em ordem da árvore. Portanto, x.left.size + 1 é a classificação de x dentro da subárvore com raiz em x.