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.
Ir a la navegación Ir a la búsqueda

Sea un nodo de un heap, en el nivel , con un desplazamiento dentro de su nivel, y con un total de nodos en el nivel .

Archivo:Arbol heap.svg

El nivel siguiente tendrá entonces nodos.


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

Lo que, para un árbol binario es

La cantidad total de nodos hasta el nivel será:

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. es la cantidad de nodos en el nivel :

Archivo:Arbol heap2.svg

Y como :

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:

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

Archivo:Arbol heap3.svg

Y el índice de sus hijos será entonces:

y

respectivamete.

Se puede entonces relacionar estos valores:

Archivo:Arbol heap4.svg