El peor de los casos en Max-Heapify: ¿cómo se obtiene 2n / 3?

En CLRS, tercera edición, en la página 155, se da que en MAX-HEAPIFY,

Cada uno de los subárboles de los niños tiene un tamaño máximo de 2n / 3 ; el peor de los casos ocurre cuando el nivel inferior del árbol está exactamente medio lleno.

Entiendo por qué es peor cuando el nivel inferior del árbol está exactamente medio lleno. Y también se responde en esta pregunta en el peor de los casos en MAX-HEAPIFY: "el peor de los casos ocurre cuando el nivel inferior del árbol está exactamente medio lleno"

Mi pregunta es cómo conseguir 2n / 3?

¿Por qué si el nivel inferior está medio lleno, entonces el tamaño del árbol secundario es de hasta 2n / 3?

¿Cómo calcular eso?

Gracias

En un árbol donde cada nodo tiene exactamente 0 o 2 hijos, el número de nodos con 0 hijos es uno más que el número de nodos con 2 hijos. {Explicación: el número de nodos a la altura h es 2 ^ h, que por el fórmula de suma de una serie geométrica es igual (suma de nodos desde la altura 0 hasta h-1) + 1; y todos los nodos desde la altura 0 hasta h-1 son los nodos con exactamente 2 hijos}

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

Sea k el número de nodos en R. El número de nodos en L es k + (k + 1) = 2k + 1. El número total de nodos es n = 1 + (2k + 1) + k = 3k + 2 (raíz más L más R). La relación es (2k + 1) / (3k + 2), que está acotada arriba por 2/3. No funciona una constante menor que 2/3, porque el límite cuando k llega al infinito es 2/3.

Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.

Una vez que está claro, el límite de 2N / 3 es fácil de conseguir.

Supongamos que el número total de nodos del árbol es N.

Número de nodos en el árbol = 1 + (Número de nodos en el subárbol izquierdo) + (Número de nodos en el subárbol derecho)

Para nuestro caso donde el árbol tiene el último nivel medio lleno, si asumimos que el subárbol derecho es de altura h, entonces el subárbol izquierdo es de altura (h + 1):

Número de nodos en el subárbol izquierdo = 1 + 2 + 4 + 8 .... 2 ^ (h + 1) = 2 ^ (h + 2) -1 ..... (i)

Número de nodos en el subárbol derecho = 1 + 2 + 4 + 8 .... 2 ^ (h) = 2 ^ (h + 1) -1 ..... (ii)

Por lo tanto, conectarse a:

Número de nodos en el árbol = 1 + (Número de nodos en el subárbol izquierdo) + (Número de nodos en el subárbol derecho)

=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)

=> N = 1 + 3*(2^(h+1)) - 2

=> N = 3*(2^(h+1)) -1

=> 2^(h+1) = (N + 1)/3

Conectando este valor en la ecuación (i), obtenemos:

Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)

Por lo tanto, el límite superior del número máximo de nodos en un subárbol para un árbol con N nodos es 2N / 3.

Para un árbol binario completo de altura h, el número de nodos es f(h) = 2^h - 1. En el caso anterior, tenemos un árbol binario casi completo con la mitad inferior llena. Podemos visualizar esto como una colección de root + left complete tree + right complete tree. Si la altura del árbol original es h, entonces la altura de la izquierda es h - 1y la derecha es h - 2. Entonces la ecuación se convierte en

n = 1 + f(h-1) + f(h-2) (1)

Queremos resolver lo anterior para f(h-1)expresado en términos den

f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/2 (2)

Usando arriba en (1) tenemos

n = 1 + f(h-1) + (f(h-1) - 1)/2 = 1/2 + 3*f(h-1)/2

=> f(h-1) = 2*(n-1/2)/3

Por tanto, O (2n / 3)

Para agregar a la respuesta de Swen. Cómo (2k + 1) / (3k + 2) tiende a 2/3, cuando k tiende a infinito,

Lim_ (k -> inf) (2k + 1) / (3k + 2) = Lim_ (k -> inf) k (2 + 1 / k) / k (3 + 2 / k) = Lim_ (k -> inf ) (2 + 1 / k) / (3 + 2 / k)

aplica el límite y obtienes 2/3

Número de nodos en -

• nivel 0, es decir, la raíz es 2 ^ 0
• el nivel 1 es 2 ^ 1
• el nivel 2 es 2 ^ 2
• ...
• el nivel n es 2 ^ n

Suma de todos los nodos desde el nivel 0 hasta el nivel n,

• S = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ n

De la regla de suma de series geométricas sabemos que

• x ^ 0 + x ^ 1 + x ^ 2 + ... + x ^ (n) = (x ^ (n + 1) - 1) / (x-1)

Sustituyendo x = 2, obtenemos

• S = 2 ^ (n + 1) - 1. es decir, 2 ^ (n + 1) = S + 1

Como 2 ^ (n + 1) es el total de nodos en el nivel n + 1, podemos decir que el número de nodos con 0 hijos es uno más que el número de nodos con 2 hijos.

Ahora calculemos el número de nodos en el subárbol izquierdo, el árbol derecho y el total.

• Suponga que el número de nodos que no son hojas en el subárbol izquierdo de root = k.

• Según el razonamiento anterior, el número de nodos de hojas en el subárbol izquierdo o raíz = k + 1. Número de nodos que no son de hojas en el subárbol derecho de root = k ya que se dice que el árbol está exactamente medio lleno.

• Número total de nodos en el subárbol izquierdo de la raíz = k + k + 1 = 2k +

• Número total de nodos en el árbol, n = (2k + 1) + k + 1 = 3k + 2.
• Relación de nodos en el subárbol izquierdo y nodos totales = (2k + 1) / (3k + 2) que está acotado arriba por 2/3.

Esa es la razón por la que se dice que los subárboles de los niños tienen un tamaño máximo de 2n / 3.