Árvores binárias de busca

Question

11) Com base na lógica de Árvores Binárias de Busca, considere que se tem uma classe BST
com o método getRoot(), que retorna um objeto da classe BSTNode, que, por sua vez,
possui os seguintes métodos disponíveis: isNIL() — retornando um booleano —,
getData() — retornando um inteiro — e getLeft() e getRight() — que retornam um
objeto da classe BSTNode. Escreva um método em Java que, dada uma árvore do tipo BST,
calcule a diferença entre o maior e o menor número inteiro armazenados na árvore.
Comente o comportamento assintótico do seu método.

int maiorDiferenca(BST arvore) {
//...
}

Ilze O. · Accepted Answer

Para calcular a diferença entre o maior e o menor número inteiro armazenados em uma árvore BST, podemos percorrer a árvore de forma recursiva, mantendo uma variável que armazena o valor máximo encontrado até o momento e outra variável que armazena o valor mínimo encontrado até o momento. A cada nó visitado, comparamos o valor do nó com as variáveis de máximo e mínimo e atualizamos as variáveis se necessário.

Segue abaixo a implementação do método em Java:

public int diferencaMinMax(BSTNode root) {
if (root.isNIL()) {
return 0;
}
int min = root.getData();
int max = root.getData();
if (!root.getLeft().isNIL()) {
int diffLeft = diferencaMinMax(root.getLeft());
if (diffLeft < min) {
min = diffLeft;
}
if (diffLeft > max) {
max = diffLeft;
}
}
if (!root.getRight().isNIL()) {
int diffRight = diferencaMinMax(root.getRight());
if (diffRight < min) {
min = diffRight;
}
if (diffRight > max) {
max = diffRight;
}
}
return max - min;
}

O comportamento assintótico do método depende da estrutura da árvore BST. Em uma árvore balanceada, a complexidade é O(log n), já que a cada nível da árvore a quantidade de nós a serem visitados é reduzida pela metade. Em uma árvore não balanceada, a complexidade pode chegar a O(n), caso a árvore esteja totalmente desbalanceada em uma das direções.

Árvores binárias de busca

Um professor já respondeu

Envie suas dúvidas pelo App. Baixe agora

Precisa de outra solução? Conheça