Projete um algoritmo para determinar o menor número em uma árvore AVL.

Passo 1

Enunciado resumido: a gente precisa projetar um algoritmo que, dada uma árvore AVL (uma árvore binária de busca balanceada), retorne o menor valor armazenado nela. Vamos usar a propriedade fundamental de toda árvore binária de busca: o menor elemento está sempre no caminho mais à esquerda.
Teoria usada: uma árvore AVL é uma árvore binária de busca balanceada por altura. Na ABP (árvore binária de busca), todo nó tem valores menores na subárvore esquerda e maiores na subárvore direita. Por isso, para achar o menor, basta seguir o ponteiro esquerdo repetidamente até chegar em um nó sem filho à esquerda.

Passo 2

Início do algoritmo: defina uma função Minimo(root) que receba a raiz da árvore. Primeiro, verifique se a raiz é nula. Se for, a árvore está vazia e você pode retornar um erro ou valor especial.
Percorra a subárvore esquerda: enquanto o nó atual tiver um filho à esquerda, atualize o nó atual para esse filho à esquerda. Isso leva você ao nó mais à esquerda da árvore.
Resultado final: quando o loop terminar, o nó atual será o mais à esquerda e, portanto, conterá o menor valor. Retorne esse valor.

Passo 3

Complexidade e conclusão: como a árvore AVL tem altura O(log n), esse algoritmo roda em tempo O(log n), o que é eficiente.

Resposta

Algoritmo Minimo(root):
  1. Se root == null, retornar erro/valor especial (árvore vazia).
  2. let node = root
  3. enquanto node.esquerda != null faça
    node = node.esquerda
  4. retornar node.valor

Exercícios relacionados