¿Por qué la búsqueda es más rápida para un árbol binario que una lista vinculada?

Lista enlazada:

1. Artículo (1) -> Artículo (2) -> Artículo (3) -> Artículo (4)

Árbol binario:

Nodo (1)
/ /
Nodo (2)
/ \
/ Nodo (3)
Nodo raíz (4)
\ Nodo (5)
\ /
Nodo (6)
\
Nodo (7)

En una lista vinculada, los elementos se vinculan entre sí a través de un único puntero siguiente. En un árbol binario, cada nodo puede tener 0, 1 o 2 subnodos, donde (en el caso de un árbol de búsqueda binario) la clave del nodo izquierdo es menor que la clave del nodo y la clave del nodo derecho es más que el nodo Mientras el árbol esté equilibrado, la ruta de búsqueda a cada elemento es mucho más corta que la de una lista vinculada.

Rutas de búsqueda:

—— —— ——
Árbol de lista clave
—— —— ——
1 1 3
2 2 2
3 3 3
4 4 1
5 5 3
6 6 2
7 7 3
—— —— ——
promedio 4 2.43
—— —— ——

Por estructuras más grandes, la ruta de búsqueda promedio se vuelve significativamente más pequeña:

—— —— ——
árbol de lista de artículos
—— —— ——
1 1 1
3 2 1.67
7 4 2,43
15 8 3.29
31 16 4.16
63 32 5.09
—— —— ——

Las otras respuestas son geniales, pero puede que no atraigan de inmediato a su intuición.

En un árbol binario, cada vez que decide tomar una de las dos ‘siguientes’ ramas, ha eliminado la mitad del árbol en ese nivel. Un nodo que no tiene que buscarse en absoluto no agregará tiempo a su búsqueda.

Por supuesto, los datos tienen que estructurarse de una manera sensata, por lo que está utilizando un árbol binario en primer lugar.

Imagina que tienes una lista de palabras y quieres saber si una palabra determinada está en la lista o no.

En una lista vinculada, miraría cada entrada una tras otra. Una vez que encuentre la palabra, puede detenerse. Pero si la palabra no está en la lista, tendrías que mirar cada elemento y aún así aparecer con las manos vacías.

Si las palabras se organizan en un árbol binario basado en el alfabeto, las cosas son mucho mejores. En el nivel superior, tenemos una división bidireccional. Todas las palabras que comienzan con al están en una rama, las palabras que comienzan con mz están en la otra. Si estamos probando una palabra que comienza con ‘g’, por ejemplo, sabemos que ni siquiera necesitamos mirar la segunda rama. Hemos reducido el número de entradas a buscar a la mitad.

El siguiente nivel repite el proceso para la segunda letra (eliminando un cuarto más), el tercer nivel para la tercera letra (eliminando otro octavo) y así sucesivamente. Bastante rápido podemos determinar si nuestra palabra está en el árbol o no, y solo hemos buscado una rama. (Tenga en cuenta que este es un ejemplo artificial: los árboles binarios no suelen utilizarse para listas de palabras por otros motivos).

Para obtener una lista vinculada con elementos [math] n [/ math], debe escanear entre 1 y [math] n [/ math] elementos ([math] \ frac {n + 1} {2} [/ math] en promedio ) antes de encontrar un elemento. Por lo tanto, una búsqueda tiene complejidad temporal [matemática] O (n) [/ matemática].

En un árbol binario adecuadamente equilibrado con nodos de hoja [matemática] n [/ matemática], elimina aproximadamente la mitad de los nodos de hoja potenciales cada vez que pasa de un nodo a su nodo secundario izquierdo o derecho. Esto significa que el número de pasos es logarítmico en el número de nodos. Por lo tanto, una búsqueda tiene complejidad de tiempo [matemática] O (\ log n) [/ matemática].

Por supuesto, el árbol binario debe estructurarse de manera adecuada. Los nodos no hoja de un árbol binario son para la toma de decisiones a dónde ir a continuación. Si desea buscar por nombre, pero el árbol binario no está preparado para la búsqueda de nombres (pero digamos para la búsqueda de marcas de tiempo de creación), el árbol binario es bastante inútil.

Las listas vinculadas (o matrices), por otro lado, son genéricas, porque no se necesita dicha estructura específica de atributo.

El tiempo de búsqueda es solo una parte de la historia, a menos que su aplicación use los datos solo de lectura. Tan pronto como las manipulaciones de datos (actualizaciones, eliminaciones, adiciones) entran en juego, las cosas se vuelven más complicadas y requieren más tiempo cuando se usan árboles binarios. Eliminar / actualizar / insertar un elemento en una lista vinculada lleva un tiempo constante ([math] O (1) [/ math]), mientras que estas operaciones toman [math] O (\ log n) [/ math] cuando un árbol binario es usado.

Un árbol binario no es más rápido que una lista vinculada a menos que se ordene el árbol binario. Un árbol binario es simplemente un árbol donde cada nodo tiene como máximo dos hijos.

Un árbol de búsqueda binaria es un árbol binario optimizado para buscar donde se ordenan todos los elementos de tal manera que satisfaga una relación transitiva entre ellos, es decir, si sé [matemática] t_1 [/ matemática] es menor que [matemática] t_2 [/ matemática] y [matemática] t_2 [/ matemática] es menor que [matemática] t_3 [/ matemática] , entonces no necesito comparar [matemáticas] t_1 [/ matemáticas] a [matemáticas] t_3 [/ matemáticas] saber que [math] t_1 [/ math] es menor que [math] t_3 [/ math] .

Esta relación transitiva es lo que hace que los árboles de búsqueda binarios sean más rápidos para buscar que las listas vinculadas. De hecho, es tan rápido que para encontrar cualquier cosa en un árbol de elementos de 1M, solo tiene que hacer un máximo de 20 búsquedas, en comparación con 1M para una lista vinculada.

La respuesta rápida es, en cada paso, el árbol binario reduce a la mitad el espacio de búsqueda (“pila” izquierda o “pila” derecha), mientras que la lista vinculada solo lo reduce en 1 (no esta, intente la siguiente).