En este artículo, analizaremos el árbol de búsqueda binaria. Este artículo será muy útil e informativo para los estudiantes con formación técnica, ya que es un tema importante de su curso.
Antes de pasar directamente al árbol de búsqueda binaria, veamos primero una breve descripción del árbol.
¿Qué es un árbol?
Un árbol es un tipo de estructura de datos que se utiliza para representar los datos en forma jerárquica. Puede definirse como una colección de objetos o entidades denominadas nodos que están vinculados entre sí para simular una jerarquía. El árbol es una estructura de datos no lineal ya que los datos de un árbol no se almacenan de forma lineal ni secuencial.
Ahora comencemos con el tema, el árbol de búsqueda binaria.
¿Qué es un árbol de búsqueda binaria?
Un árbol de búsqueda binario sigue algún orden para organizar los elementos. En un árbol de búsqueda binaria, el valor del nodo izquierdo debe ser menor que el nodo principal y el valor del nodo derecho debe ser mayor que el nodo principal. Esta regla se aplica de forma recursiva a los subárboles izquierdo y derecho de la raíz.
Entendamos el concepto de árbol de búsqueda binaria con un ejemplo.
En la figura anterior, podemos observar que el nodo raíz es 40, todos los nodos del subárbol izquierdo son más pequeños que el nodo raíz y todos los nodos del subárbol derecho son mayores que el nodo raíz.
De manera similar, podemos ver que el hijo izquierdo del nodo raíz es mayor que su hijo izquierdo y más pequeño que su hijo derecho. Por tanto, también satisface la propiedad del árbol de búsqueda binario. Por tanto, podemos decir que el árbol de la imagen de arriba es un árbol de búsqueda binario.
Supongamos que si cambiamos el valor del nodo 35 a 55 en el árbol anterior, verificamos si el árbol será un árbol de búsqueda binario o no.
En el árbol anterior, el valor del nodo raíz es 40, que es mayor que su hijo izquierdo 30 pero menor que su hijo derecho de 30, es decir, 55. Por lo tanto, el árbol anterior no satisface la propiedad del árbol de búsqueda binaria. Por tanto, el árbol anterior no es un árbol de búsqueda binario.
Ventajas del árbol de búsqueda binaria
- Buscar un elemento en el árbol de búsqueda binaria es fácil ya que siempre tenemos una pista de qué subárbol tiene el elemento deseado.
- En comparación con las matrices y las listas vinculadas, las operaciones de inserción y eliminación son más rápidas en BST.
Ejemplo de creación de un árbol de búsqueda binario
Ahora, veamos la creación de un árbol de búsqueda binario usando un ejemplo.
Supongamos que los elementos de datos son - 45, 15, 79, 90, 10, 55, 12, 20, 50
- Primero tenemos que insertar 45 en el árbol como la raíz del árbol.
- Luego, lea el siguiente elemento; si es más pequeño que el nodo raíz, insértelo como la raíz del subárbol izquierdo y pase al siguiente elemento.
- De lo contrario, si el elemento es más grande que el nodo raíz, insértelo como la raíz del subárbol derecho.
Ahora, veamos el proceso de creación del árbol de búsqueda binaria utilizando el elemento de datos dado. El proceso de creación del BST se muestra a continuación:
Paso 1: inserte 45.
entero a cadena en java
Paso 2: inserte 15.
Como 15 es menor que 45, insértelo como el nodo raíz del subárbol izquierdo.
Paso 3: inserte 79.
Como 79 es mayor que 45, insértelo como el nodo raíz del subárbol derecho.
Paso 4: inserte 90.
90 es mayor que 45 y 79, por lo que se insertará como el subárbol derecho de 79.
Paso 5: inserte 10.
10 es menor que 45 y 15, por lo que se insertará como un subárbol izquierdo de 15.
Paso 6: inserte 55.
55 es mayor que 45 y menor que 79, por lo que se insertará como el subárbol izquierdo de 79.
Paso 7: inserte 12.
12 es menor que 45 y 15 pero mayor que 10, por lo que se insertará como el subárbol derecho de 10.
Paso 8: inserta 20.
20 es menor que 45 pero mayor que 15, por lo que se insertará como el subárbol derecho de 15.
Paso 9: inserta 50.
50 es mayor que 45 pero menor que 79 y 55. Por lo tanto, se insertará como un subárbol izquierdo de 55.
Ahora se completa la creación del árbol de búsqueda binaria. Después de eso, avancemos hacia las operaciones que se pueden realizar en el árbol de búsqueda binaria.
Podemos realizar operaciones de inserción, eliminación y búsqueda en el árbol de búsqueda binaria.
recorrido previo al pedido de un árbol
Entendamos cómo se realiza una búsqueda en un árbol de búsqueda binario.
Búsqueda en el árbol de búsqueda binaria
Buscar significa encontrar o localizar un elemento o nodo específico en una estructura de datos. En el árbol de búsqueda binaria, buscar un nodo es fácil porque los elementos en BST se almacenan en un orden específico. Los pasos para buscar un nodo en el árbol de búsqueda binaria se enumeran a continuación:
- Primero, compare el elemento a buscar con el elemento raíz del árbol.
- Si la raíz coincide con el elemento de destino, devuelve la ubicación del nodo.
- Si no coincide, verifique si el elemento es menor que el elemento raíz, si es más pequeño que el elemento raíz, muévase al subárbol izquierdo.
- Si es más grande que el elemento raíz, muévase al subárbol derecho.
- Repita el procedimiento anterior de forma recursiva hasta encontrar la coincidencia.
- Si el elemento no se encuentra o no está presente en el árbol, devuelve NULL.
Ahora, comprendamos la búsqueda en un árbol binario usando un ejemplo. Estamos tomando el árbol de búsqueda binario formado arriba. Supongamos que tenemos que encontrar el nodo 20 en el siguiente árbol.
Paso 1:
Paso 2:
Paso 3:
Ahora veamos el algoritmo para buscar un elemento en el árbol de búsqueda binaria.
Algoritmo para buscar un elemento en el árbol de búsqueda binaria
Search (root, item) Step 1 - if (item = root → data) or (root = NULL) return root else if (item <root 2 → data) return search(root left, item) else right, end if step - < pre> <p>Now let's understand how the deletion is performed on a binary search tree. We will also see an example to delete an element from the given tree.</p> <h3>Deletion in Binary Search tree</h3> <p>In a binary search tree, we must delete a node from the tree by keeping in mind that the property of BST is not violated. To delete a node from BST, there are three possible situations occur -</p> <ul> <li>The node to be deleted is the leaf node, or,</li> <li>The node to be deleted has only one child, and,</li> <li>The node to be deleted has two children</li> </ul> <p>We will understand the situations listed above in detail.</p> <p> <strong>When the node to be deleted is the leaf node</strong> </p> <p>It is the simplest case to delete a node in BST. Here, we have to replace the leaf node with NULL and simply free the allocated space.</p> <p>We can see the process to delete a leaf node from BST in the below image. In below image, suppose we have to delete node 90, as the node to be deleted is a leaf node, so it will be replaced with NULL, and the allocated space will free.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-15.webp" alt="Binary Search tree"> <p> <strong>When the node to be deleted has only one child</strong> </p> <p>In this case, we have to replace the target node with its child, and then delete the child node. It means that after replacing the target node with its child node, the child node will now contain the value to be deleted. So, we simply have to replace the child node with NULL and free up the allocated space.</p> <p>We can see the process of deleting a node with one child from BST in the below image. In the below image, suppose we have to delete the node 79, as the node to be deleted has only one child, so it will be replaced with its child 55.</p> <p>So, the replaced node 79 will now be a leaf node that can be easily deleted.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-16.webp" alt="Binary Search tree"> <p> <strong>When the node to be deleted has two children</strong> </p> <p>This case of deleting a node in BST is a bit complex among other two cases. In such a case, the steps to be followed are listed as follows -</p> <ul> <li>First, find the inorder successor of the node to be deleted.</li> <li>After that, replace that node with the inorder successor until the target node is placed at the leaf of tree.</li> <li>And at last, replace the node with NULL and free up the allocated space.</li> </ul> <p>The inorder successor is required when the right child of the node is not empty. We can obtain the inorder successor by finding the minimum element in the right child of the node.</p> <p>We can see the process of deleting a node with two children from BST in the below image. In the below image, suppose we have to delete node 45 that is the root node, as the node to be deleted has two children, so it will be replaced with its inorder successor. Now, node 45 will be at the leaf of the tree so that it can be deleted easily.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-17.webp" alt="Binary Search tree"> <p>Now let's understand how insertion is performed on a binary search tree.</p> <h3>Insertion in Binary Search tree</h3> <p>A new key in BST is always inserted at the leaf. To insert an element in BST, we have to start searching from the root node; if the node to be inserted is less than the root node, then search for an empty location in the left subtree. Else, search for the empty location in the right subtree and insert the data. Insert in BST is similar to searching, as we always have to maintain the rule that the left subtree is smaller than the root, and right subtree is larger than the root.</p> <p>Now, let's see the process of inserting a node into BST using an example.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-18.webp" alt="Binary Search tree"> <br> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-19.webp" alt="Binary Search tree"> <h3>The complexity of the Binary Search tree</h3> <p>Let's see the time and space complexity of the Binary search tree. We will see the time complexity for insertion, deletion, and searching operations in best case, average case, and worst case.</p> <h3>1. Time Complexity</h3> <table class="table"> <tr> <th>Operations</th> <th>Best case time complexity</th> <th>Average case time complexity</th> <th>Worst case time complexity</th> </tr> <tr> <td> <strong>Insertion</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> <tr> <td> <strong>Deletion</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> <tr> <td> <strong>Search</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> </table> <p>Where 'n' is the number of nodes in the given tree.</p> <h3>2. Space Complexity</h3> <table class="table"> <tr> <th>Operations</th> <th>Space complexity</th> </tr> <tr> <td> <strong>Insertion</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Deletion</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Search</strong> </td> <td>O(n)</td> </tr> </table> <ul> <li>The space complexity of all operations of Binary search tree is O(n).</li> </ul> <h2>Implementation of Binary search tree</h2> <p>Now, let's see the program to implement the operations of Binary Search tree.</p> <p> <strong>Program:</strong> Write a program to perform operations of Binary Search tree in C++.</p> <p>In this program, we will see the implementation of the operations of binary search tree. Here, we will see the creation, inorder traversal, insertion, and deletion operations of tree.</p> <p>Here, we will see the inorder traversal of the tree to check whether the nodes of the tree are in their proper location or not. We know that the inorder traversal always gives us the data in ascending order. So, after performing the insertion and deletion operations, we perform the inorder traversal, and after traversing, if we get data in ascending order, then it is clear that the nodes are in their proper location.</p> <pre> #include using namespace std; struct Node { int data; Node *left; Node *right; }; Node* create(int item) { Node* node = new Node; node->data = item; node->left = node->right = NULL; return node; } /*Inorder traversal of the tree formed*/ void inorder(Node *root) { if (root == NULL) return; inorder(root->left); //traverse left subtree cout<data <right); traverse right subtree } node* findminimum(node* cur) *to find the inorder successor* { while(cur->left != NULL) { cur = cur->left; } return cur; } Node* insertion(Node* root, int item) /*Insert a node*/ { if (root == NULL) return create(item); /*return new node if tree is empty*/ if (item data) root->left = insertion(root->left, item); else root->right = insertion(root->right, item); return root; } void search(Node* &cur, int item, Node* &parent) { while (cur != NULL && cur->data != item) { parent = cur; if (item data) cur = cur->left; else cur = cur->right; } } void deletion(Node*& root, int item) /*function to delete a node*/ { Node* parent = NULL; Node* cur = root; search(cur, item, parent); /*find the node to be deleted*/ if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) /*When node has no children*/ { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur->right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? cur->left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } int main() { Node* root = NULL; root = insertion(root, 45); root = insertion(root, 30); root = insertion(root, 50); root = insertion(root, 25); root = insertion(root, 35); root = insertion(root, 45); root = insertion(root, 60); root = insertion(root, 4); printf('The inorder traversal of the given binary tree is -
'); inorder(root); deletion(root, 25); printf('
After deleting node 25, the inorder traversal of the given binary tree is -
'); inorder(root); insertion(root, 2); printf('
After inserting node 2, the inorder traversal of the given binary tree is -
'); inorder(root); return 0; } </data></pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-20.webp" alt="Binary Search tree"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></root> Producción
Después de la ejecución del código anterior, el resultado será:
Entonces, eso es todo sobre el artículo. Espero que el artículo le resulte útil e informativo.