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(){...}
}
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ãoPasso 3
No método
descendingOrder()
, fazemos:int n = size(root);
- Cria-se um array
T[] result = (T[]) new Comparable[n];
- Um índice mutável, por exemplo
int[] idx = {0};
- Chama-se o método auxiliar
fillDesc(root, result, idx);
- 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. - O método
fillDesc
também visita cada nó exatamente uma vez, custo. - Logo, o tempo total é
. - Em espaço, usamos um array de tamanho
e a pilha de recursão de profundidade máxima , onde é 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);
}
}