Qual o melhor e o pior caso de altura de uma árvore binária de busca e uma árvore AVL para um mesmo número de elementos?

Passo 1

Beleza, vamos entender qual é a pergunta! Estamos falando sobre árvores binárias de busca (ABB) e árvores AVL. O exercício quer saber qual é a altura dessas árvores nos melhores e piores casos quando temos o mesmo número de elementos, que chamamos de n. Para resolver isso, vamos precisar entender o que é altura de uma árvore, como diferentes estruturas de árvores afetam essa altura, e algumas propriedades específicas das árvores AVL.

Passo 2

Primeiro, vamos definir altura da árvore. A altura de uma árvore é o número de nós no caminho mais longo da raiz até uma folha. Ela nos dá uma ideia de quão “profunda” a árvore está. Uma árvore com menor altura é geralmente mais eficiente para operações como busca, inserção e remoção.

Passo 3

Vamos falar sobre a Árvore Binária de Busca (ABB). Em uma ABB, para cada nó, os valores à esquerda são menores e à direita são maiores.
  • Melhor caso: A árvore está perfeitamente balanceada, ou seja, cada nível está completamente cheio. Nesse caso, a altura é mínima e calculada por:
  • Pior caso: A árvore está totalmente desbalanceada, como uma lista ligada, onde cada nó tem apenas um filho. A altura máxima é:

Passo 4

Agora, vamos para a Árvore AVL. As árvores AVL são um tipo de ABB que se mantém balanceada automaticamente após cada operação de inserção ou remoção. A diferença principal é que em uma AVL, para cada nó, as alturas das subárvores esquerda e direita diferem no máximo em 1.
  • Melhor caso: Assim como na ABB, se a árvore estiver perfeitamente balanceada, a altura é:
  • Pior caso: Devido ao balanceamento rígido, a altura máxima de uma árvore AVL é: Mas, para simplificar, podemos dizer que a altura está na ordem de .

Passo 5

Comparando as duas estruturas:
  • ABB pode ter uma altura que varia de a , dependendo de como os elementos são inseridos.
  • Árvore AVL sempre mantém a altura na ordem de , garantindo operações eficientes.

Resposta

Para um número de elementos:
  • Árvore Binária de Busca (ABB):
    • Melhor caso de altura:
    • Pior caso de altura:
  • Árvore AVL:
    • Melhor caso de altura:
    • Pior caso de altura: está na ordem de , aproximadamente
Isso significa que, enquanto a ABB pode ter alturas muito grandes se não estiver balanceada, a árvore AVL garante que a altura permaneça sempre proporcional a , tornando-a mais eficiente para grandes conjuntos de dados.

Exercícios relacionados

  • Faça um programa que dados um inteiro e um inteiro (representando um dígito, ou seja, ), devolve quantas vezes o dígito aparece em .
Considerando alunos de uma determinada classe onde são dadas 3 provas. Faça um programa que calcula a média aritmética das provas de cada aluno, a média da classe, o número de aprovados e o número de reprovados (critério de aprovação: média maior ou igual a seis).
Detalhar o algoritmo de remoção de nós em árvores AVL.
Prove ou dê um contraexemplo para as afirmações abaixo:
(a) Toda árvore cheia é completa.