¿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 arquitectura de un algoritmo de búsqueda binario básico; 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.
En este tutorial de estructura de datos, aprenderá:
- ¿Qué es un árbol de búsqueda binaria?
- Atributos del árbol de búsqueda binaria
- ¿Por qué necesitamos un árbol de búsqueda binario?
- Tipos de árboles binarios
- ¿Cómo funciona el árbol de búsqueda binaria?
- Términos importantes
Atributos del árbol de búsqueda binaria
Un BST está formado por varios 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í mismos.
- 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.
- Está el nodo principal o el nivel principal 11. Debajo, hay nodos / ramas izquierdos y derechos con sus propios valores clave.
- El subárbol derecho tiene valores clave mayores que el nodo principal
- El subárbol izquierdo tiene valores que el nodo padre
¿Por qué necesitamos un árbol de búsqueda binario?
- Los dos factores principales que hacen del árbol de búsqueda binario 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 tiene un formato similar a una rama con relaciones padre-hijo, el algoritmo sabe en qué ubicación del árbol deben buscarse los elementos. Esto reduce el número de comparaciones clave-valor que el programa tiene que hacer para localizar el elemento deseado.
- Además, en caso de que el elemento a buscar sea mayor o menor que el nodo padre, el nodo sabe qué lado del árbol buscar. La razón es que el subárbol izquierdo es siempre menor que el nodo principal y el subárbol derecho tiene valores siempre iguales o mayores que el nodo principal.
- BST se utiliza comúnmente para implementar búsquedas complejas, lógicas de juego sólidas, 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, dirigiendo 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 de cada subnodo.
¿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 en consecuencia.
Depende del elemento que se inserte, busque o elimine, 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: 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.
Operación de búsqueda
Siempre inicie el árbol de análisis 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.
- El elemento a buscar es 10
- Compare el elemento con el nodo raíz 12, 10 <12, por lo que se mueve al subárbol izquierdo. No es necesario analizar el subárbol derecho
- Ahora compare 10 con el nodo 7, 10> 7, así que muévase al subárbol derecho
- Luego compare 10 con el siguiente nodo, que es 9, 10> 9, mire en el subárbol secundario derecho
- 10 coincidencias con el valor en el nodo, 10 = 10, devuelven el valor al usuario.
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.
- Hay una lista de 6 elementos que deben insertarse en una BST en orden de izquierda a derecha
- Inserte 12 como el nodo raíz y compare los siguientes valores 7 y 9 para insertarlos en consecuencia en el subárbol derecho e izquierdo
- 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 <7, por lo tanto colóquelo como hijo izquierdo de 7.
- Ahora compare 10, 10 es <12 y 10 es> 7 y 10 es> 9, coloque 10 como subárbol derecho de 9.
Eliminar operaciones
Eliminar es la más avanzada y compleja entre todas las demás operaciones. Hay varios casos manejados para su eliminación en la BST.
- 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 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 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
- Este es el primer caso de eliminación en el que elimina un nodo que no tiene hijos. Como puede ver en el diagrama, 19, 10 y 5 no tienen hijos. Pero eliminaremos 19.
- Elimine el valor 19 y elimine el enlace del nodo.
- Ver la nueva estructura del BST sin 19
- Este es el segundo caso de eliminación en el que elimina un nodo que tiene 1 hijo, como puede ver en el diagrama que 9 tiene un hijo.
- Elimine el nodo 9 y reemplácelo con su hijo 10 y agregue un enlace del 7 al 10
- Ver la nueva estructura del BST sin 9
- Aquí estarás borrando el nodo 12 que tiene dos hijos
- La eliminación del nodo ocurrirá en base a la regla predecesora en orden, lo que significa que el elemento más grande en el subárbol izquierdo de 12 lo reemplazará.
- Elimine el nodo 12 y reemplácelo con 10, ya que es el valor más grande en el subárbol izquierdo
- Ver la nueva estructura de la BST después de eliminar 12
- 1 Eliminar un nodo 12 que tiene dos hijos
- 2 La eliminación del nodo ocurrirá según la regla de sucesor en orden, lo que significa que el elemento más grande en el subárbol derecho de 12 lo reemplazará
- 3 Elimine el nodo 12 y reemplácelo con 19, ya que es el valor más grande en el subárbol derecho
- 4 Ver la nueva estructura de la BST después de eliminar 12
Términos importantes
- Insertar: inserta un elemento en un árbol / crea un árbol.
- Buscar: busca un elemento en un árbol.
- Preorder Traversal: atraviesa un árbol en forma de preorden.
- Inorder Traversal: atraviesa un árbol en orden.
- Recorrido posterior al pedido: atraviesa un árbol de una manera posterior al pedido.
Resumen
- BST es un algoritmo de nivel avanzado que realiza varias operaciones basadas en la comparación de los valores del nodo 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 que es mayor que el nodo raíz.
- Cada nodo puede tener cero, uno o dos hijos.
- Un árbol de búsqueda binaria facilita las operaciones primarias como buscar, insertar y eliminar.
- Eliminar siendo el más complejo tiene 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.