Árboles Binarios de Búsqueda

3.1 Definición de un Árbol Binario de Búsqueda (BST)

Árbol Binario de Búsqueda (BST) — es un árbol binario que tiene las siguientes propiedades:

• Para cualquier nodo, su subárbol izquierdo contiene solo nodos con claves menores que la clave del nodo.
• Para cualquier nodo, su subárbol derecho contiene solo nodos con claves mayores que la clave del nodo.
• Ambos subárboles de cada nodo también son árboles binarios de búsqueda.

Ejemplo de BST:

BST es la abreviatura de Binary Search Tree – literalmente «Árbol Binario de Búsqueda». En realidad, es una organización de datos en forma de «árbol», por lo cual se puede realizar búsquedas muy rápidamente. La estructura del árbol es, de hecho, una ordenación oculta/ingeniosa de elementos.

Recorrido en orden central (in-order traversal)

La tarea del recorrido es formar una lista de nodos de una manera determinada (o de datos de nodos, cuestión de terminología y tiene significado en la práctica). El recorrido central (simétrico) es un recorrido donde la raíz del árbol ocupa un lugar entre los resultados de los correspondientes recorridos de los subárboles izquierdo y derecho.

Junto con la propiedad del árbol binario de búsqueda (que se trata de desigualdades, ver teoría), esto indica que el recorrido central de un árbol binario de búsqueda formará una lista ordenada de nodos — ¡genial! Así es como se verá el recorrido de un árbol definido anteriormente:

3.2 Principios de funcionamiento y propiedades del BST

Principios de funcionamiento:

• Organización de datos: BST organiza los datos para garantizar la búsqueda, inserción y eliminación de elementos de manera eficiente.
• Estructura recursiva: Cada nodo en el BST sigue las mismas reglas que la raíz del árbol, lo que hace que la estructura sea recursiva.
• Equilibrio: Para asegurar un rendimiento óptimo, el BST debe estar equilibrado, es decir, la altura de los subárboles izquierdo y derecho debe ser aproximadamente la misma.

Propiedades del BST:

• Orden: En cualquier momento se puede recorrer el árbol en orden "in-order" (subárbol izquierdo → nodo actual → subárbol derecho), para obtener todos los elementos en ordenado.
• Tiempo de operaciones:
  • En promedio, el tiempo de ejecución de las operaciones de búsqueda, inserción y eliminación es O(log n), donde n es el número de nodos.
  • En el peor de los casos (si el árbol no está equilibrado), el tiempo de ejecución de las operaciones puede alcanzar O(n).
• Claves únicas: Todas las claves en el BST deben ser únicas para mantener el orden.

3.3 Operaciones principales

1. Inserción (Insertion):

Principio de funcionamiento:

• Comenzamos con el nodo raíz.
• Comparamos la clave del nuevo nodo con la clave del nodo actual.
• Si la nueva clave es menor, vamos al subárbol izquierdo, si es mayor — al derecho.
• Repetimos el proceso hasta encontrar el lugar adecuado para insertar el nuevo nodo (ya sea que falte el descendiente izquierdo o el derecho).

Algoritmo:

1. Si el árbol está vacío, el nuevo nodo se convierte en el nodo raíz.
2. De lo contrario, encontramos recursivamente el lugar correcto y añadimos el nuevo nodo.

2. Eliminación (Deletion):

Principio de funcionamiento:

• Encontrar el nodo a eliminar.
• Considerar tres casos:
• El nodo es una hoja (no tiene hijos): simplemente eliminamos el nodo.
• El nodo tiene un hijo: reemplazamos el nodo por su hijo.
• El nodo tiene dos hijos: encontramos el nodo más pequeño en el subárbol derecho (o el más grande en el izquierdo), copiamos su valor en el nodo a eliminar y eliminamos recursivamente el nodo más pequeño en el subárbol derecho.

Algoritmo:

1. Encontrar el nodo con la clave dada.
2. Dependiendo del caso, realizar la eliminación y redistribución correspondientes de nodos.

3. Búsqueda (Search):

Principio de funcionamiento:

• Comenzamos con el nodo raíz.
• Comparamos la clave del nodo buscado con la clave del nodo actual.
• Si la clave coincide, devolvemos el nodo.
• Si la clave es menor, vamos al subárbol izquierdo, si es mayor — al derecho.
• Repetimos el proceso hasta encontrar el nodo con la clave buscada o llegar al final del árbol (en este caso el nodo no se encuentra).

Algoritmo:

1. Si el árbol está vacío o la clave del nodo coincide con la buscada, devolvemos el nodo.
2. Si la clave del nodo buscado es menor, buscamos recursivamente en el subárbol izquierdo.
3. Si la clave del nodo buscado es mayor, buscamos recursivamente en el subárbol derecho.

3.4 Ejemplos de problemas resueltos usando BST

1. Búsqueda de un elemento en un conjunto dinámico

Es necesario mantener un conjunto de números en el que se pueden añadir nuevos elementos, eliminar existentes y buscar rápidamente si un número dado está en el conjunto.

Solución usando BST:

• Insertar nuevos elementos en el árbol.
• Eliminar elementos existentes.
• Buscar elementos en el árbol.

Ejemplo de uso:

Soporte de una lista de usuarios registrados en un sistema, donde los usuarios pueden ser añadidos y eliminados, y el sistema debe comprobar rápidamente si un usuario está registrado.

2. Encontrar el elemento mínimo y máximo

Es necesario encontrar rápidamente los valores mínimo y máximo en un conjunto de datos.

Solución usando BST:

• El elemento mínimo se encuentra en el nodo más a la izquierda del árbol.
• El elemento máximo se encuentra en el nodo más a la derecha del árbol.

Ejemplo de uso:

Soporte de un sistema que rastrea los precios de acciones, donde es necesario encontrar rápidamente el precio mínimo y máximo en el momento actual.

3. Comprobación del balance de una expresión

Se da una expresión matemática, se necesita comprobar su equilibrio en términos de la cantidad de paréntesis de apertura y cierre.

Solución usando BST:

Usamos BST para almacenar estados intermedios de verificación del equilibrio de paréntesis.

Ejemplo de uso:

Análisis y compilación de código, donde es necesario comprobar la correcta colocación de paréntesis en las expresiones.

4. Construcción de un diccionario

Es necesario crear una estructura de datos para almacenar un diccionario, en el cual se puedan añadir palabras, eliminarlas y encontrarlas rápidamente.

Solución usando BST:

• Las palabras se añaden al árbol en orden alfabético.
• La búsqueda de palabras se realiza mediante las claves.

Ejemplo de uso:

Un sistema de autocorrección de texto, donde se necesita encontrar y corregir rápidamente las palabras.