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:
- Melhor caso de altura:
-
Árvore AVL:
- Melhor caso de altura:
- Pior caso de altura:
está na ordem de , aproximadamente
- Melhor caso de altura:
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.
(a) Toda árvore cheia é completa.