Árvores binárias de busca

Professora Ilze O.

Identidade verificada

• CPF verificado
• E-mail verificado

Respondeu há 1 ano

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.