Considere o código de uma BST abaixo. Utilizando recursão (no próprio método ou em algum método auxiliar), complete a implementação do método descendingOrder(), que retorna um array contendo as chaves da árvore ordenadas em valor decrescente. Faça a análise de seu algoritmo. Obs: sua implementação NÃO pode originar um array ordenado e depois inverter!
public class BSTNode<T extends
        Comparable<T> > {
    protected T data;
    protected BSTNode<T> left;
    protected BSTNode<T> right;
    protected BSTNode<T> parent;
}
public class BSTImpl<T extends
        Comparable<T>> implements
            BST<T> {
        protected BSTNode<T> root;
    public T[] descendingOrder(){...}
}

Passo 1

O objetivo é implementar o método descendingOrder() de uma BST genérica de forma recursiva, de modo que o resultado seja um array contendo todas as chaves em ordem estritamente decrescente. O conteúdo que vamos usar é o percurso em ordem reversa (right → root → left) e a ideia de primeiro determinar o número de nós para criar um array do tamanho exato.

Passo 2

Para criar o array de tamanho exato, precisamos saber quantos nós a árvore tem. Uma forma é implementar um método size(BSTNode<T> node) recursivo que retorne 0 se node for null ou então
\text{size}(node) = 1 + \text{size}(node.left) + \text{size}(node.right).

Passo 3

No método descendingOrder(), fazemos:
  1. int n = size(root);
  2. Cria-se um array T[] result = (T[]) new Comparable[n];
  3. Um índice mutável, por exemplo int[] idx = {0};
  4. Chama-se o método auxiliar fillDesc(root, result, idx);
  5. Retorna-se result.

Passo 4

O método auxiliar fillDesc(BSTNode<T> node, T[] arr, int[] idx) funciona assim:
  • Se node == null, retorna imediatamente.
  • Faz fillDesc(node.right, arr, idx);
  • Atribui arr[idx[0]++] = node.data;
  • Faz fillDesc(node.left, arr, idx);
Isso garante que visitemos primeiro os maiores (filho direito), depois a raiz, depois os menores.

Passo 5

Análise de complexidade:
  • O método size visita cada nó exatamente uma vez, custo \text{O}(n).
  • O método fillDesc também visita cada nó exatamente uma vez, custo \text{O}(n).
  • Logo, o tempo total é \text{O}(n).
  • Em espaço, usamos um array de tamanho n \text{O}(n) e a pilha de recursão de profundidade máxima h \text{O}(h), onde h é a altura da árvore.

Resposta

public class BSTImp\(l<T\) extends Comparabl\(e<T\)>> implements BS\(T<T\)> {
 protected BSTNod\(e<T\)> root;

 @Override
 public T[] descendingOrder() {
 int n = size(root);
 @SuppressWarnings("unchecked")
 T[] result = (T[]) new Comparable[n];
 int[] idx = {0};
 fillDesc(root, result, idx);
 return result;
 }

 private int size(BSTNod\(e<T\)> node) {
 if (node \(==\) null) return 0;
 return \(1+\) size(node.left) + size(node.right);
 }

 private void fillDesc(BSTNod\(e<T\)> node, T[] arr, int[] idx) {
 if (node \(==\) null) return;
 fillDesc(node.right, arr, idx);
 arr[idx[0]\(++\)] = node.data;
 fillDesc(node.left, arr, idx);
 }
}

Exercícios relacionados