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

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 del subárbol izquierdo tienen valores menores que las claves de sus nodos principales.

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

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

• Los dos factores principales que hacen del á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, en caso de que el elemento a buscar sea mayor o menor que el nodo principal, el nodo sabe qué lado del árbol buscar. La razón es que el subárbol izquierdo siempre es menor que el nodo principal y el subárbol derecho siempre tiene valores iguales o mayores que el nodo principal.
• 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 de los árboles están llenos de posibles excepciones del último nivel. Del mismo modo, todos los nodos están llenos, dirigiéndose hacia el extremo izquierdo.
• Árbol binario completo: todos los nodos tienen 2 nodos secundarios excepto la hoja.
• Árbol binario equilibrado o perfecto: en el árbol, todos los nodos tienen dos hijos. Además, existe el mismo nivel para cada subnodo.

Más información sobre Árbol binario en estructura de datos si estás interesado.

¿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.

Depende del elemento que se insertará, buscará o eliminará; después de la comparación, el algoritmo puede eliminar 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 del árbol binario
• Insertar: agrega un elemento al árbol binario
• Eliminar: eliminar 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 Operadesarrollo

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 que el elemento a ubicar sea menor o mayor que la raíz.

1. El elemento a buscar es 10.
2. Compare el elemento con el nodo raíz 12, 10 <12, por lo tanto, se moverá al subárbol izquierdo. No es necesario analizar el subárbol derecho
3. Ahora compare 10 con el nodo 7, 10 > 7, así que muévase al subárbol derecho
4. Luego compare 10 con el siguiente nodo, que es 9, 10 > 9, busque en el subárbol secundario derecho
5. 10 coincide con el valor en el nodo, 10 = 10, devuelve el valor al usuario.

Pseudocódigo para búsquedas 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 Operadesarrollo

Esta es una operación muy sencilla. Primero, se inserta el nodo raíz, luego se compara el siguiente valor con el nodo raíz. Si el valor es mayor que la raíz, se agrega al subárbol derecho y si es menor que la raíz, 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. Inserte 12 como nodo raíz y compare los siguientes valores 7 y 9 para insertarlos en consecuencia en los subárboles derecho e izquierdo.
3. Compare los valores restantes 19, 5 y 10 con el nodo raíz 12 y colóquelos en consecuencia. 19 > 12 colóquelo como hijo derecho de 12, 5 12 y 5 es > 7, coloque 7 como subárbol derecho de 10.

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

Borrar OperaSupuestos de Alcance

Para eliminar un nodo de una BST, existen algunos casos, es decir, eliminar una raíz o eliminar un nodo hoja. Además, después de eliminar una raíz, debemos pensar en el nodo raíz.

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 fácil, solo necesita eliminar el nodo que no tiene 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 con las dos reglas siguientes
• 3a – En orden predecesor: debe eliminar el nodo con dos hijos y reemplazarlo con el valor más grande en el subárbol izquierdo del nodo eliminado.
• 3b – En el orden sucesor: debe eliminar el nodo con dos hijos y reemplazarlo con el valor más grande en el subárbol derecho del nodo eliminado.

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

1. Este es el segundo caso de eliminación en el que eliminas un nodo que tiene 1 hijo, como puedes ver en el diagrama que 9 tiene un hijo.
2. Elimine el nodo 9 y reemplácelo con su hijo 10 y agregue un enlace del 7 al 10
3. Ver la nueva estructura del BST sin 9

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

1. 1 Eliminar un nodo 12 que tenga dos hijos
2. 2 La eliminación del nodo se producirá según la regla Sucesor en orden, lo que significa que el elemento más grande en el subárbol derecho de 12 lo reemplazará.
3. 3 Elimine el nodo 12 y reemplácelo con 19, ya que es el valor más grande en el subárbol derecho.
4. 4 Ver la nueva estructura del BST después de eliminar 12

Pseudocódigo 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 to the root #we're deleting 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: atraviesa un árbol en forma de preorden.
• Recorrido en orden: atraviesa un árbol en orden.
• Recorrido posterior al orden: atraviesa un árbol en forma posterior al orden.

Resum

• BST es un algoritmo de nivel avanzado que realiza varias operaciones basadas en la comparación de los valores de los nodos con el nodo raíz.
• Cualquiera de los puntos en una jerarquía padre-hijo representa el nodo. Al menos un nodo principal o raíz permanece presente todo el tiempo.
• Hay un subárbol izquierdo y un subárbol derecho. El subárbol izquierdo contiene valores menores que el nodo raíz. Sin embargo, el subárbol derecho contiene un valor mayor que el nodo raíz.
• Cada nodo puede tener cero, uno o dos hijos.
• Un árbol de búsqueda binario facilita operaciones primarias como buscar, insertar y eliminar.
• La eliminación, al ser la más compleja, tiene múltiples casos, por ejemplo, un nodo sin ningún hijo, un nodo con un hijo y un nodo con dos hijos.
• El algoritmo se utiliza en soluciones del mundo real como juegos, datos de autocompletar y gráficos.