data-structures - programar - crear arbol binario

¿Por qué buscar en un árbol de búsqueda binario es O(log(n))? (4)

Puedo ver cómo, al buscar un valor en un BST , dejamos la mitad del árbol cada vez que comparamos un nodo con el valor que estamos buscando.

Sin embargo, no veo por qué la complejidad del tiempo es O(log(n)) . Entonces, mi pregunta es:

Si tenemos un árbol de N elementos, ¿por qué la complejidad del tiempo para buscar el árbol y verificar si existe un valor en particular es O (log (n)), cómo obtenemos eso?

Esto se puede mostrar matemáticamente muy fácilmente.

Antes de presentar eso, déjame aclarar algo. La complejidad de la búsqueda o la búsqueda en un árbol de búsqueda binaria equilibrada es O (log (n)). Para un árbol de búsqueda binario en general, es O (n). Voy a mostrar ambos a continuación.

En un árbol de búsqueda binaria equilibrada, en el peor de los casos, el valor que busco está en la hoja del árbol. Básicamente atravesaré de la raíz a la hoja, observando cada capa del árbol solo una vez, debido a la estructura ordenada de las BST. Por lo tanto, el número de búsquedas que necesito hacer es el número de capas del árbol. Por lo tanto, el problema se reduce a encontrar una expresión de forma cerrada para el número de capas de un árbol con n nodos.

Aquí es donde haremos una inducción simple. Un árbol con solo 1 capa tiene solo 1 nodo. Un árbol de 2 capas tiene 1 + 2 nodos. 3 capas 1 + 2 + 4 nodos, etc. El patrón es claro: un árbol con k capas tiene exactamente

n = 2 ^ 0 + 2 ^ 1 + ... + 2 ^ {k-1}

nodos Esta es una serie geométrica, lo que implica

n = 2 ^ k-1,

equivalentemente

k = log (n + 1)

Sabemos que big-oh está interesado en grandes valores de n, por lo tanto, las constantes son irrelevantes. De ahí la complejidad de O (log (n)).

Te daré otra forma, mucho más corta, de mostrar el mismo resultado. Ya que mientras buscamos un valor, dividimos constantemente el árbol en dos mitades, y tenemos que hacer esto k veces, donde k es el número de capas, lo siguiente es cierto:

(n + 1) / 2 ^ k = 1,

lo que implica el mismo resultado exacto. Tienes que convencerte de dónde viene ese +1 en n + 1, pero está bien incluso si no le prestas atención, ya que estamos hablando de grandes valores de n.

Ahora vamos a discutir el árbol de búsqueda binario general. En el peor de los casos, está perfectamente desequilibrado, lo que significa que todos sus nodos tienen un solo hijo (y se convierte en una lista enlazada) Ver, por ejemplo, https://www.cs.auckland.ac.nz/~jmor159/PLDS210/niemann/s_fig33.gif

En este caso, para encontrar el valor en la hoja, necesito iterar en todos los nodos, por lo tanto, O (n).

Una nota final es que estas complejidades son verdaderas no solo para las operaciones de búsqueda, sino también para insertar y eliminar.

(Editaré mis ecuaciones con un estilo matemático de látex más atractivo cuando alcance los 10 puntos de repetición. Por lo tanto, no me dejará ahora).

Para mí, la forma más sencilla era mirar una gráfica de log2 (n), donde n es el número de nodos en el árbol binario. Como tabla esto se ve así:

log2(n) = d log2(1) = 0 log2(2) = 1 log2(4) = 2 log2(8) = 3 log2(16)= 4 log2(32)= 5 log2(64)= 6

y luego dibujo un pequeño árbol binario, este va de la profundidad d = 0 a d = 3:

d=0 O / / d=1 R B // // d=2 R B R B // // // // d=3 R B RB RB R B

Entonces, a medida que el número de nodos, n, en el árbol se duplica efectivamente (por ejemplo, n aumenta en 8 a medida que va de 7 a 15 (que es casi una duplicación) cuando la profundidad d va de d = 2 a d = 3, aumentando en 1.) Por lo tanto, la cantidad adicional de procesamiento requerido (o el tiempo requerido) aumenta en solo 1 cómputo adicional (o iteración), debido a que la cantidad de procesamiento está relacionada con d.

Podemos ver que bajamos solo 1 nivel adicional de profundidad d, de d = 2 a d = 3, para encontrar el nodo que queremos de todos los nodos n, después de duplicar el número de nodos. Esto es cierto porque ahora hemos buscado en todo el árbol, bueno, la mitad de lo que necesitábamos para encontrar el nodo que queríamos.

Podemos escribir esto como d = log2(n) , donde d nos dice cuántos cálculos (cuántas iteraciones) debemos hacer (en promedio) para alcanzar cualquier nodo en el árbol, cuando hay n nodos en el árbol.

Siempre que vea un tiempo de ejecución que tenga un factor O (log n), es muy probable que esté viendo algo de la forma "siga dividiendo el tamaño de un objeto por una constante". Entonces, probablemente la mejor manera de pensar acerca de esta pregunta es que, al hacer búsquedas en un árbol de búsqueda binario, ¿qué es exactamente lo que se está reduciendo por un factor constante y qué es exactamente esa constante?

Para empezar, imaginemos que tienes un árbol binario perfectamente equilibrado, algo que se parece a esto:

* / / * * / / / / * * * * / / / / / / / / * * * * * * * *

En cada punto al hacer la búsqueda, mira el nodo actual. Si es el que estás buscando, ¡genial! Estas totalmente hecho Por otro lado, si no lo es, desciende al subárbol izquierdo o al subárbol derecho y luego repite este proceso.

Si entras en uno de los dos subárboles, esencialmente estás diciendo "No me importa en absoluto lo que hay en ese otro subárbol". Estás tirando todos los nodos en ella. ¿Y cuántos nodos hay allí? Bueno, con una rápida inspección visual, idealmente una complementada con un buen cálculo matemático, verás que estás tirando la mitad de los nodos del árbol.

Esto significa que en cada paso en una búsqueda, o bien (1) encuentra el nodo que está buscando, o (2) arroja la mitad de los nodos en el árbol. Dado que está realizando una cantidad constante de trabajo en cada paso, está observando el comportamiento distintivo del comportamiento O (log n): el trabajo cae por un factor constante en cada paso, por lo que solo puede hacerlo logarítmicamente muchos veces.

Ahora, por supuesto, no todos los árboles se ven así. Los árboles AVL tienen la propiedad divertida de que cada vez que desciendes a un subárbol, tiras aproximadamente una fracción de proporción de oro de los nodos totales. Por lo tanto, esto garantiza que solo puede tomar muchos pasos logarítmicamente antes de quedarse sin nodos, de ahí la altura O (log n). En un árbol rojo / negro, cada paso arroja (aproximadamente) una cuarta parte de los nodos totales, y como se está reduciendo por un factor constante, nuevamente obtiene el tiempo de búsqueda O (log n) que desea. El muy divertido árbol de chivo expiatorio tiene un parámetro ajustable que se usa para determinar qué tan bien equilibrado está, pero de nuevo puedes mostrar que cada paso que das elimina algún factor constante basado en este parámetro ajustable, lo que da búsquedas O (log n).

Sin embargo, este análisis se descompone para árboles desequilibrados. Si tiene un árbol puramente degenerado (uno en el que cada nodo tiene exactamente un hijo), cada paso hacia abajo en el árbol que elimine solo arroja un solo nodo, no una fracción constante. Eso significa que el tiempo de búsqueda llega a O (n) en el peor de los casos, ya que el número de veces que puede restar una constante de n es O (n).

Su pregunta parece estar bien respondida here pero para resumir en relación con su pregunta específica, sería mejor pensar en ella al revés; "¿Qué sucede con el tiempo de solución BST a medida que aumenta el número de nodos"?

Esencialmente, en una BST cada vez que duplica la cantidad de nodos, solo aumenta la cantidad de pasos a la solución en uno. Para ampliar esto, cuatro veces los nodos dan dos pasos adicionales. Ocho veces los nodos dan tres pasos extra. Dieciséis veces los nodos dan cuatro pasos extra. Y así.

El registro de la base 2 del primer número en estos pares es el segundo número en estos pares. Es el registro de la base 2 porque se trata de una búsqueda binaria (se divide a la mitad el espacio del problema en cada paso).