Ir al contenido

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

De Wikilibros, la colección de libros de texto de contenido libre.

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=nh+1−1n−1

Lo que, para un árbol binario es

C=2h+1−12−1=2h+1−1

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

D=2h+1+1−1=2h+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=2h+2−1−(2h+1−1) D−C=2∗2h+1−2h+1 D−C=2h+1(2−1) D−C=2h+1

Archivo:Arbol heap2.svg

Y como C=2h+1−1⇒2h+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:

hijo1=2a+b−1+b+2(a−1)+1

y

hijo2=2a+b−1+b+2(a−1)+2

respectivamete.

Se puede entonces relacionar estos valores:

hijo1=2∗(2a+b−1)=2∗padre

hijo2=2∗(2a+b−1)+1=2∗padre+1

Archivo:Arbol heap4.svg