(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.
(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 o filho esquerdo está em
e o direito em
.
(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
Passo 2
Quando usamos vetor contíguo para representar árvore binária, adotamos o mapeamento
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
pode ser necessário que o vetor tenha tamanho até
, 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:
Árvore:
A
/
B
/
C
Aqui a profundidade máxima é
, mas para armazenar
precisamos de índice
. A heap em vetor (índices começando em 1) fica:
(raiz)
(filho esquerdo de
)
(filho direito de
, vazio)
(filho esquerdo de
)
Isso significa vetor de tamanho pelo menos 4, mas só 3 nós reais. As posições “null” em ilustram o desperdício de espaço quando a árvore não é completa.
Isso significa vetor de tamanho pelo menos 4, mas só 3 nós reais. As posições “null” em
Resposta
(a) Porque a representação em vetor assume índices de filhos iguais a
e
; se a árvore não for completa, surgem muitos índices sem nó (buracos), forçando o vetor a ter tamanho até
e desperdiçando memória.
(b) Por exemplo, a árvore
A
/
B
/
C
faz com que a heap em vetor seja
,
ou seja, usamos 4 posições de vetor para armazenar apenas 3 nós, com um índice nulo no meio.
ou seja, usamos 4 posições de vetor para armazenar apenas 3 nós, com um índice nulo no meio.