Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Unidad 3/Indexación de un heap

Sea un nodo de un heap, en el nivel $h$, con un desplazamiento $a$ dentro de su nivel, y con un total de nodos en el nivel $a+b$.

Archivo:Arbol heap.svg

El nivel siguiente $h+1$ tendrá entonces $2(a+b)$ nodos.

Además, la cantidad total de nodos hasta el nivel $h$ será:

$C={\cfrac {n^{h+1}-1}{n-1}}$

Lo que, para un árbol binario es

$C={\cfrac {2^{h+1}-1}{2-1}}=2^{h+1}-1$

La cantidad total de nodos hasta el nivel $h+1$ será:

$D=2^{h+1+1}-1=2^{h+2}-1$

Con lo cual se puede relacionar la cantidad de nodos de un nivel con la cantidad de nodos del resto del árbol encima de él. $D-C$ es la cantidad de nodos en el nivel $h+1$:

$D-C=2^{h+2}-1-(2^{h+1}-1)$ $D-C=2*2^{h+1}-2^{h+1}$ $D-C=2^{h+1}(2-1)$ $D-C=2^{h+1}$

Archivo:Arbol heap2.svg

Y como $C=2^{h+1}-1\Rightarrow 2^{h+1}=C+1$:

$D-C=C+1$

Lo que permite concluir:

La cantidad de nodos de un nivel h+1 de un árbol binario, es igual a la cantidad de nodos de todo el árbol hasta el nivel h, más uno.

De esta forma podemos obtener el desplazamiento dentro del heap, del nivel h:

$a+b-1$

De manera que el índice absoluto del nodo padre dentro del heap es:

$padre=(a+b-1)+a=2a+b-1$

Archivo:Arbol heap3.svg

Y el índice de sus hijos será entonces:

$hijo_{1}=2a+b-1+b+2(a-1)+1$

y

$hijo_{2}=2a+b-1+b+2(a-1)+2$

respectivamete.

Se puede entonces relacionar estos valores:

$hijo_{1}=2*(2a+b-1)=2*padre$

$hijo_{2}=2*(2a+b-1)+1=2*padre+1$

Archivo:Arbol heap4.svg