¿Qué es un árbol de búsqueda binaria?

Un árbol de búsqueda binaria es una de las diversas estructuras de datos que nos ayudan a organizar y ordenar los datos. Es una forma eficiente de almacenar datos en una jerarquía y es muy flexible.

En este artículo, analizaremos más de cerca cómo funciona, junto con sus propiedades y aplicaciones.

¿Qué es un árbol de búsqueda binaria?

Un árbol de búsqueda binaria es una estructura de datos compuesta de nodos, similar a las listas enlazadas. Puede haber dos tipos de nodos: padre e hijo. El nodo raíz es el punto de inicio de la estructura que se ramifica en dos nodos secundarios, llamados nodo izquierdo y nodo derecho.

Cada nodo solo puede ser referenciado por su padre, y podemos atravesar los nodos del árbol según la dirección. El árbol de búsqueda binaria tiene tres propiedades principales:

1. El nodo izquierdo es más pequeño que su padre.
2. El nodo derecho es mayor que su padre.
3. Los subárboles izquierdo y derecho deben ser árboles de búsqueda binarios.

Se logra un árbol de búsqueda binario perfecto cuando todos los niveles están llenos y cada nodo tiene un nodo secundario izquierdo y derecho.

Relacionado: Bibliotecas de ciencia de datos para Python que todo científico de datos debería usar

Operaciones básicas de un árbol de búsqueda binario

Ahora que tiene una mejor idea de lo que es un árbol de búsqueda binaria, podemos ver sus operaciones básicas a continuación.

1. Operación de búsqueda

La búsqueda nos permite localizar un valor particular presente en el árbol. Podemos utilizar dos tipos de búsquedas: búsqueda en amplitud (BFS) y búsqueda en profundidad (DFS). La búsqueda primero en amplitud es un algoritmo de búsqueda que comienza en el nodo raíz y atraviesa horizontalmente, de lado a lado, hasta que se encuentra el objetivo. Cada nodo se visita una vez durante esta búsqueda.

La búsqueda en profundidad, por otro lado, atraviesa el árbol verticalmente, comenzando desde el nodo raíz y siguiendo una sola rama. Si se encuentra el objetivo, la operación finaliza. Pero si no, busca en los otros nodos.

2. Insertar operación

La operación de inserción utiliza la operación de búsqueda para determinar la ubicación donde se debe insertar el nuevo nodo. El proceso comienza desde el nodo raíz y la búsqueda comienza hasta que se alcanza el destino. Hay tres casos a considerar con la inserción.

• Caso 1: cuando no existe ningún nodo. El nodo que se insertará se convertirá en el nodo raíz.

• Caso 2: No hay hijos. En este caso, el nodo se comparará con el nodo raíz. Si es mayor, se convertirá en el niño adecuado; de lo contrario, se convertirá en el hijo izquierdo.

• Caso 3: Cuando la raíz y sus hijos están presentes. El nuevo nodo se comparará con cada nodo en su ruta para determinar qué nodo visita a continuación. Si el nodo es mayor que el nodo raíz, atravesará el subárbol derecho o el izquierdo. De manera similar, se hacen comparaciones en cada nivel para determinar si irá hacia la derecha o hacia la izquierda hasta llegar a su destino.

3. Eliminar operación

La operación de eliminación se utiliza para eliminar un nodo en particular dentro del árbol. La eliminación se considera complicada, ya que después de eliminar un nodo, el árbol debe reorganizarse en consecuencia. Hay tres casos principales a considerar:

• Caso 1: Eliminación de un nodo hoja. Un nodo hoja es un nodo sin hijos. Este es el más fácil de eliminar ya que no afecta a ningún otro nodo; simplemente atravesamos el árbol hasta llegar a él y lo borramos.

• Caso 2: Eliminación de un nodo con un hijo. Eliminar un padre con un nodo dará como resultado que el hijo tome su posición y todos los nodos posteriores subirán un nivel. No habrá cambios en la estructura de los subárboles.

• Caso 3: Eliminación de un nodo con dos hijos. Cuando tenemos que eliminar un nodo con dos hijos, primero debemos encontrar un nodo posterior que pueda tomar su posición. Dos nodos pueden reemplazar el nodo eliminado, el sucesor o el predecesor en orden. El sucesor en orden es el hijo más a la izquierda del subárbol derecho, y el predecesor en orden es el hijo más a la derecha del subárbol izquierdo. Copiamos el contenido del sucesor / predecesor al nodo y eliminamos el sucesor / predecesor en orden.

Relacionado: Cómo construir estructuras de datos con clases de JavaScript ES6

Cómo recorrer un árbol de búsqueda binaria

El recorrido es el proceso a través del cual navegamos por un árbol de búsqueda binaria. Se hace para ubicar un elemento específico o para imprimir un esquema del árbol. Siempre partimos del nodo raíz y tenemos que seguir los bordes para llegar a los otros nodos. Cada nodo debe considerarse un subárbol y el proceso se repite hasta que se visitan todos los nodos.

• Recorrido en orden: Atravesar en orden producirá un mapa en orden ascendente. Con este método, comenzamos desde el subárbol izquierdo y continuamos hasta el subárbol raíz y derecho.

• Recorrido por pedido anticipado: En este método, primero se visita el nodo raíz, seguido del subárbol izquierdo y el subárbol derecho.

• Recorrido posterior al pedido: Este recorrido implica visitar el nodo raíz en último lugar. Comenzamos desde el subárbol izquierdo, luego el subárbol derecho y luego el nodo raíz.

Aplicaciones del mundo real

Entonces, ¿cómo utilizamos los algoritmos de árbol de búsqueda binaria? Como se puede suponer, son extremadamente eficientes en la búsqueda y clasificación. La mayor fortaleza de los árboles binarios es su estructura organizada. Permite realizar búsquedas a velocidades notables al reducir a la mitad la cantidad de datos que necesitamos analizar por pasada.

Los árboles de búsqueda binaria nos permiten mantener de manera eficiente un conjunto de datos que cambia dinámicamente en una forma organizada. Para las aplicaciones que tienen datos insertados y eliminados con frecuencia, son muy útiles. Los motores de videojuegos utilizan un algoritmo basado en árboles conocido como partición de espacio binario para ayudar a renderizar los objetos de manera ordenada. Microsoft Excel y la mayoría de los programas de hojas de cálculo utilizan árboles binarios como estructura básica de datos.

Le sorprenderá saber que el código Morse utiliza un árbol de búsqueda binario para codificar datos. Otra razón importante por la que los árboles de búsqueda binaria son tan útiles son sus múltiples variaciones. Su flexibilidad ha llevado a la creación de numerosas variantes para resolver todo tipo de problemas. Cuando se usan correctamente, los árboles de búsqueda binaria son un gran activo.

Árboles de búsqueda binaria: el punto de partida perfecto

Una de las principales formas de medir la experiencia de un ingeniero es a través de su conocimiento y aplicación de estructuras de datos. Las estructuras de datos son útiles y pueden ayudar a crear un sistema más eficiente. Los árboles de búsqueda binaria son una excelente introducción a las estructuras de datos para cualquier desarrollador que esté comenzando.

15 métodos de matriz de JavaScript que debe dominar hoy

¿Quiere comprender las matrices de JavaScript pero no puede familiarizarse con ellas? Consulte nuestros ejemplos de matrices de JavaScript para obtener orientación.

Leer siguiente

Sobre el Autor