Profundidad-Primero vs Breadth-First Búsqueda

Si se ha tomado el tiempo de estudiar el código en cualquier forma o forma, probablemente haya encontrado estructuras de datos. Las estructuras de datos se componen de una gran cantidad de posibilidades para almacenar, organizar y manipular datos. Algunos de los más populares incluyen matrices, listas vinculadas, pilas, colas y árboles de búsqueda binarios. Por el bien de este artículo, nos centraremos en dos formas diferentes de abordar el recorrido del árbol: Búsqueda de profundidad primero y Búsqueda de amplitud primero.

¿Qué es un árbol?

Un árbol es una estructura de datos compuesta de nodos, que contienen punteros a otros nodos. A diferencia de los árboles en la vida real (o tal vez existen en algún lugar), un árbol de datos está al revés. Esencialmente, la raíz está en la parte superior y las hojas están en la parte inferior.

Analicemos el diagrama.

Cada árbol tiene un solo nodo raíz que se encuentra en el nivel superior (en este caso, nivel 0). Luego vemos que en el siguiente nivel, el nodo raíz A tiene punteros a los nodos B y C. Asimismo, los nodos B y C tienen punteros al nodo A. En esta situación, el nodo A es el nodo padre, y los nodos B y C son sus hijos Además, los nodos B y C se consideran hermanos.

Tal vez se pregunte si es posible que un nodo tenga más de 2 hijos. ¡La respuesta es sí! Esta representación específica es de un árbol binario que puede determinarse por un máximo de dos nodos secundarios para cada padre.

Código de árbol

Descargo de responsabilidad: ¡usaré Javascript para crear un árbol simple!

En primer lugar, necesitamos crear una clase de nodo:

Cuando creamos una clase de nodo, le pasamos un valor, o datos, que se convierte en la propiedad de datos del nodo. También tenemos propiedades primarias y secundarias que son nulas y una matriz vacía, respectivamente, por ahora. Eventualmente, la propiedad padre apuntará al padre del nodo específico y la propiedad hijos apuntará a los hijos del nodo.

Luego, creamos la clase de árbol:

La clase de árbol contiene una sola propiedad, root, que inicialmente es nula. Los árboles incluyen métodos prototipo tales como contiene (), insertar () y eliminar (), ¡pero los guardaremos para un día lluvioso!

¡Buscando!

Tanto las búsquedas de profundidad como de amplitud son métodos prototipo de la clase Tree que se utilizan para determinar si un nodo particular que contiene datos específicos existe dentro de un árbol. La siguiente imagen muestra los dos procedimientos de búsqueda diferentes.

Profundidad: primer enfoque

El método de profundidad primero comienza en el nodo raíz y se mueve hacia el nodo más a la izquierda. Una vez que alcanza el nodo más a la izquierda, atraviesa el árbol de regreso a la raíz y luego al nodo más a la derecha. Si golpea un nodo con hijos, atravesará los hijos de ese nodo de izquierda a derecha y luego continuará hacia la derecha.

Orden de búsqueda: [10, 4, 1, 9, 17, 12, 18]

Código

La búsqueda de profundidad primero toma un valor como argumento, que es el valor que estamos buscando en el árbol. Dado que queremos atravesar los nodos de izquierda a derecha, configuramos la raíz como una pila porque queremos tomar un enfoque de último en entrar, primero en salir. Luego realizamos un ciclo while que continúa mientras la pila contenga elementos. Dentro del ciclo while, eliminamos el primer elemento en la pila, o llamamos al método de matriz shift (), y lo establecemos igual a un nodo. Comparamos los datos de ese nodo con el valor del argumento y, si coinciden, la función devuelve verdadero. Si este no es el caso, agrega los elementos secundarios del nodo al frente de la pila o llama al método de matriz unshift () y continúa buscando a través de los nuevos datos. Si el valor particular no existe en el árbol, la función devuelve falso.

Enfoque de amplitud primero

El enfoque de amplitud inicial comienza en el nodo raíz y atraviesa cada nivel sucesivo para buscar el nodo deseado. De manera similar al enfoque de profundidad primero, los nodos se leen de izquierda a derecha en cada nivel.

Orden de búsqueda: [10, 4, 17, 1, 9, 12, 18]

Código

La búsqueda de amplitud es similar en código a la búsqueda de profundidad. Se necesita un valor para encontrarlo como argumento. La diferencia aquí es que, en lugar de utilizar una pila, queremos utilizar una cola para poder tomar un enfoque de primero en entrar, primero en salir. En el bucle while, de manera similar a la búsqueda de profundidad primero, queremos usar el método de matriz shift () para eliminar el primer elemento de la cola como un nodo. Sin embargo, si los datos del nodo no son los mismos que el valor deseado, en lugar de deshabilitar los elementos secundarios del nodo, utilizaremos el método de matriz push () para agregar los elementos secundarios al final de la cola. Esto nos permite verificar cada nodo en un nivel antes de atravesar los nodos en el siguiente nivel. Finalmente, al igual que la búsqueda de profundidad primero, si no se encuentra el valor, la función devolverá falso.

¿Cuál uso?

Aunque tanto las búsquedas de profundidad primero (DFS) como de amplitud (BFS) son enfoques legítimos y pueden llegar a las mismas conclusiones, cada una se ve favorecida bajo ciertas circunstancias. Sin embargo, a menudo no es obvio cuál es el más eficiente de los dos.

Descargo de responsabilidad: ¡Estas son pautas generales! Definitivamente no siempre son los enfoques más óptimos.

DFS: Generalmente se prefiere cuando el árbol es muy profundo y los valores o datos deseados ocurren con poca frecuencia.

BFS: generalmente preferido en árboles poco profundos que no son demasiado anchos. También se usa si se sabe que el nodo deseado está más cerca del nivel raíz.

Aunque existen preferencias generales al decidir qué método utilizar, si no está seguro, probablemente sea mejor probar ambos métodos y ver cuál es más eficiente.

Por ejemplo, supongamos que está utilizando el árbol de arriba y está buscando el nodo que contiene 8. El árbol no es tan profundo, por lo que podría pensar que sería mejor utilizar un BFS. Sin embargo, en realidad sería más eficiente usar un DFS.

Comparemos los dos métodos y qué nodos se han recorrido:

DFS: 1, 2, 4, 8

BFS: 1, 2, 3, 4, 5, 6, 7, 8

Ya podemos ver que una búsqueda amplia atraviesa más nodos y, por lo tanto, necesita acceso a más memoria.

Además, una vez que ubiquemos el nodo 8, la pila DFS sería [8, 9, 5, 3] mientras que la cola BFS sería [8, 9, 10, 11, 13, 14]. La cola BFS contiene 2 nodos más, lo que no parece ser mucho en este ejemplo, pero en términos de memoria, todavía usa una cantidad mayor. Por lo tanto, en esta situación particular, un DFS sería más eficiente que un BFS.

Aunque este ejemplo es simple y directo, en situaciones donde los árboles son más profundos y anchos, definitivamente es mucho más difícil determinar cuál es el más óptimo. La mejor manera de dictar el mejor método es intentar ambos.

Complejidad

La complejidad de tiempo y espacio tanto para DFS como para BFS es bastante sencilla. Como estamos hablando del recorrido del árbol, para determinar si existe un valor o datos dentro del árbol, debemos visitar cada nodo. Visitar cada nodo una sola vez significa que la complejidad del tiempo tanto para DFS como para BFS es O (n) o lineal. Si pensamos en los árboles como matrices ordenadas, solo tendríamos que recorrerlo una sola vez para determinar si un valor coincide o no con el valor que estamos buscando. Del mismo modo, en términos de complejidad espacial, DFS es O (h) y BFS es O (w). Para DFS, "h" significa altura, ya que la cantidad de espacio que ocupará la función depende de cuántos nodos tenga el árbol. Del mismo modo, para BFS, "w" significa ancho, ya que el espacio depende de qué tan ancho sea el árbol. Por supuesto, estas grandes notaciones de O cambian según la estructura de datos, pero por el bien de los árboles, las complejidades de tiempo y espacio serán las mismas.

¡Gracias por tomarse el tiempo de leer este artículo! Si tiene algún comentario o pregunta, ¡hágamelo saber! ¡Espero que tengas un gran día!