BST es una estructura de datos que mantiene los datos en una lista ordenada. Se conoce como árbol de búsqueda binaria porque, en el árbol, cada nodo tiene un máximo de dos hijos que no se pueden aumentar más. Esto se conoce como árbol de búsqueda porque se utiliza para buscar o encontrar cualquier elemento presente. Implementaremos este fenómeno en el lenguaje C++.
Tabla de Contenidos
Implementación
En una implementación, el primer paso es usar una estructura para inicializar la clave de tipo entero y los nodos del lado izquierdo y derecho. Estos nodos se definen mediante el uso de un puntero variable, ya que ambos guardan las direcciones de los nodos alternativos. Después de eso, cerramos la estructura.
Volveremos a crear un nuevo nodo a través de una estructura. El parámetro de la función contendrá los datos que queremos introducir en el nodo.
nodo de estructura *nuevoNodo (elemento int)
Creará un nuevo nodo temporal que almacenará datos en él, y el tamaño de la memoria se asignará a través de malloc(). Agregaremos el valor del elemento en la parte clave del nodo. Mientras que las partes izquierda y derecha, que se declararon previamente en la estructura, se declaran como nulas ahora porque es el primer nodo. Se devolverá la temperatura.
Se crea una función con el nombre «inorder» y aceptará el nodo raíz en el parámetro. Como sabemos, el árbol contiene tres partes principales: nodo, lados izquierdo y derecho del árbol. Usaremos una declaración if para verificar si la raíz no es nula. Luego, llame a la función y envíe la parte izquierda de la raíz. Esto mostrará la raíz misma con una flecha que indicará la dirección del camino en el árbol. A continuación, para atravesar a la derecha, llame a la función inorder con la derecha de la raíz como parámetro.
En orden (raíz -> izquierda)
Así es como se realiza el desplazamiento en orden. Para insertar un nuevo nodo en el árbol, usaremos una función que tomará un nodo y la clave como valores de parámetro. Si el árbol ya está vacío, se devolverá el nuevo nodo. En el segundo caso, si el árbol no está vacío, primero vaya al lado derecho e inserte un nuevo nodo aquí. Para la inserción, usaremos una instrucción if-else para verificar el orden de la clave. La nueva clave irá al lado izquierdo para el orden ascendente. Si la parte que verificará la nueva clave es menor que el valor presente en el nodo, ingrese la clave en la parte izquierda del nodo.
Nodo – > izquierda = insertar (nodo ->izquierda, clave)
Mientras que si la clave es mayor, irá a la parte derecha.
Después de la inserción del nodo, comprobaremos el siguiente nodo o el nodo que es el sucesor. Se crea una función de valor mínimo que creará un nuevo nodo con un nombre *actual. Este nodo será asignado por un valor pasado como argumento a la función. Primero encontrará el nodo de la esquina o la hoja del modo izquierdo en el lado izquierdo del árbol. Usamos un bucle while que itera hasta que finaliza el recorrido del nodo. En otras palabras, la parte izquierda del nodo actual no es nula.
Actual =actual – >izquierda
Continúe asignando al nodo actual el valor de la siguiente corriente dentro del bucle de la izquierda.
Nuestro árbol está atravesado y organizado agregando hojas en ambos lados. Cada valor se insertará a través de la llamada de función realizada desde el programa principal. Ahora, necesitamos buscar cualquier elemento y lo eliminaremos una vez que lo encuentre.
El árbol en C++ funciona con el mismo fenómeno que la lista enlazada. Aplicaremos la búsqueda binaria en el árbol y realizaremos una operación de eliminación para eliminar un nodo u hoja del árbol. Se crea una función del nodo de eliminación; contendrá el árbol y el valor como parámetros. Comprobaremos primero que los árboles deben tener valores dentro de ellos. Por lo tanto, se usará la declaración if, y si la raíz es NULL, significa que solo se devolverá la raíz.
Si (clave < root – >llave)
La clave que desea eliminar es más pequeña que el nodo raíz. Luego muévase hacia el lado izquierdo y llame a la función de eliminación con la parte izquierda del árbol y la tecla que se eliminará.
Raíz -> izquierda = deletenode (raíz -> izquierda, clave);
Y lo mismo ocurre con la parte else-if. Si la clave es mayor que la clave del nodo, vaya al camino correcto, llame a la función de eliminación. Pase la parte derecha del árbol y la clave para que sea fácil encontrar el nodo que desea eliminar.
Ahora, viniendo hacia la parte else, eso es aplicable si el nodo está solo, no tiene más hojas, o solo tiene un hijo por delante. Dentro de la parte else nuevamente, si se usará una declaración que verificará si no hay un nodo en el lado derecho, luego agregue el valor en el lado derecho del nodo al nuevo nodo temporal, de manera similar para el lado izquierdo.
Nodo de estructura * temp = raíz ->izquierda;
En esa condición, libere la raíz. Esto eliminará el valor de la raíz.
Gratis (raíz);
Si algún nodo contiene dos hojas, entonces para buscar el valor, usaremos la función de valor mínimo, y la parte correcta se enviará a la función.
Minvaluenode (raíz -> derecha);
Cuando se encuentre el valor a eliminar, lo declararemos la última parte del árbol para que pueda eliminarse fácilmente.
Raíz -> clave = temporal -> clave;
Después de hacer esto, elimine el nodo,
Raíz ->derecha = eliminar nodo (nodo – >derecha, temporal -> tecla);
Después de cerrar la función, declararemos aquí el programa principal. El nodo raíz se establecerá como NULL inicialmente. Usando la llamada a la función insert(), usaremos la raíz y los datos numéricos para el nodo.
Insertar (raíz, 5);
La función inorder se llama para el recorrido del árbol.
En orden (raíz);
Luego, para eliminar el nodo, llamaremos a la función eliminar.
Raíz = eliminarNodo (raíz, 10);
Después de la eliminación, los valores se muestran de nuevo.
Luego de escribir el código, lo ejecutaremos en la terminal de Ubuntu a través del compilador.
ps/expediente
Como puede ver, los siete elementos se ingresan en el nodo. Uno se elimina y el resto se mostrará en el mismo orden que antes.
Conclusión
Se utiliza un árbol de búsqueda binaria para almacenar los valores en forma ordenada. Para buscar cualquier número, todos los números deben ordenarse primero en orden. Después de eso, se busca el número especificado dividiendo el árbol en dos partes, formando subárboles. La implementación de BST se realiza en el sistema Ubuntu explicando un ejemplo de forma elaborada. Esperamos que este artículo le haya resultado útil. Consulte los otros artículos de Linux Hint para obtener más consejos y tutoriales.
