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.
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.
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):
- Se root == null, retornar erro/valor especial (árvore vazia).
- let node = root
- enquanto node.esquerda != null faça
node = node.esquerda - retornar node.valor