Estructuras de datos 101: ¿Qué es un árbol de búsqueda binario?

Bienvenido, soy Miguel y hoy les traigo este artículo.

Diversión con Buscando a Nemo

En la vida diaria, necesitamos encontrar cosas o tomar decisiones, y una forma de hacer ese proceso más fácil es cortar esas opciones a la mitad.

Digamos que estás jugando una ronda del juego de mesa «Adivina quién», donde el objetivo del juego es adivinar el personaje que tu oponente ha seleccionado. Podrías hacerles preguntas como:

¿Es tu persona un hombre o una mujer?

Masculino. Bien, ¿tiene vello facial?

No. Ok, ¿lleva un sombrero?

Continuamos deduciendo nuestras opciones con cada paso. Después de todo, no hay necesidad de considerar a todas esas mujeres o hombres con bigote si sabes que estás buscando un hombre afeitado. De manera similar, los árboles de búsqueda binarios nos permiten encontrar lo que buscamos reduciendo nuestras opciones a cada paso.

En primer lugar, ¿Qué diablos es un árbol de búsqueda binario?

Un árbol de búsqueda binaria (BST) es un tipo especial de estructura de datos de árbol formado por nodos y sus descendientes, que también se conocen como ‘hijos’. Puedes imaginar esto como un árbol al revés o las raíces de un árbol.

Cada nodo solo puede tener un máximo 2 niños: un nodo izquierdo y un nodo derecho. El valor del nodo izquierdo siempre debe ser menor que el nodo principal, y el valor del nodo derecho siempre debe ser mayor, para que sea un árbol de búsqueda binario válido. Un BST sin espacios, donde cada nodo tiene un descendiente izquierdo y derecho, se conoce como árbol «perfecto».

En un árbol perfecto, la cantidad de nodos en cada nivel se duplica a medida que recorre el árbol. Además, puede encontrar el número total de nodos en el nivel inferior sumando todos los nodos anteriores y agregando un «1» adicional a ese número.

Cuando buscamos un elemento en un árbol de búsqueda binario balanceado, se necesita O (log n) tiempo en promedio, y en el peor de los casos, En). Puede pensar en buscar a través de un BST como un modelo de “Elija su propia aventura” comenzando en el nodo superior y continuando hacia abajo en el árbol, haciendo las mismas 2 preguntas en cada nodo al que llegue.

¿El valor que busco es menor que el nodo actual? Si es así, ve a la izquierda.

¿El valor que estoy buscando es mayor que el nodo actual? Si es así, ve a la derecha.

También son bastante rápidos para inserciones o eliminaciones, tomando O (log n) tiempo en promedio. Una desventaja es que no puede obtener acceso a elementos aleatorios como puede hacerlo con una matriz.

¿Cuándo usaría un árbol de búsqueda binario?

Digamos que le pidieron que diseñara una base de datos para una aplicación de redes sociales como Facebook. Sabe que su base de datos necesitará manejar millones de nombres de usuario y necesitará recuperar uno rápidamente durante el inicio de sesión. Dado que las personas se registran o eliminan sus cuentas todos los días, también necesitará un acceso fácil para realizar esas inserciones y eliminaciones.

Sabemos que la búsqueda binaria a través de una matriz ordenada sería bastante rápida (O (log n)), pero para insertar o eliminar un nombre de usuario, toda la matriz necesitaría reordenarse tomando O (n) tiempo que, dependiendo en el tamaño de su matriz, podría ser un poco lento. Si usáramos una BST en su lugar, este tiempo de inserción / eliminación se vuelve mucho más rápido (O (log n)).

Si tuviéramos un árbol de búsqueda binario con nombres (como en este árbol de Buscando a Nemo hábilmente diseñado que hice 😊), el árbol podría organizarse alfabéticamente.

«Dory» viene antes de «Marlin» en el alfabeto, por lo que es el nodo de la izquierda, y «Moonfish» viene después de Marlin, por lo que van a la derecha. El mismo proceso se repite a medida que nos adentramos en cada nivel. “Bruce” viene antes que “Crush” y antes que Dory y Marlin. “Darla” viene después de Crush, pero aún antes de Dory y Marlin.

¡Ahora prepárate, porque es hora de encontrar a Nemo! 🕵️‍♀️

¡Encuentra a Nemo!

Digamos que ya sabemos que tenemos un árbol de búsqueda binario válido y necesitamos encontrar a Nemo. Como sabemos que los nodos de nuestro árbol están ordenados alfabéticamente, esto debería ser bastante simple.

Partiendo de Marlin, tenemos a Dory a la izquierda y Moonfish a la derecha. Sabemos que Nemo viene después de Marlin en el alfabeto, por lo que atravesaríamos hasta el nodo derecho (Moonfish). Sabemos que Nemo viene después de Moonfish alfabéticamente, así que continuamos hasta el descendiente derecho de Moonfish. Por suerte para nosotros, eso es… ¡NEMO! ¡Encontraste a Nemo! 🥳

Bueno, eso fue eficiente. Gracias árbol de búsqueda binaria, ¡redujo toda nuestra búsqueda con complejidad de tiempo O (log n)! 👍

Ahora, ¿qué pasaría si nuestro árbol no estuviera ordenado en absoluto y fuera solo una estructura de árbol normal? O ¿qué pasa si se nos pide que validemos que tenemos un árbol de búsqueda binario? Hay 2 técnicas de búsqueda diferentes que pueden ayudar con eso.

¿Qué es la búsqueda en amplitud?

La búsqueda primero en amplitud es una forma de atravesar un árbol (o gráfico) un nivel a la vez, moviéndose a través de los nodos de izquierda a derecha.

En nuestro ejemplo de Buscando a Nemo, Marlin primero verificaría con Dory y le preguntaría «¿Sabes dónde está mi hijo, Nemo?» Si ella dice que no, él le haría la misma pregunta al pez luna. Si también dicen que no, Marlin bajaría un nivel y le preguntaría a Crush, Gill, Mr. Ray, y luego… ¡Nemo! ¡Encontró a Nemo! 🎉

Si Nemo no hubiera sido localizado después del Sr. Ray, Marlin habría continuado hasta el siguiente nivel, preguntando a Bruce, Darla, etc.

El uso de la búsqueda en amplitud le permitirá encontrar la distancia más corta posible entre el nodo inicial (Marlin) y el que está buscando (¡Nemo!). La complejidad del tiempo es O (n) porque, en el peor de los casos, necesitaría verificar cada nodo para encontrar a Nemo.

¿Qué es la búsqueda en profundidad?

La búsqueda en profundidad es una forma de atravesar un árbol (o gráfico) desde el nodo superior hasta su descendiente más lejano, y luego retroceder y probar otra ruta si no se encuentra el nodo que está buscando.

En nuestro ejemplo de Buscando a Nemo, Marlin primero verificaría con Dory, preguntando «¿Sabes dónde está Nemo?» Si ella dice que no, él le haría a Crush la misma pregunta ya que Crush desciende de Dory en el camino más a la izquierda. Si Crush también dice que no, Marlin bajaría un nivel hasta Bruce y, aunque estaba aterrorizado de convertirse en un bocadillo de tiburón 😰, le preguntaría si ha visto a su hijo.

Como Bruce dice que no, asegurándole a Marlin que “los peces son amigos, no comida”, Marlin tendría que volver sobre sus pasos hacia el árbol para encontrar el siguiente nodo que aún no ha preguntado. Volviendo a Crush, vería que debería preguntarle a Darla a continuación. Dado que todos los descendientes de Crush ahora han sido interrogados, Marlin se trasladaría a Dory, verificando a sus descendientes restantes, y así sucesivamente. En nuestro ejemplo, Marlin necesitaría verificar con cada personaje antes de finalmente encontrar a Nemo al final.

Al igual que la búsqueda en amplitud, la búsqueda en profundidad también tiene una complejidad temporal de O (n), pero la complejidad espacial puede diferir. Búsqueda en profundidad primero generalmente ocupa menos memoria o espacio, asumiendo que puede encontrar el nodo en cuestión antes de recorrer todo el árbol. Dado que cada nivel en un árbol de búsqueda binaria tiende a duplicarse (al menos para un árbol equilibrado), si su nodo faltante (Nemo) estuviera ubicado más abajo en el árbol, podría ahorrar memoria usando la búsqueda en profundidad. En el peor de los casos, la complejidad del espacio para ambos métodos será O (n).

Hay mucho más que aprender sobre los árboles de búsqueda binarios y cómo implementarlos a través del código, pero es de esperar que este sea un punto de partida útil. Si tiene alguna solicitud para revisar la próxima estructura de datos, hágamelo saber en los comentarios a continuación.

Disfruta leyendo.