Te sugerimos que pruebes esta solución en un entorno controlado antes de enviarlo a producción, un saludo.
Solución:
Si encontramos un nodo desequilibrado, obtenemos un retorno anticipado de false así que este es el caso óptimo. El “peor de los casos” para que este algoritmo maneje es un árbol completamente balanceado, ya que no obtenemos retornos tempranos de false. Por el bien de este ejemplo, usemos un árbol binario perfecto con n nodos.
La primera llamada activaría getHeight() en cada nodo para que se visiten ~n nodos. El trabajo total para el nivel raíz es O(n).
Las siguientes dos llamadas (root.left.isBalanced() y root.right.isBalanced()) activarían getHeight() en los nodos subsiguientes, pero cada una solo lo llama en ~1/2 n nodos. El trabajo total para 1 altura también es O(n).
Las próximas 4 llamadas llamarían a getHeight en n/4 nodos cada una. Así que el trabajo total para 2 alturas también es O(n).
Si ve el patrón, el trabajo total para cada nivel del árbol es O(n), por lo que el trabajo total para todos los niveles es O(n) * niveles en un árbol perfecto, que resulta en O(nlogn).
El getHeight definitivamente tiene una complejidad lineal. Simplemente visita cada elemento en el subárbol, por lo que es O(k) dónde k es el número de nodos en el subárbol.
Ahora con respecto a isBalanced. Primero calcula la altura (que es lineal como hemos visto antes). Pero entonces, si no tenemos tanta suerte, tenemos que calcular isBalanced 2 veces más: para los subárboles izquierdo y derecho. En el peor de los casos, realizaremos el cálculo lineal para log N veces.
Puedes estudiar el Teorema del Maestro que describe casos más genéricos.
En este caso particular los parámetros para el teorema son: a = b = 2 y hay una sobrecarga constante al dividir el problema en subproblemas.
La complejidad del peor de los casos de este algoritmo ocurre en el caso del árbol de búsqueda binario equilibrado, ya que de lo contrario regresamos temprano. Considere el siguiente árbol de búsqueda binario balanceado
isBalanced La función pasa por todos los nodos una vez (incluido el null hijos de nodos hoja). Para cada uno de estos nodos llama getHeight para calcular la altura del niño izquierdo y derecho. Asi que getHeight requiere un trabajo proporcional al tamaño del subárbol enraizado en ese nodo.Para null hijos de hojas (hay
16 tales nodos) requiere una cantidad constante de trabajo. Para los nudos de hoja (1, 3, 5, 7...) necesitamos el doble de trabajo pero nuestro nodo se reduce a la mitad (es decir, tenemos 8 nodos). Un nivel por encima necesitamos cuatro veces el trabajo, pero nuestro nodo se reduce a la mitad nuevamente.En general si tenemos
N nodos, por lo que la cantidad total de trabajo es aproximadamente
N + N/2*2 + N/4*4 + ... + N/N * 1
Todo término de la suma es igual a N. ¿Cuántos términos hay? Esa es solo la altura del árbol, es decir lg(N) ya que reducimos N por 2 hasta que alcanza 1. Entonces la complejidad total es O(N*lg(N))
Si aceptas, tienes el poder dejar una crónica acerca de qué te ha impresionado de esta crónica.