Árvore AVL: guia completo com implementação em Python

Desbalanceamento em árvores binárias de busca

Árvores binárias de busca (BSTs) são um tipo de árvore binária estrutura de dados que organiza dados seguindo uma ordenação específica. Cada nó contém um valor e possui ligações para até dois outros nós: os filhos esquerdo e direito. Em uma BST, a regra é que o valor do filho esquerdo deve ser menor que o valor do nó pai, e o valor do filho direito deve ser maior.

BSTs podem ser muito eficientes para encontrar valores específicos porque permitem eliminar grandes porções da árvore durante a busca. Por exemplo, se estamos procurando o valor um na árvore acima, podemos desconsiderar todos os nós à direita de seis. Isso porque a propriedade de ordem garante que todos aqueles valores são maiores que seis.

Idealmente, cada nó deveria dividir os dados pela metade, de modo que metade dos valores seja eliminada a cada passo pela árvore. Isso leva a consultas muito rápidas. Porém, dependendo da ordem de inserção, é possível acabar com uma árvore desbalanceada que não divide os dados de forma eficaz. Por exemplo, inserir valores do menor para o maior resulta em uma árvore linear, que não performa melhor do que uma lista.

O que é uma árvore AVL

Uma árvore AVL é uma árvore binária de busca com a seguinte propriedade adicional:

Para cada nó, a altura das subárvores esquerda e direita difere em, no máximo, um.

Detalhando essa definição, a subárvore esquerda de um nó inclui todos os nós à sua esquerda, enquanto a subárvore direita compreende todos os nós à sua direita. A altura de uma árvore é definida como o comprimento do caminho mais longo do nó raiz (o nó superior) até qualquer uma de suas folhas descendentes (nós sem filhos).

O fator de balanceamento de um nó é calculado como a diferença entre a altura da sua subárvore esquerda e a da subárvore direita:

balance(N) = height(subárvore esquerda de N) - height(subárvore direita de N)

Por exemplo, balance(6) = 1 - 3 = -2.

No diagrama, o nó 6 apresenta um fator de balanceamento igual a -2, indicando que a árvore não atende aos critérios de uma árvore AVL. Para que uma árvore seja classificada como AVL, o fator de balanceamento de cada nó deve ser -1, 0 ou 1.

Por que usar árvores AVL

A eficiência das consultas em uma árvore binária de busca depende da altura da árvore. No pior caso, a quantidade de nós a serem examinados é igual à altura da árvore. Um problema central nas BSTs é que a altura pode ser igual ao número de nós, ou seja, uma consulta pode exigir inspecionar todos os nós.

Seja M(h) o número mínimo de nós necessários para adicionar a uma árvore binária de busca para atingir altura h. Para BSTs simples, observamos que M(h) = h, ou seja, podemos atingir altura h usando apenas h nós. Isso implica que a altura de uma BST pode crescer linearmente com o número de nós, levando a um tempo de consulta proporcional ao tamanho do conjunto de dados.

Prova de que árvores AVL têm altura logarítmica

Vamos considerar o número mínimo de nós, M(h), necessários para criar uma árvore AVL com altura h. Como é uma árvore AVL, é importante notar que o fator de balanceamento de todo nó só pode ser -1, 0 ou 1.

No entanto, dado que assumimos que a árvore tem o menor número de nós possível para atingir a altura h, a raiz não pode ter balanço 0. Se tivesse, poderíamos remover um nó do lado esquerdo ou direito para obter um balanço -1 ou 1, e ainda assim teríamos uma AVL válida.

Vamos supor que o balanço da raiz seja 1 (o raciocínio é o mesmo se o balanço fosse -1). Isso implica que a árvore está estruturada assim:

Por sua vez, as subárvores esquerda e direita também devem ser AVL, cada uma com o número mínimo de nós requerido para suas alturas (caso contrário, seria possível remover nós adicionais). O total de nós na árvore é igual a 1 (a raiz) mais o número de nós da subárvore esquerda mais o número de nós da subárvore direita.

M(h) = 1 + (nós em L) + (nós em R) = 1 + M(h - 1) + M(h - 2)

À medida que a altura cresce, precisamos adicionar mais nós para alcançá-la. Portanto:

M(h - 1) > M(h - 2)

Combinando as duas, podemos dizer que:

M(h) = 1 + M(h - 1) + M(h - 2) > 1 + 2 × M(h - 2) > 2 × M(h - 2)

Podemos aplicar isso h/2 vezes até chegarmos a M(1) = 1 ou M(2) = 2:

M(h) > 2 × M(h - 2) > 2 × 2 × M(h - 4) > 2 × 2 × 2 × M(h - 6) > … > 2(h/2)

Para clareza, a imagem a seguir mostra os exemplos específicos quando h = 7 e h = 6:

Concluímos que o número mínimo de nós em uma AVL de altura h é pelo menos 2(h/2):

M(h) > 2(h/2)

Aplicando logaritmo de base dois em ambos os lados, obtemos:

log2(M(h)) > log2(2(h/2)) = h/2

Consequentemente, multiplicando ambos os lados por dois, deduzimos que a altura é, no máximo, duas vezes o logaritmo em base 2 do número de nós:

2 × log2(M(h)) > h

Mostramos que:

A altura de uma árvore AVL com N nós é, no máximo, 2 × log2(N).

Isso indica que consultas em uma AVL exigem examinar apenas uma pequena fração do conjunto de dados. Por exemplo, com um bilhão de entradas, o logaritmo é aproximadamente 30, o que significa que, mesmo com um bilhão de pontos de dados, é necessário inspecionar apenas cerca de 60 pontos para encontrar um item específico. É uma melhora enorme comparada a BSTs que, no pior caso, exigiriam inspecionar todos os um bilhão de pontos.

Para se aprofundar em complexidade de tempo algorítmica e na diferença entre complexidade linear e logarítmica, confira este post sobre notação Big-O e complexidade de tempo.

Mantendo o balanceamento com árvores AVL

Árvores AVL garantem consultas rápidas ao impor que o balanço de cada nó seja -1, 0 ou 1. Para manter esse balanço, precisamos rebalancear a árvore após inserir um novo valor.

A inserção em BSTs funciona seguindo o caminho da raiz para baixo. Vamos à esquerda quando o valor a inserir é menor e à direita caso contrário.

Uma inserção aumenta a altura em, no máximo, um. Então, se a propriedade de balanceamento não for respeitada após inserir, significa que havia um nó com balanço -1 que virou -2, ou um nó com balanço 1 que virou 2. O primeiro caso é o que acontece no exemplo acima.

Rotações simples

Para restaurar o balanceamento, usamos rotações de árvore. Uma rotação à esquerda no nó A reestrutura a árvore girando A para a esquerda, como abaixo:

No diagrama:

• BL representa a subárvore esquerda de B
• BR é a subárvore direita
• AL é a subárvore esquerda de A

Perceba que, após a rotação, a ordem dos nós continua válida:

1. O nó A é menor que B porque B era seu filho direito.
2. Os nós em BL são maiores que A porque estavam à direita de A.
3. Os nós em AL são menores que B porque são menores que A.

Uma rotação à direita funciona de forma simétrica, girando A para a direita.

Vamos ver um exemplo concreto corrigindo o desbalanceamento da árvore após inserir 19 usando uma rotação à esquerda no nó 6.

Após a inserção, vamos corrigir o desbalanceamento rotacionando um nó com balanço -2 ou 2. Neste caso, o fator de balanceamento do nó 6 era -2, indicando que a árvore estava pendendo para a direita, então aplicamos uma rotação à esquerda (na direção oposta ao desbalanceamento). Se, em vez disso, o balanço fosse 2, usaríamos uma rotação à direita.

Rotações duplas

No exemplo anterior, a árvore estava totalmente pendendo para a direita, então uma rotação simples à esquerda foi suficiente para restaurar o balanceamento. Porém, em alguns casos, temos um desbalanceamento em zigue-zague, quando a árvore pende para um lado, mas a subárvore pende para o lado oposto. Para ver isso, vamos voltar à árvore original antes de inserir 19 e inserir 7 no lugar:

Neste caso, a árvore ainda pende para a direita, mas a subárvore enraizada em 10 pende para a esquerda. Aqui, primeiro precisamos rotacionar o nó 10 para a direita:

Note que o nó B não tem filho direito. Ainda o exibimos em azul no diagrama para facilitar a visualização. 

Depois da rotação à direita, caímos no caso anterior, em que uma rotação à esquerda em 6 restaura o balanceamento:

Como implementar uma árvore AVL em Python

Vamos começar pela implementação do nó.

Implementação do nó

Cada nó da árvore tem cinco atributos:

• O valor que armazena (self.value)
• O nó pai (self.parent)
• O filho esquerdo (self.left)
• O filho direito (self.right)
• A altura da subárvore enraizada nesse nó (self.height)

class Node:
  def __init__(self, value, parent = None):
    self.value = value
    self.parent = parent
    self.left = None
    self.right = None
    self.height = 1

Usamos o valor None para representar nós ausentes. A height padrão é 1 porque uma árvore com um único nó tem altura 1. 

Para facilitar a implementação da árvore, adicionamos alguns métodos à classe Node.

# Inside the Node class
  def left_height(self):
    # Get the heigth of the left subtree
    return 0 if self.left is None else self.left.height
  
  def right_height(self):
    # Get the height of the right subtree
    return 0 if self.right is None else self.right.height
  def balance_factor(self):
    # Get the balance factor
    return self.left_height() - self.right_height()
  def update_heigth(self):
    # Update the heigth of this node
    self.height = 1 + max(self.left_height(),self.right_height())
    
  def set_left(self, node):
    # Set the left child
    self.left = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  
  def set_right(self, node):
    # Set the right child
    self.right = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  def is_left_child(self):
    # Check whether this node is a left child
    return self.parent is not None and self.parent.left == self
  
  def is_right_child(self):
    # Check whether this node is a right child
    return self.parent is not None and self.parent.right == self

Note que usamos os métodos .set_left() e .set_right() para definir os filhos esquerdo e direito, respectivamente. A razão para usar esses métodos, em vez de alterar diretamente os atributos self.left e self.right, é que sempre que um filho é alterado, é necessário atualizar o pai do novo filho e também a altura do nó.

Implementação da árvore AVL

A árvore AVL mantém um parâmetro: a raiz da árvore, que é o nó mais alto.

class AVLTree:
  def __init__(self):
    self.root = None

Para manter o balanceamento, precisamos implementar rotações à esquerda e à direita. Vamos recapitular como a rotação à esquerda é ilustrada no diagrama:

# Inside the AVLTree class
  
  def rotate_left(self, a):
    b = a.right
    # 1. The new right child of A becomes the left child of B
    a.set_right(b.left)
    # 2. The new left child of B becomes A
    b.set_left(a)
    return b # 3. Return B to replace A with it

Rotações à direita são implementadas de forma simétrica:

# Inside the AVLTree class
  
  def rotate_right(self, a):
    b = a.left
    a.set_left(b.right)
    b.set_right(a)
    return b

Com as rotações, podemos rebalancear a árvore. Um nó precisa de rebalanço quando seu fator de balanceamento chega a 2 (a árvore pende para a esquerda) ou -2 (pende para a direita). No total, há quatro cenários a considerar:

Implementamos esses quatro casos no método .rebalance().

# Inside the AVLTree class
  
  def rebalance(self, node):
    if node is None:
      # Empty tree, no rebalancing needed
      return None
    balance = node.balance_factor()
    if abs(balance) <= 1:
      # The node is already balanced, no rebalancing needed
      return node
    if balance == 2: 
      # Cases 1 and 2, the tree is leaning to the left
      if node.left.balance_factor() == -1: 
        # Case 2, we first do a left rotation
        node.set_left(self.rotate_left(node.left))
      return self.rotate_right(node)
    # Balance must be -2
    # Cases 3 and 4, the tree is leaning to the left
    if node.right.balance_factor() == 1:
      # Case 4, we first do a right rotation
      node.set_right(self.rotate_right(node.right)) 
    return self.rotate_left(node)

Observe que, em cada caso, o método retorna a raiz da subárvore que acabou de ser balanceada. Essa nova raiz será usada depois para atualizar os filhos durante o processo de rebalanço.

Adicionar um nó em uma AVL é semelhante ao processo em uma BST comum, com o adicional de restaurar o balanceamento após a inserção. Para adicionar um nó em uma BST, começamos na raiz e descemos a árvore. A cada passo, comparamos o valor a ser adicionado com o valor do nó atual. Se for menor, vamos à esquerda; caso contrário, à direita. Enquanto descemos, guardamos o nó pai para inserir o novo nó como seu filho.

Quando chegamos a um nó vazio, existem dois casos:

1. O pai é None, o que significa que a árvore está vazia, então o novo nó vira a nova raiz.
2. Encontramos o pai, então precisamos definir o novo nó como filho esquerdo ou direito, conforme os valores.

# Inside the AVLTree class
  def add(self, value):
    self.size += 1
    parent = None
    current = self.root
    while current is not None:
      parent = current
      if value < current.value:
        # Value to insert is smaller than node value, go left
        current = current.left
      else:
        # Value to insert is larger than node value, go right
        current = current.right
    # We found the parent, create the new node
    new_node = Node(value, parent)
    # Case 1: The parent is None so the new node is the root
    if parent is None:
      self.root = new_node
    else:
      # Case 2: Set the new node as a child of the parent
      if value < parent.value:
        parent.left = new_node
      else:
        parent.right = new_node
    # After a new node is added, we need to restore balance
    self.restore_balance(new_node)

A única diferença entre o método .add() de uma BST e o de uma AVL está no passo final. Nele, subimos a árvore e reequilibramos os nós, do recém-adicionado até a raiz, usando o método .rebalance().

# Inside the AVLTree class
  def restore_balance(self, node):
    current = node
    # Go up the tree and rebalance left and right children
    while current is not None:
      current.set_left(self.rebalance(current.left))
      current.set_right(self.rebalance(current.right))
      current.update_heigth()
      current = current.parent
    self.root = self.rebalance(self.root)
    self.root.parent = None

Note que o método .rebalance() não faz nada quando o nó já está balanceado — ele simplesmente retorna o mesmo nó. Por isso, ao subir pela árvore, podemos chamá-lo nos dois lados, embora apenas um deles possa estar desbalanceado. A outra chamada não altera a árvore.

Repare que implementamos .rebalance() para retornar a (potencialmente) nova raiz da subárvore. O motivo é permitir atualizar os filhos esquerdo e direito dos nós atuais conforme subimos restaurando o balanceamento.

O diagrama a seguir mostra as etapas de .restore_balance() subindo a árvore.

No exemplo, primeiro adicionamos o nó 8. Em seguida, o processo de restaurar o balanceamento começa nesse nó e sobe a árvore, verificando e reequilibrando os filhos esquerdo e direito de cada nó encontrado. Isso continua até chegar ao nó 10. Até esse ponto, nenhuma chamada de .rebalance() tem efeito, pois os nós permanecem balanceados.

Porém, ao chegar ao nó 10, observa-se que seu filho esquerdo, o nó 7, tem fator de balanceamento -2, indicando necessidade de rebalanço. Consequentemente, .rebalance(7) é chamado, substituindo o filho esquerdo de 10 pela nova raiz da subárvore esquerda, o nó 8, restaurando o balanceamento da árvore.

Operações adicionais em árvores AVL

Além de adicionar e remover elementos mantendo o balanceamento, árvores AVL suportam diversas operações essenciais.

Mínimo e máximo

Devido à natureza ordenada da BST, o valor mínimo está no nó mais à esquerda da árvore, enquanto o máximo está no nó mais à direita.

Implementamos duas funções auxiliares que identificam os nós mais à esquerda e mais à direita a partir de um nó dado. Essas funções ajudam na implementação da remoção de nós.

# Inside the AVLTree class
  
  def leftmost(self, starting_node):
    # Find the leftmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.left
    return previous
  def minimum(self):
    # Return the minimum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.leftmost(self.root).value

# Inside the AVLTree class
 
  def rightmost(self, starting_node):
    # Find the rightmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.right
    return previous
  
  def maximum(self):
    # Fidn the maximum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.rightmost(self.root).value

Contains

Para saber se a árvore contém um valor específico, usamos a propriedade de ordenação para guiar a busca. A partir da raiz, seguimos à esquerda se o valor buscado for menor que o nó atual e à direita se for maior. Se chegarmos ao fim sem encontrar, o valor não está na árvore.

Para facilitar, implementamos o método auxiliar .locate_node(). Ele é útil não só na busca, mas também para operações como remoção. Também usamos o método .__contains__(), que permite usar o operador in para verificar de forma simples se um valor está na árvore.

# Inside the AVLTree class

  def locate_node(self, value):

    # Returns the node containing a given value or None if no

    # such node exists

    current = self.root

    while current is not None:

      if value == current.value:

        return current

      if value < current.value:

        current = current.left

      else:

        current = current.right

    return None

  def __contains__(self, value):

    node = self.locate_node(value)

    return node is not None

Remoção

Remover um nó em uma AVL pode ser especialmente desafiador quando o nó está no meio da árvore. Se o nó é uma folha, ou seja, não tem filhos, podemos removê-lo facilmente definindo o ponteiro de filho esquerdo ou direito do pai como None, conforme o nó seja filho esquerdo ou direito.

Um caso especial ocorre quando o nó a ser removido é a raiz da árvore. Nesse cenário, podemos removê-lo definindo a raiz como None.

# Inside the AVLTree class

  def delete_leaf(self, node):

    if node.parent is None:

      self.root = None

    elif node.is_left_child():

      node.parent.left = None

      node.parent = None

    else:

      node.parent.right = None

      node.parent = None

Para remover um valor de uma AVL, primeiro localizamos o nó que contém esse valor com .locate_node(). Encontrado o nó, podemos removê-lo com .delete_leaf() se ele for folha. Se não for, a remoção direta quebraria a estrutura. Para contornar, buscamos um nó substituto. Se o nó a ser removido tem filho esquerdo, escolhemos o nó mais à direita da sua subárvore esquerda. Isso mantém a ordenação da árvore.

O diagrama abaixo exemplifica a remoção do nó 10. Como ele tem filho esquerdo, substituímos pelo nó mais à direita da subárvore esquerda. Após a substituição, é crucial rebalancear a árvore, começando pelo pai do nó recém-substituído.

Neste exemplo, o nó substituto é uma folha. Porém, se o substituto tiver filhos, é necessário reatribuí-los ao pai do substituto. Como o substituto é um nó extremo (mais à esquerda ou mais à direita), ele só pode ter um filho. Portanto, essa reatribuição é sempre viável.

# Inside the AVLTree class

  def delete(self, value):

    # Delete a value from the tree

    node = self.locate_node(value)

    if node is None:

      raise Exception("Value not stored in tree")

    replacement = None

    rebalance_node = node.parent

    if node.left is not None:

      # There's a left child so we replace with rightmost node

      replacement = self.rightmost(node.left)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.left)

      else:

        replacement.parent.set_right(replacement.left)

    elif node.right is not None:

      # There's a right child so we replace with the leftmost node

      replacement = self.leftmost(node.right)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.right)

      else:

        replacement.parent.set_right(replacement.right)

    if replacement:

      # We found a replacement so replace the value

      node.value = replacement.value

      rebalance_node = replacement.parent

    else:

      # No replacement so it means the node to delete is a leaf

      self.delete_leaf(node)

    if rebalance_node is not None:

      self.restore_balance(rebalance_node)

Consulta por intervalo

Consultas por intervalo consistem em identificar todos os valores que estão entre dois limites. Graças à ordenação das árvores AVL, conseguimos localizar esses valores com eficiência.

Para localizar todos os valores dentro do intervalo definido pelo limite inferior lb e limite superior ub, usamos uma busca recursiva na árvore. Para cada nó encontrado, se seu valor estiver no intervalo, incluímos no resultado. Em seguida, exploramos as subárvores esquerda e direita.

Ignoramos a subárvore esquerda se o valor do nó for menor que o limite inferior, pois todos os valores à esquerda serão menores que o do nó. Da mesma forma, ignoramos a subárvore direita se o valor do nó for maior que o limite superior, já que todos os valores à direita serão maiores que o do nó.

  def search(self, node, lb, ub, results):

    # Search for values between lower bound and upper bound

    if node is None:

      return

    if lb <= node.value and node.value <= ub:

      results.append(node.value)

    if node.value >= lb:

      self.search(node.left, lb, ub, results)

    if node.value <= ub:

      self.search(node.right, lb, ub, results)

  def range_query(self, lb, ub):

    # Search for values between lower bound and upper bound

    results = []

    self.search(self.root, lb, ub, results)

    return results

Outras árvores auto-balanceadas

Implementamos uma árvore AVL capaz de executar as seguintes operações:

• Adicionar um valor
• Remover um valor
• Buscar um valor
• Consultar o mínimo e o máximo
• Consultar todos os valores que estão entre dois limites

O pacote avltree package oferece uma implementação em Python com essas funcionalidades.

Outras árvores binárias de busca auto-balanceadas, como red-black trees, splay trees e B-trees, fornecem funcionalidades similares. Em geral, o desempenho é comparável na maioria das aplicações, já que todas mantêm altura logarítmica garantida. No entanto, árvores AVL são mais estritamente balanceadas, otimizando buscas ao custo de inserções possivelmente mais lentas devido ao rebalanço mais rigoroso.

Splay trees são especialmente eficazes em cenários em que elementos acessados recentemente são reutilizados com frequência, tornando-as uma ótima escolha para implementações de cache.

B-trees são projetadas para operar de forma eficiente em disco e não somente em memória, sendo valiosas para lidar com grandes volumes de dados que excedem a capacidade de memória, como na criação de índices de banco de dados.

Melhorias futuras

Há várias formas de melhorar nossa implementação. Aqui vão algumas sugestões de exercícios para aprofundar seu entendimento sobre árvores AVL:

• Na implementação atual, os nós armazenam apenas um único valor. Para uso como índices de banco de dados, é necessário armazenar linhas inteiras, já que o valor corresponderá a uma das colunas da tabela. Podemos aprimorar a implementação para que a árvore AVL funcione de forma semelhante a um dicionário, mapeando valores para suas linhas correspondentes.
• Nossa implementação não suporta valores duplicados. Porém, é possível modificá-la para permitir vários nós com o mesmo valor.
• Normalmente, árvores AVL são implementadas de forma recursiva. Optamos por evitar isso para não exigir domínio prévio de recursão. Embora implementações recursivas sejam mais elegantes e concisas, elas exigem uma boa compreensão do conceito.

Conclusão

BSTs são um tipo de estrutura de dados de árvore binária que organiza dados seguindo uma ordem específica. Essa organização evita inspecionar todo o dataset ao buscar valores específicos. No entanto, BSTs podem ficar desbalanceadas, degradando o desempenho e, em alguns cenários, exigindo inspecionar todo o conjunto de dados.

Árvores AVL resolvem esse problema impondo propriedades adicionais de balanceamento por meio de rotações. Essas propriedades mantêm a altura da árvore logarítmica em relação ao tamanho do conjunto de dados, oferecendo um grande ganho.

A complexidade de tempo logarítmica é uma melhoria substancial em relação à linear, tornando árvores AVL extremamente eficientes para consultas. Mesmo com bilhões de entradas, uma árvore AVL exige inspecionar apenas alguns pontos de dados para localizar um elemento, sendo muito mais eficiente.