Aplicaciones, ventajas y desventajas del árbol de búsqueda binario

Binary Search Tree (BST) es un árbol binario especial que tiene las siguientes propiedades:

•  El subárbol izquierdo contiene solo las claves que son menores que la clave del Node.
•  El subárbol derecho contiene solo las claves que son mayores que la clave del Node.
• El subárbol izquierdo y derecho debe ser un árbol de búsqueda binaria.

Operaciones en el árbol de búsqueda binaria:

Las cuatro operaciones básicas de BST:

1. Buscando, 
2. Inserción, y 
3. Supresión
4. travesías

1. Buscando en un BST:

La búsqueda en BST implica la comparación de los valores clave. Si el valor de la clave es igual a la clave raíz, entonces, busque con éxito, si es menor que la clave raíz, busque la clave en el subárbol izquierdo y si la clave es mayor que la clave raíz, busque la clave en el subárbol derecho.

Buscando en el algoritmo BST: –

• Compruebe si el árbol es NULL, si el árbol no es NULL, siga los siguientes pasos.
• Compare la clave a buscar con la raíz de la BST.
• Si la clave es menor que la raíz, busque en el subárbol izquierdo.
• Si la clave es mayor que la raíz, busque en el subárbol derecho.
• Si la clave es igual a la raíz, regrese e imprima la búsqueda exitosa.
• Repita los pasos 3, 4 o 5 para el subárbol obtenido.

2. Inserción en un BST:

La inserción en BST implica la comparación de los valores clave. Si el valor de la clave es menor o igual que la clave raíz, vaya al subárbol izquierdo, busque un espacio vacío siguiendo el algoritmo de búsqueda e inserte los datos y si la clave es mayor que la clave raíz, vaya al subárbol derecho, busque un espacio vacío siguiendo el algoritmo de búsqueda e inserte los datos.

3. Eliminación en un BST:

La eliminación en BST implica tres casos: –

Primero, busque la clave que se eliminará utilizando el algoritmo de búsqueda y encuentre el Node. Luego, busque el número de elementos secundarios del Node que desea eliminar.  

• Caso 1: si el Node que se eliminará es un Node hoja: si el Node que se eliminará es un Node hoja, elimínelo.
• Caso 2: si el Node que se eliminará tiene un hijo: si el Node que se eliminará tiene un hijo, elimine el Node y coloque el hijo del Node en la posición del Node eliminado.
• Caso 3: si el Node que se eliminará tiene dos hijos: si el Node que se eliminará tiene dos hijos, busque el sucesor en orden o el predecesor en orden del Node de acuerdo con el valor capaz más cercano del Node que se eliminará. Elimine el sucesor o predecesor en orden utilizando los casos anteriores. Reemplace el Node con el sucesor o predecesor en orden. 

4. Recorridos en un BST:

Hay 4 tipos de recorridos del árbol de búsqueda binaria.

Recorrido por orden de niveles: cada Node del árbol se recorre nivel por nivel en el orden de su aparición.

Recorrido de pedido anticipado: los Nodes se recorren en el formato raíz y luego en el subárbol izquierdo y luego en el subárbol derecho.

Recorrido en orden: los Nodes se recorren en el formato de subárbol izquierdo y luego raíz y luego subárbol derecho.

Post Traversal: los Nodes se recorren en el formato de subárbol izquierdo y luego subárbol derecho y luego raíz

Aplicaciones del árbol de búsqueda binaria:

• Los BST se utilizan para la indexación.
• También se utiliza para implementar varios algoritmos de búsqueda.
• La TI se puede utilizar para implementar varias estructuras de datos.

Aplicación en tiempo real del árbol de búsqueda binaria:

• Los BST se utilizan para la indexación en bases de datos.
• Se utiliza para implementar algoritmos de búsqueda.
• Los BST se utilizan para implementar el algoritmo de codificación de Huffman.
• También se utiliza para implementar diccionarios.

Ventajas del árbol de búsqueda binaria:

• BST es rápido en inserción y eliminación cuando está balanceado.
• BST es eficiente.
• También podemos hacer consultas de rango: encontrar claves entre N y M (N <= M).
• El código BST es simple en comparación con otras estructuras de datos.

Desventajas del árbol de búsqueda binario:

• La principal desventaja es que siempre debemos implementar un árbol de búsqueda binario balanceado. De lo contrario, el costo de las operaciones puede no ser logarítmico y degenerar en una búsqueda lineal en una array.
• Acceder al elemento en BST es un poco más lento que en array.
• Un BST puede estar desequilibrado o degenerado, lo que puede aumentar la complejidad.