Estructuras de datos | Árboles binarios | Pregunta 9

Un árbol de peso equilibrado es un árbol binario en el que para cada Node. El número de Nodes en el subárbol izquierdo es al menos la mitad y como máximo el doble del número de Nodes en el subárbol derecho. ¿Cuál de las siguientes describe mejor la altura máxima posible (número de Nodes en el camino desde la raíz hasta la hoja más lejana) de tal árbol en n Nodes?
a) $\log_2 n$
b) $\log_{4/3} n$
c) $\log_3 n$
d) $\log_{3/2} n$
(A) A
(B) B
(C) C
(D) D

Respuesta: (D)
Explicación: Sea H(n) la altura máxima posible de un árbol con n Nodes.

El valor máximo posible de H(n) se puede escribir aproximadamente usando la siguiente recursión

   H(n) = H(2n/3) + 1

La solución de la recurrencia anterior es $\log_{3/2} n$ . Simplemente podemos obtenerlo dibujando un árbol de recurrencia.

4. Considere el siguiente algoritmo para buscar un número dado x en una array sin clasificar A[1..n] que tiene n valores distintos:

1)    Choose an i uniformly at random from 1..n; 
2)    If A[i] = x then Stop else Goto 1;

Suponiendo que x está presente en A, ¿cuál es el número esperado de comparaciones realizadas por el algoritmo antes de que termine?
a) n
b) nl
c) 2n
d) n/2

Respuesta (a)

Si recuerdas las preguntas sobre monedas y dados, puedes adivinar la respuesta a las anteriores.

A continuación se muestra la prueba de la respuesta.

Sea E el número esperado de comparaciones. El valor de E es la suma de la siguiente expresión para todos los casos posibles.

number_of_comparisons_for_a_case * probability_for_the_case

Caso 1

  If A[i] is found in the first attempt 
  number of comparisons = 1
  probability of the case  = 1/n

Caso 2

  If A[i] is found in the second attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*1/n

Caso 3

  If A[i] is found in the third attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*(n-1)/n*1/n

En realidad, hay infinitos casos de este tipo. Entonces, tenemos las siguientes series infinitas para E.

E  = 1/n + [(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[1/n]*3 + ….  (1)

Después de multiplicar la ecuación (1) por (n-1)/n, obtenemos

E (n-1)/n = [(n-1)/n]*[1/n] + [(n-1)/n]*[(n-1)/n]*[1/n]*2 + 
                                 [(n-1)/n]*[(n-1)/n]*[(n-1)/n]*[1/n]*3 ……….(2)

Restando (2) de (1), obtenemos

E/n = 1/n + (n-1)/n*1/n + (n-1)/n*(n-1)/n*1/n + …………

La expresión del lado derecho es un GP con infinitos elementos. Apliquemos la fórmula de la suma (a/(1-r))

  E/n = [1/n]/[1-(n-1)/n]  = 1
  E = n

Cuestionario de esta pregunta

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta