La respuesta correcta es que la profundidad de dicho árbol puede ser 8, 9 o 10 .
No, no son solo 8.
Es un error común pensar que la profundidad de un árbol equilibrado en los nodos [matemática] n [/ matemática] debe ser algo así como [matemática] \ lceil \ log_2 n \ rceil [/ matemática], tal vez más o menos uno.
- ¿Cuáles son algunos ejemplos de problemas que son: (1) NP pero no NP-Complete; (2) NP-Completo; (3) NP-Hard pero no NP-Complete?
- Si ASCII es binario a texto, ¿cuál es la relación entre binario a imagen?
- ¿Qué algoritmo es mejor para una variante 4 * 4 * 4 * 4 del último dedo del pie tic-tac considerando un límite de tiempo de 15 segundos?
- ¿La evolución biológica es algorítmica?
- ¿Qué significa front = rear = null y front = rear = -1 en la cola de las estructuras de datos en C ++?
La definición comúnmente utilizada de un árbol equilibrado es la siguiente:
- un nodo está equilibrado si las profundidades de su subárbol izquierdo y su subárbol derecho difieren en como máximo 1.
- un árbol está equilibrado si cada uno de sus nodos está equilibrado
(Esta es también la definición original utilizada en los árboles AVL).
Dada esta definición, es cierto que la profundidad de cualquier árbol equilibrado en los nodos [matemática] n [/ matemática] debe ser [matemática] O (\ log n) [/ matemática], pero esa es una afirmación estrictamente más débil que decir que la profundidad es [math] \ log_2 n [/ math]. De hecho, esto último no es cierto. La mayor profundidad posible de un árbol equilibrado en los nodos [matemática] n [/ matemática] es en realidad aproximadamente [matemática] \ log _ {\ Phi} n [/ matemática], donde [matemática] \ Phi [/ matemática] es la proporción áurea . Eso es aproximadamente 1,44 veces peor que el simple [math] \ log_2 n [/ math].
Por ejemplo, el árbol “mejor” equilibrado en los nodos [matemática] 2 ^ {30} -1 [/ matemática] tiene obviamente una profundidad de 30, pero hay otros árboles equilibrados con el mismo número de nodos y una profundidad diferente. El árbol más profundo en los nodos [matemática] 2 ^ {30} -1 [/ matemática] que aún está equilibrado tiene una profundidad 42.
Incluso si requerimos que el árbol esté lleno (es decir, cada nodo interno debe tener dos hijos), el cambio en el rango de profundidades posibles es insignificante.
A continuación se muestra una figura que muestra el árbol binario equilibrado completo más pequeño con profundidad 10 . Este árbol tiene solo 144 hojas (y, por lo tanto, 143 nodos internos). Este árbol obviamente puede extenderse a un árbol binario completo que todavía está equilibrado y tiene 187 hojas, mientras que todavía tiene la misma profundidad.
La figura de arriba es ancha y casi desaparece después de que Quora la encoge 🙁 haga clic en ella para ampliarla.
