Escreva e implemente um algoritmo que dada uma ABB, construa uma outra árvore ABB aproximadamente completa. Para isso, obtenha todas as chaves e valores e insira na nova árvore sempre o elemento mediano das chaves ainda não inseridas.

Passo 1

O exercício pede que, dada uma ABB (árvore binária de busca), a gente construa outra ABB aproximadamente completa, inserindo sempre o elemento mediano das chaves ainda não inseridas. Para resolver isso, vamos precisar entender como extrair todas as chaves em ordem crescente (usando percurso inorder) e como construir recursivamente uma árvore balanceada a partir de um vetor ordenado.

Passo 2

Primeiro, fazemos um percurso inorder na árvore original para coletar todos os pares (chave, valor) em um vetor. Em uma ABB, o percurso inorder visita a subárvore esquerda, depois o nó e depois a subárvore direita, o que naturalmente produz uma sequência de chaves ordenadas.
Em seguida, definimos uma função recursiva buildTree(vetor, início, fim) que constrói a árvore aproximadamente completa: se início > fim, retorna null; senão calcula o índice mediano mid = (início + fim) // 2; cria um novo nó com vetor[mid], e configura suas subárvores esquerda e direita chamando buildTree(vetor, início, mid-1) e buildTree(vetor, mid+1, fim), respectivamente. Esse processo garante que a cada passo escolhamos a mediana e mantenhamos a árvore equilibrada.

Passo 3

Por fim, chamamos buildTree sobre todo o intervalo do vetor (0 até n-1) e retornamos a raiz resultante. Assim obtemos uma nova ABB aproximadamente completa. A complexidade é O(n) no tempo (pois percorremos a árvore uma vez e depois construímos a árvore em tempo linear) e O(n) no espaço extra para o vetor.

Passo 4

Segue abaixo o pseudocódigo completo em estilo de implementação genérica.

Resposta

// Reconstrói uma ABB aproximadamente completa a partir de outra ABB
function rebuildABB(origRoot):
let lista = empty list of (key, value)
inorder(origRoot, lista)
return buildTree(lista, 0, lista.size - 1)
// Percurso inorder para preencher lista com pares (chave, valor) em ordem crescente
function inorder(node, lista):
if node == null:
return
inorder(node.left, lista)
lista.add((node.key, node.value))
inorder(node.right, lista)
// Constroi recursivamente a árvore aproximadamente completa
function buildTree(lista, inicio, fim):
if inicio > fim:
return null
mid = floor((inicio + fim) / 2)
let (k, v) = lista[mid]
let novoNo = new Node(k, v)
novoNo.left = buildTree(lista, inicio, mid - 1)
novoNo.right = buildTree(lista, mid + 1, fim)
return novoNo

Exercícios relacionados