Este simulador de árvore binária de busca desenha a árvore a cada operação e mostra o caminho percorrido na busca. No modo AVL, ele exibe o fator de balanceamento de cada nó e informa qual rotação foi feita, como nos exercícios de estrutura de dados.
Complexidade
| Operação | BST balanceada | BST degenerada | AVL |
|---|---|---|---|
| Busca | O(log n) | O(n) | O(log n) |
| Inserção | O(log n) | O(n) | O(log n) |
| Remoção | O(log n) | O(n) | O(log n) |
Remoção em Árvore Binária de Busca
- Nó folha: basta remover.
- Nó com um filho: o filho ocupa o lugar do nó removido.
- Nó com dois filhos: o nó é substituído pelo sucessor (o menor valor da subárvore direita), que é removido do lugar original.
Inserção em Python
class No:
def __init__(self, valor):
self.valor = valor
self.esq = None
self.dir = None
def inserir(raiz, valor):
if raiz is None:
return No(valor)
if valor < raiz.valor:
raiz.esq = inserir(raiz.esq, valor)
elif valor > raiz.valor:
raiz.dir = inserir(raiz.dir, valor)
return raiz
def em_ordem(raiz):
if raiz:
em_ordem(raiz.esq)
print(raiz.valor)
em_ordem(raiz.dir)Rotação à Direita (AVL) em C
No* rotacao_direita(No* y) {
No* x = y->esq;
y->esq = x->dir;
x->dir = y;
y->altura = 1 + max(altura(y->esq), altura(y->dir));
x->altura = 1 + max(altura(x->esq), altura(x->dir));
return x; /* nova raiz da subárvore */
}Perguntas Frequentes
O que é uma árvore binária de busca?
É uma árvore em que cada nó tem no máximo dois filhos, e todos os valores da subárvore esquerda são menores que o nó e todos os da direita são maiores. Isso permite buscar, inserir e remover descartando metade da árvore a cada comparação, quando ela está balanceada.
O que é uma árvore AVL?
É uma árvore binária de busca que se mantém balanceada: em todo nó, a diferença de altura entre as subárvores esquerda e direita (o fator de balanceamento) é no máximo 1. Quando uma inserção ou remoção quebra essa regra, a árvore faz rotações para se reequilibrar.
Quais são as rotações da AVL?
Rotação simples à direita (caso esquerda-esquerda), rotação simples à esquerda (caso direita-direita), rotação dupla esquerda-direita e rotação dupla direita-esquerda. As duplas acontecem quando o desequilíbrio forma um zigue-zague.
Por que balancear a árvore?
Sem balanceamento, inserir valores já ordenados (1, 2, 3, 4...) gera uma árvore que é praticamente uma lista, com altura n, e a busca vira O(n). A AVL garante altura O(log n), então busca, inserção e remoção ficam O(log n) sempre. Teste inserindo 1 a 7 nos dois modos.
Para que serve o percurso em ordem?
Em uma árvore binária de busca, o percurso em ordem (esquerda, raiz, direita) visita os valores em ordem crescente. A pré-ordem serve para copiar a árvore, e a pós-ordem para apagá-la ou avaliar expressões.