Árbol de búsqueda binaria (BST) con ejemplo

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

El árbol de búsqueda binaria (BST) es un algoritmo avanzado que se utiliza para analizar un nodo, sus ramas izquierda y derecha (modeladas en una estructura de árbol) y devolver su valor. El BST se basa en la arquitectura de un algoritmo de búsqueda binaria básico, lo que permite búsquedas, inserciones y eliminaciones de nodos más rápidas. Esto hace que el programa sea realmente rápido y preciso.

Atributos del árbol de búsqueda binaria

Una BST está formada por múltiples nodos y consta de los siguientes atributos:

• Los nodos del árbol están representados en una relación padre-hijo.
• Cada nodo principal puede tener cero nodos secundarios o un máximo de dos subnodos o subárboles en los lados izquierdo y derecho.
• Cada subárbol, también conocido como árbol de búsqueda binaria, tiene subramas a la derecha e izquierda de sí mismo.
• Todos los nodos están vinculados con pares clave-valor.
• Las claves de los nodos presentes en el subárbol izquierdo son más pequeñas que las claves de su nodo padre.
• De manera similar, las claves de los nodos presentes en el subárbol derecho son mayores que las claves de su nodo padre.

1. Existe un nodo principal o nivel padre, el nivel 11. Debajo de él, hay nodos/ramas izquierda y derecha con sus propios valores clave.
2. El subárbol derecho tiene valores clave mayores que el nodo padre.
3. El subárbol izquierdo tiene valores clave menores que el nodo padre.

¿Por qué necesitamos un árbol de búsqueda binaria?

• Los dos factores principales que hacen de un árbol de búsqueda binaria una solución óptima para cualquier problema del mundo real son la velocidad y la precisión.
• Debido al hecho de que la búsqueda binaria se realiza en un formato similar a una rama con relaciones padre-hijo, el algoritmo sabe en qué ubicación del árbol se deben buscar los elementos. Esto reduce la cantidad de comparaciones clave-valor que el programa debe realizar para ubicar el elemento deseado.
• Además, si el elemento que se busca es mayor o menor que el nodo padre, el nodo sabe en qué lado del árbol debe buscar. Esto se debe a que el subárbol izquierdo siempre es menor que el nodo padre, y el subárbol derecho siempre tiene valores iguales o mayores que el nodo padre.
• BST se utiliza comúnmente para implementar búsquedas complejas, lógicas de juego robustas, actividades de autocompletar y gráficos.
• El algoritmo admite de manera eficiente operaciones como buscar, insertar y eliminar.

Tipos de árboles binarios

Tres tipos de árboles binarios son:

• Árbol binario completo: Todos los niveles del árbol están completos, con una posible excepción en el último nivel. Del mismo modo, todos los nodos están completos y apuntan hacia la izquierda.
• Árbol binario completo: Todos los nodos tienen 2 nodos hijos, excepto la hoja.
• Árbol binario equilibrado o perfecto: En el árbol, todos los nodos tienen dos hijos. Además, cada subnodo tiene el mismo nivel.

Aprenda más sobre la Árbol binario en estructura de datos si están interesados.

¿Cómo funciona el árbol de búsqueda binaria?

El árbol siempre tiene un nodo raíz y más nodos secundarios, ya sea a la izquierda o a la derecha. El algoritmo realiza todas las operaciones comparando valores con la raíz y sus nodos secundarios adicionales en el subárbol izquierdo o derecho, según corresponda.

Dependiendo del elemento que se vaya a insertar, buscar o eliminar, después de la comparación, el algoritmo puede descartar fácilmente el subárbol izquierdo o derecho del nodo raíz.

BST ofrece principalmente los siguientes tres tipos de operaciones para su uso:

• Buscar: busca el elemento en el árbol binario.
• Insertar: agrega un elemento al árbol binario.
• Borrar: elimina el elemento de un árbol binario.

Cada operación tiene su propia estructura y método de ejecución/análisis, pero la más compleja de todas es la operación Eliminar.

Buscar Operadisrupción

Siempre inicie el análisis del árbol en el nodo raíz y luego avance hacia el subárbol derecho o izquierdo del nodo raíz, dependiendo de si el elemento que se va a localizar es menor o mayor que la raíz.

1. El elemento que se va a buscar es 10.
2. Compara el elemento con el nodo raíz 12, 10 < 12, por lo tanto, pasa al subárbol izquierdo. No es necesario analizar el subárbol derecho.
3. Ahora comparamos 10 con el nodo 7, 10 > 7, así que pasamos al subárbol de la derecha.
4. Luego compara 10 con el siguiente nodo, que es 9, 10 > 9, mira en el hijo del subárbol derecho.
5. 10 coincide con el valor en el nodo, 10 = 10, devuelve el valor al usuario.

Apodo Code para búsqueda en BST

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

recuadro Operadisrupción

Esta es una operación muy sencilla. Primero, se inserta el nodo raíz; luego, el siguiente valor se compara con el nodo raíz. Si el valor es mayor que el de la raíz, se agrega al subárbol derecho; si es menor, se agrega al subárbol izquierdo.

1. Hay una lista de 6 elementos que deben insertarse en un BST en orden de izquierda a derecha.
2. Inserta 12 como nodo raíz y compara los siguientes valores 7 y 9 para insertarlos respectivamente en el subárbol derecho e izquierdo.
3. Compara los valores restantes 19, 5 y 10 con el nodo raíz 12 y colócalos en consecuencia. 19 > 12, colócalo como hijo derecho de 12; 5 < 12 y 5 < 7, por lo tanto, colócalo como hijo izquierdo de 7. Ahora compara 10, 10 es < 12 y 10 es > 7 y 10 es > 9, coloca 10 como subárbol derecho de 9.

Pseudocódigo para insertar un nodo en BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

Eliminar OperaSupuestos de Alcance

Para eliminar un nodo de un árbol binario de búsqueda (BST), existen diferentes casos, como eliminar un nodo raíz o un nodo hoja. Además, después de eliminar un nodo raíz, debemos considerar qué sucede con dicho nodo.

Digamos que queremos eliminar un nodo de hoja, podemos simplemente eliminarlo, pero si queremos eliminar una raíz, necesitamos reemplazar el valor de la raíz con otro nodo. Tomemos el siguiente ejemplo:

• Caso 1 – Nodo con cero hijos: Esta es la situación más sencilla: solo tienes que eliminar el nodo que no tenga más hijos a la derecha o a la izquierda.
• Caso 2 – Nodo con un hijo: Una vez que elimine el nodo, simplemente conecte su nodo hijo con el nodo padre del valor eliminado.
• Caso 3 – Nodo con dos hijos: Esta es la situación más difícil, y funciona según las dos reglas siguientes:
  • 3a – Predecesor en orden: Debes eliminar el nodo con dos hijos y reemplazarlo con el valor más grande en el subárbol izquierdo del nodo eliminado.
  • 3b – Sucesor en orden: Debes eliminar el nodo con dos hijos y reemplazarlo con el valor más pequeño en el subárbol derecho del nodo eliminado.

1. Este es el primer caso de eliminación, en el que se borra un nodo que no tiene hijos. Como se puede observar en el diagrama, los nodos 19, 10 y 5 no tienen hijos. Pero eliminaremos el nodo 19.
2. Elimine el valor 19 y elimine el enlace del nodo.
3. Vea la nueva estructura del BST sin 19.

1. Este es el segundo caso de eliminación, en el que se elimina un nodo que tiene 1 hijo. Como se puede ver en el diagrama, el nodo 9 tiene un hijo.
2. Elimina el nodo 9 y reemplázalo con su hijo 10, y agrega un enlace del 7 al 10.
3. Vea la nueva estructura del BST sin 9.

1. Aquí eliminarás el nodo 12, que tiene dos hijos.
2. La eliminación del nodo se producirá según la regla de predecesor en orden, lo que significa que el elemento más grande del subárbol izquierdo de 12 lo reemplazará.
3. Elimina el nodo 12 y reemplázalo por el 10, ya que es el valor más grande en el subárbol izquierdo.
4. Vea la nueva estructura del BST después de eliminar 12.

1. Eliminar el nodo 12 que tiene dos hijos.
2. La eliminación del nodo se producirá según la regla de sucesor en orden, lo que significa que el elemento más pequeño del subárbol derecho de 12 lo reemplazará.
3. Elimina el nodo 12 y reemplázalo por el 19, ya que es el valor más pequeño en el subárbol derecho.
4. Vea la nueva estructura del BST después de eliminar 12.

Apodo Code Para eliminar un nodo

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Términos Importantes

• Insertar: Inserta un elemento en un árbol / crea un árbol.
• Buscar: Busca un elemento en un árbol.
• Recorrido de preorden: Recorre un árbol siguiendo un orden predeterminado.
• Recorrido en orden: Recorre un árbol de forma ordenada.
• Recorrido en postorden: Recorre un árbol en orden inverso.

Preguntas Frecuentes