De Wikilibros, la colección de libros de texto de contenido libre.
Sea un nodo de un heap, en el nivel
h
{\displaystyle h}
a
{\displaystyle a}
a
+
b
{\displaystyle a+b}
Archivo:Arbol heap.svg
El nivel siguiente
h
+
1
{\displaystyle h+1}
2
(
a
+
b
)
{\displaystyle 2(a+b)}
h
{\displaystyle h}
C
=
n
h
+
1
−
1
n
−
1
{\displaystyle C={\cfrac {n^{h+1}-1}{n-1}}}
Lo que, para un árbol binario es
C
=
2
h
+
1
−
1
2
−
1
=
2
h
+
1
−
1
{\displaystyle C={\cfrac {2^{h+1}-1}{2-1}}=2^{h+1}-1}
La cantidad total de nodos hasta el nivel
h
+
1
{\displaystyle h+1}
D
=
2
h
+
1
+
1
−
1
=
2
h
+
2
−
1
{\displaystyle 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
{\displaystyle D-C}
h
+
1
{\displaystyle h+1}
D
−
C
=
2
h
+
2
−
1
−
(
2
h
+
1
−
1
)
{\displaystyle D-C=2^{h+2}-1-(2^{h+1}-1)}
D
−
C
=
2
∗
2
h
+
1
−
2
h
+
1
{\displaystyle D-C=2*2^{h+1}-2^{h+1}}
D
−
C
=
2
h
+
1
(
2
−
1
)
{\displaystyle D-C=2^{h+1}(2-1)}
D
−
C
=
2
h
+
1
{\displaystyle D-C=2^{h+1}}
Archivo:Arbol heap2.svg
Y como
C
=
2
h
+
1
−
1
⇒
2
h
+
1
=
C
+
1
{\displaystyle C=2^{h+1}-1\Rightarrow 2^{h+1}=C+1}
D
−
C
=
C
+
1
{\displaystyle 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
{\displaystyle a+b-1}
De manera que el índice absoluto del nodo padre dentro del heap es:
p
a
d
r
e
=
(
a
+
b
−
1
)
+
a
=
2
a
+
b
−
1
{\displaystyle padre=(a+b-1)+a=2a+b-1}
Archivo:Arbol heap3.svg
Y el índice de sus hijos será entonces:
h
i
j
o
1
=
2
a
+
b
−
1
+
b
+
2
(
a
−
1
)
+
1
{\displaystyle hijo_{1}=2a+b-1+b+2(a-1)+1}
y
h
i
j
o
2
=
2
a
+
b
−
1
+
b
+
2
(
a
−
1
)
+
2
{\displaystyle hijo_{2}=2a+b-1+b+2(a-1)+2}
respectivamete.
Se puede entonces relacionar estos valores:
h
i
j
o
1
=
2
∗
(
2
a
+
b
−
1
)
=
2
∗
p
a
d
r
e
{\displaystyle hijo_{1}=2*(2a+b-1)=2*padre}
h
i
j
o
2
=
2
∗
(
2
a
+
b
−
1
)
+
1
=
2
∗
p
a
d
r
e
+
1
{\displaystyle hijo_{2}=2*(2a+b-1)+1=2*padre+1}
Archivo:Arbol heap4.svg
