(8 pontos) Responda:
(a) (3 pontos) Por que não se aconselha usar heap para representar uma árvore binária a menos que esta seja completa ou quase completa?
(b) ( 5 pontos) Dê um exemplo que ilustre a situação acima, ilustrando com uma árvore e sua respectiva heap.

Passo 1

O enunciado pede duas coisas:
(a) explicar por que não se aconselha usar uma heap (isto é, representação de árvore binária em vetor) quando a árvore não é completa ou quase completa;
(b) dar um exemplo que ilustre esse problema, mostrando uma árvore e sua respectiva representação em vetor.
O conteúdo é estrutura de dados, mais precisamente as formas de representar árvore binária em vetor (heap), em que para um nó no índice i o filho esquerdo está em 2i e o direito em 2i+1.

Passo 2

Quando usamos vetor contíguo para representar árvore binária, adotamos o mapeamento
\text{filho-esq}(i)=2i,\quad \text{filho-dir}(i)=2i+1.
Se a árvore não for completa, aparecem “buracos” no vetor: posições sem nó que precisamos marcar como nulo. Para atingir um nó em profundidade h pode ser necessário que o vetor tenha tamanho até 2^{h+1}-1, mesmo que haja muito poucos nós. Isso desperdiça memória (muitas células vazias) e torna operações de varredura ineficientes. Em contraste, na representação por ponteiros cada nó só ocupa espaço proporcional a si mesmo (dois ponteiros mais o dado), sem lacunas.

Passo 3

Exemplo simples de árvore esparsa (apenas ramo à esquerda):
Árvore:
 A
 /
 B
 /
C
Aqui a profundidade máxima é 2, mas para armazenar C precisamos de índice 4. A heap em vetor (índices começando em 1) fica: H[1]=A (raiz) H[2]=B (filho esquerdo de A) H[3]=\text{null} (filho direito de A, vazio) H[4]=C (filho esquerdo de B)
Isso significa vetor de tamanho pelo menos 4, mas só 3 nós reais. As posições “null” em H[3] ilustram o desperdício de espaço quando a árvore não é completa.

Resposta

(a) Porque a representação em vetor assume índices de filhos iguais a 2i e 2i+1; se a árvore não for completa, surgem muitos índices sem nó (buracos), forçando o vetor a ter tamanho até 2^{h+1}-1 e desperdiçando memória.
(b) Por exemplo, a árvore
 A
 /
 B
 /
C
faz com que a heap em vetor seja H[1]=A,\;H[2]=B,\;H[3]=\text{null},\;H[4]=C,
ou seja, usamos 4 posições de vetor para armazenar apenas 3 nós, com um índice nulo no meio.

Exercícios relacionados