Árvore completa

Se você já sabe o que é um heap, basta considerar que estou falando apenas
dos índices do heap binário no vetor (começando em \(1\)), ignorando completamente
os valores.

Para quem não sabe o que é Heap, considere uma árvore binária completa
em que os valores dos nós são preenchidos seqüencialmente com uma busca
em largura que explora primeiro o nó da esquerda. Para explicar com um desenho:

         1
       /   \
      2     3
     / \   / \
    4   5 6   7
   / \
  8   9

Observe que, dado um valor \(v\) (\(2\) por exemplo), podemos encontrar o valor
do filho esquerdo fazendo \(2v\) (\(2\times 2 = 4\) por exemplo), \(2v + 1\) para
o da direita (\(2\times 2 + 1 = 5\) por exemplo), e também podemos encontrar
o pai fazendo \(\lfloor v/2 \rfloor\).

Uma árvore binária completa é uma árvore em que todos os níveis estão
completamente preenchidos, exceto possivelmente pelo último, que deve ser
preenchido da esquerda para a direita (o exemplo é uma árvore completa, se
retirarmos o \(9\) ou o \(8\) e o \(9\), continua sendo, mas se retirarmos apenas
o \(8\) ou apenas o \(7\), não é mais uma árvore completa).

Questões

Ao responder a pergunta "Por que a inserção no heap ocorre de baixo para
cima?", surgiu a dúvida: além do pai e dos filhos de um nó \(v\), o que
mais podemos descobrir sem precisar percorrer a árvore? Não tentei nada,
mas achei que seria interessante levantar esse questionamento aqui.

Seja \(n\) o número de nós de uma árvore completa e \(r\) um nó. Considere
a subárvore com raiz \(r\).

Algumas perguntas:

• Como determinar se a subárvore com raiz \(r\) está completamente preenchida?
• Qual a altura da subárvore com raiz \(r\)?
• Como calcular o número de nós da subárvore com raiz \(r\)?
• Qual a distância da raiz (nó \(1\)) até \(r\)?
• Qual a distância de \(r\) até um nó \(v\) que faz parte da subárvore com raiz \(r\)?
• Qual a distância entre dois nós \(u\) e \(v\)?

O interesse principal é na primeira pergunta, que foi o que faltou na minha
resposta sobre inserção em heap.