Proporcione un límite superior asintótico en la altura de un árbol de búsqueda binaria n-nodo en el que la profundidad promedio de un nodo es Θ (lg n)

Question

Recientemente, estoy tratando de resolver todos los ejercicios en CLRS. pero hay algunos de ellos que no puedo entender. Aquí es uno de ellos, de CLRS ejercicio 12,4-2:

describir un árbol de búsqueda binaria en n nodos de tal manera que la profundidad media de un nodo en el árbol es Θ (lg n) pero la altura del árbol es ω (lg n). Asigne un límite superior asintótico a la altura de un árbol binario de búsqueda de nodos en el que la profundidad promedio de un nodo sea Θ (lg n).

¿Alguien puede compartir algunas ideas o referencias para resolver este problema? Gracias.

Answer 1

Supongamos que construimos el árbol de esta manera: dados n nodos, tome f (n) nodos y déjelos a un lado. Luego construya un árbol construyendo un árbol binario perfecto donde la raíz tiene un subárbol izquierdo que es un árbol binario perfecto de n - f (n) - 1 nodos y un subárbol derecho que es una cadena de longitud f (n). Elegiremos f (n) más tarde.

Entonces, ¿cuál es la profundidad promedio en el árbol? Como solo queremos un límite asintótico, vamos a elegir n tal que n - f (n) - 1 es uno menos que una potencia perfecta de dos, por ejemplo, 2^k - 1. En ese caso, la suma de las alturas en este parte del árbol es 1 * 2 + 2 * 3 + 4 * 4 + 8 * 5 + ... + 2^(k-1) * k, que es (IIRC) aproximadamente k 2^k, que es casi (n - f (n)) log (n - f (n)) por nuestra elección de k. En la otra parte del árbol, la profundidad total es aproximadamente f (n)^2. Esto significa que la longitud promedio del camino es aproximadamente ((n - f (n)) log (n - f (n)) + f (n)^2)/n. Además, la altura del árbol es f (n). Por lo tanto, queremos maximizar f (n) manteniendo la profundidad promedio O (log n).

Para ello, tenemos que encontrar f (n) tal que

1. n - f (n) = Θ (n), o el término de registro en el numerador desaparece y la altura no es logarítmico,
2. f (n)^2/n = O (log n), o el segundo término en el numerador se vuelve demasiado grande.

Si elige f (n) = Θ (sqrt (n log n)), creo que 1 y 2 se cumplen al máximo. Así que apostaría (aunque podría estar totalmente equivocado sobre esto) que esto es lo mejor que se puede obtener. Obtiene un árbol de altura Θ (sqrt (n log n)) que tiene una profundidad promedio Θ (Log n).

Espero que esto ayude! Si mis cálculos están muy lejos, házmelo saber. Es tarde ahora y no he hecho mi doble verificación habitual. :-)

Answer 2

maximice primero la altura del árbol. (tiene un árbol donde cada nodo solo tiene un nodo hijo, por lo que tiene una cadena larga hacia abajo).

Compruebe la profundidad promedio. (obviamente, la profundidad promedio será demasiado alta).

mientras que la profundidad promedio es demasiado alta, debe disminuir la altura del árbol en uno. Hay muchas formas de reducir la altura del árbol en una. Elija la manera que minimiza la altura promedio. (demuestre por inducción que cada vez debe seleccionar el que minimiza la altura promedio). Continúa hasta que caigas bajo el requisito de altura promedio. (por ejemplo, calcular usando inducción una fórmula para la altura y la profundidad promedio).

Answer 3

Si usted está tratando de maximizar la altura de un árbol mientras se minimiza el promedio profundidad de todos los nodos del árbol, la mejor forma inequívoca sería un "paraguas" de forma, por ejemplo, un árbol binario completo con k nodos y altura = lg k, donde 0 < k < n, junto con una única ruta, o "cola", de nodos n-k que salen de una de las hojas de la parte completa. La altura de este árbol es aproximadamente lg k + n - k.

Ahora calculemos la profundidad total de todos los nodos. La suma de las profundidades de los nodos de la parte completa es suma [j * 2^j], donde la suma se toma de j = 0 a j = lg k. Por algún álgebra, el término dominante del resultado es 2k lg k.

A continuación, la suma de las profundidades de la parte de la cola viene dada por la suma [i + lg k], donde la suma se toma desde i = 0 hasta i = n-k. Por algún álgebra, el resultado es aproximadamente (n-k) lg k + (1/2) (n-k)^2.

Por lo tanto, sumando las dos partes juntas y dividiendo por n, la profundidad promedio de todos los nodos es (1 + k/n) lg k + (n-k)^2/(2n). Tenga en cuenta que debido a 0 < k < n, el primer término aquí es O (lg n) sin importar qué k elijamos. Por lo tanto, solo debemos asegurarnos de que el segundo término sea O (lg n). Para hacerlo, se requiere que (n-k)^2 = O (n lg n), o k = n - O (sqrt (n lg n)). Con esta elección, la altura del árbol es

lg k + n - k = O (sqrt (n lg n))

esto es asintóticamente más grande que el O ordinario (lg n), y es asintóticamente el más alto que puede hacer el árbol mientras mantiene la profundidad promedio para ser O (lg n)