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

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

El árbol de búsqueda binaria es un algoritmo avanzado que se utiliza para analizar el nodo, sus ramas izquierda y derecha, que se modelan en una estructura de árbol y devuelven el valor. El BST está diseñado sobre la base de architecnología de un algoritmo básico de búsqueda binaria; por lo tanto, 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

Un BST está formado por varios nodos y consta de lo siguientewing 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.

Atributos del árbol de búsqueda binaria

  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 complex búsquedas, lógica de juego sólida, 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.

Aprenda más 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 lo siguientewing 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 comúnplex de todo es la operación Eliminar.

Operación de búsqueda

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.

Operación de búsqueda

  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 Searching 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)

Insertar operación

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.

Insertar operación

  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

Eliminar operaciones

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 hoja, podemos simplemente eliminarlo, pero si queremos eliminar una raíz, debemos reemplazar el valor de la raíz con otro nodo. Tomemos el siguientewing 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 de la siguiente manerawing dos reglas
  • 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.

Eliminar operaciones

  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

Eliminar operaciones

  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

Eliminar operaciones

  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

Eliminar operaciones

  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.

Resumen

  • 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.
  • Eliminar por ser el mas complex tener varios casos, por ejemplo, un nodo sin 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.