algorithm tree heap time-complexity

algorithm - min heap c++



El peor caso en Max-Heapify: ¿Cómo obtienes 2n/3? (5)

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

Cada uno de los subárboles infantiles 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, el peor caso en MAX-HEAPIFY: "el peor caso ocurre cuando el nivel inferior del árbol está exactamente medio lleno"

Mi pregunta es ¿cómo obtener 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: número de nodos en la altura h es 2 ^ h, que por la fórmula de suma de una serie geométrica es igual a (suma de nodos desde la altura 0 hasta h-1) + 1; y todos los nodos desde la altura 0 a 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á delimitada arriba por 2/3. Ninguna constante inferior a 2/3 funciona, porque el límite cuando k va hasta el infinito es 2/3.

Número de nodos en -

  • nivel 0 es decir, la raíz es 2 ^ 0
  • nivel 1 es 2 ^ 1
  • 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 vamos a calcular el número de nodos en el subárbol izquierdo, el árbol derecho y el total.

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

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

  • Número total de nodos en el subárbol izquierdo de root = 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á delimitado arriba por 2/3.

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

Para añadir 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.

Para un árbol binario completo de altura h , el número de nodos es f(h) = 2^h - 1 . En el caso anterior tenemos casi completo el árbol binario 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 , la altura de la izquierda es h - 1 y la derecha es h - 2 . Entonces la ecuación se convierte

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

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

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 lo tanto, O (2n / 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 obtener.

Supongamos que el número total de nodos en el á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, luego el subárbol izquierdo si 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, conectar en:

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

Al insertar 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 en el número máximo de nodos en un subárbol para un árbol con N nodos es 2N / 3.