Escreva uma função que encontra o valor máximo em uma árvore de busca binária.
Passo 1
O enunciado pede para escrever uma função que, dada uma árvore de busca binária (BST), retorna o maior valor armazenado nela. O conteúdo aqui é a propriedade de BST e a iteração em estruturas encadeadas.
Passo 2
Em uma BST, todo nó à direita de um dado nó contém valor maior do que o próprio nó. Logo, o maior valor da árvore estará sempre no nó mais à direita (aquele que não tem filho direito).
Podemos criar um algoritmo iterativo que comece na raiz e percorra sucessivamente o ponteiro direito até encontrar um nó cuja referência direita seja nula. Esse nó é o de maior valor.
Podemos criar um algoritmo iterativo que comece na raiz e percorra sucessivamente o ponteiro direito até encontrar um nó cuja referência direita seja nula. Esse nó é o de maior valor.
Passo 3
A seguir está a implementação em pseudocódigo (estilo Python) da função find_max de forma iterativa:
def find_max(root):
if root is None:
raise ValueError(“Árvore vazia não tem máximo”)
current = root
while current.right is not None:
current = current.right
return current.value
if root is None:
raise ValueError(“Árvore vazia não tem máximo”)
current = root
while current.right is not None:
current = current.right
return current.value
Passo 4
A complexidade desse método é O(h), onde h é a altura da árvore. No pior caso (árvore degenerada), h = n e a complexidade é O(n). No melhor caso (árvore balanceada), h = log n e o método roda em O(log n).
Resposta
def find_max(root):
if root is None:
raise ValueError(“Árvore vazia não tem máximo”)
current = root
while current.right is not None:
current = current.right
return current.value
if root is None:
raise ValueError(“Árvore vazia não tem máximo”)
current = root
while current.right is not None:
current = current.right
return current.value