Árvore binária de busca balanceada

Em ciência da computação, uma árvore binária de busca balanceada ou árvore binária de busca auto-balanceada é qualquer árvore de busca binária que automaticamente mantém a sua altura (número máximo de níveis abaixo da raiz) pequeno mesmo depois de sucessivas inserções e exclusões arbitrárias.^[1]

Um exemplo de uma árvore desbalanceada; seguindo da raiz até um nó leva uma média de 3,27 acessos por outros nós

A mesma árvore após ser balanceada; a média de acessos foi reduzida para 3.00 acessos

Estas estruturas fornecem implementações eficientes para listas ordenadas mutáveis, podendo ser usadas para outras estruturas de dados abstratas, tais como arrays associativos, filas de prioridade e conjuntos.

Visão geral

Rotações são operações internas muito comuns em árvores binárias de busca balanceadas para manter um balanceamento perfeito ou quase perfeito.

A maioria das operações em uma árvore binária de busca (BST) leva um tempo diretamente proporcional à altura da árvore, por isso, é desejável manter a altura pequena. Uma árvore binária de altura h pode conter no máximo 2⁰+2¹+···+2^h = 2^h+1-1 nós. Segue-se que para uma árvore com n nós e altura h:

${\displaystyle n\leq 2^{h+1}-1}$

E isso implica que:

${\displaystyle h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor }$.

Em outras palavras, a altura mínima da árvore com n nós é log₂(n), arredondado para baixo; isto é, ${\displaystyle \lfloor \log _{2}n\rfloor }$.^[1]

No entanto, o mais simples dos algoritmos para inserção em BSTs pode resultar em uma árvore com altura n na maioria das situações. Por exemplo, quando os itens são inseridos de forma ordenada, a árvore se degenera em uma lista ligada com n nós. A diferença no desempenho entre as duas situações podem ser enormes: para n = 1.000.000, por exemplo, a altura mínima é ${\displaystyle \lfloor \log _{2}(1,000,000)\rfloor =19}$.

Se os dados são conhecidos, a altura pode ser mantido pequena, num sentido geral, adicionando valores em uma ordem aleatória, resultando em uma árvore de busca binária aleatória. No entanto, existem muitas situações (como em algoritmos online), onde esta aleatoriedade não é viável.

Árvores binárias de busca balanceadas resolvem este problema através da realização de transformações na árvore, como rotações), a fim de manter a altura proporcional a log₂(n). Apesar de uma certa sobrecarga estar envolvida, isso pode ser justificado, a longo prazo, assegurando a rápida execução de operações posteriores.

Manter a altura sempre no seu valor mínimo ${\displaystyle \lfloor \log _{2}(n)\rfloor }$ não é sempre viável; pode-se provar que qualquer algoritmo de inserção que faça isso causa uma sobrecarga excessiva.^{[carece de fontes?]} Portanto, a maioria dos algoritmos em BST balanceadas mantém a altura dentro de um fator constante próximo deste limite.

Em temos de complexidade ("Big-O"), uma árvore binária de busca balanceada contendo n itens permite a pesquisa, inserção e remoção de um item em O(log n) no pior caso de tempo, e uma ordenação de todos os itens em tempo O(n). Estes tempos são assintoticamente ideais entre todas as estruturas de dados que manipulam as chaves apenas por meio de comparações.

Implementações

Estruturas de dados populares que implementam este tipo de árvore incluem:

• Árvore 2-3
• Árvore AA
• Árvore AVL
• Árvore rubro-negra
• Árvore scapegoat
• Árvore splay
• Treap

Aplicações

Árvores binárias de busca balanceadas podem ser usadas para construir e manter listas ordenadas, tais como filas de prioridade. Elas também podem ser usadas para arrays associativos; Árvores binárias de busca balanceadas podem ser usadas para implementar qualquer algoritmo que requira listas ordenadas, para alcançar o melhor desempenho assintótico. Muitos algoritmos de geometria computacional exploram variações de BSTs balanceadas para resolver problemas, tais como a interseção entre segmentos de reta e o problema de localização do ponto de forma eficiente.

Referências

1. Donald Knuth.