En este tutorial, aprenderá cómo funciona Binary Search Tree. Además, encontrará ejemplos prácticos del árbol de búsqueda binaria en C, C ++, Java y Python.
El árbol de búsqueda binaria es una estructura de datos que nos permite mantener rápidamente una lista ordenada de números.
- Se le llama árbol binario porque cada nodo de árbol tiene un máximo de dos hijos.
- Se denomina árbol de búsqueda porque se puede utilizar para buscar la presencia de un número en el
O(log(n))tiempo.
Las propiedades que separan un árbol de búsqueda binario de un árbol binario normal son
- Todos los nodos del subárbol izquierdo son menores que el nodo raíz
- Todos los nodos del subárbol derecho son más que el nodo raíz
- Ambos subárboles de cada nodo también son BST, es decir, tienen las dos propiedades anteriores.
Se muestra un árbol que tiene un subárbol derecho con un valor menor que la raíz para demostrar que no es un árbol de búsqueda binario válido
El árbol binario de la derecha no es un árbol de búsqueda binario porque el subárbol derecho del nodo "3" contiene un valor menor que él.
Hay dos operaciones básicas que puede realizar en un árbol de búsqueda binaria:
Operación de búsqueda
El algoritmo depende de la propiedad de BST de que si cada subárbol izquierdo tiene valores por debajo de la raíz y cada subárbol derecho tiene valores por encima de la raíz.
Si el valor está por debajo de la raíz, podemos decir con certeza que el valor no está en el subárbol derecho; solo necesitamos buscar en el subárbol izquierdo y si el valor está por encima de la raíz, podemos decir con seguridad que el valor no está en el subárbol izquierdo; solo necesitamos buscar en el subárbol correcto.
Algoritmo:
If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)
Intentemos visualizar esto con un diagrama.
4 no se encuentra, por lo tanto, atravesar el subárbol izquierdo de 8 
4 no se encuentra, por lo tanto, atravesar el subárbol derecho de 3 
4 no se encuentra, por lo tanto, atravesar el subárbol izquierdo de 6 4 se encuentra
Si se encuentra el valor, devolvemos el valor para que se propague en cada paso de recursividad como se muestra en la imagen a continuación.
Si te habrás dado cuenta, hemos llamado a return search (struct node *) cuatro veces. Cuando devolvemos el nuevo nodo o NULL, el valor se devuelve una y otra vez hasta que la búsqueda (raíz) devuelve el resultado final.
Si el valor se encuentra en alguno de los subárboles se propaga hacia arriba para que al final se devuelva, en caso contrario se devuelve nulo
Si no se encuentra el valor, finalmente llegamos al hijo izquierdo o derecho de un nodo hoja que es NULL y se propaga y devuelve.
Insertar operación
Insertar un valor en la posición correcta es similar a buscar porque tratamos de mantener la regla de que el subárbol izquierdo es menor que root y el subárbol derecho es mayor que root.
Seguimos yendo al subárbol derecho o al subárbol izquierdo dependiendo del valor y cuando llegamos a un punto que el subárbol izquierdo o derecho es nulo, colocamos el nuevo nodo allí.
Algoritmo:
If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;
El algoritmo no es tan simple como parece. Intentemos visualizar cómo agregamos un número a una BST existente.
4 <8 entonces, transversal a través del hijo izquierdo de 8 
4> 3 entonces, transversal a través del hijo derecho de 8 
4 <6 entonces, transversal a través del hijo izquierdo de 6 
Inserte 4 como un hijo izquierdo de 6
Hemos adjuntado el nodo pero aún tenemos que salir de la función sin dañar el resto del árbol. Aquí es donde el return node;al final resulta útil. En el caso de NULL, el nodo recién creado se devuelve y se adjunta al nodo padre; de lo contrario, se devuelve el mismo nodo sin ningún cambio a medida que subimos hasta que volvemos a la raíz.
Esto asegura que a medida que retrocedemos en el árbol, las otras conexiones de nodo no cambian.
Imagen que muestra la importancia de devolver el elemento raíz al final para que los elementos no pierdan su posición durante el paso de recursividad ascendente.
Operación de eliminación
Hay tres casos para eliminar un nodo de un árbol de búsqueda binaria.
Caso I
En el primer caso, el nodo a eliminar es el nodo hoja. En tal caso, simplemente elimine el nodo del árbol.
4 debe eliminarse 
Eliminar el nodo
Caso II
En el segundo caso, el nodo que se va a eliminar tiene un único nodo hijo. En tal caso, siga los pasos a continuación:
- Reemplace ese nodo con su nodo hijo.
- Retire el nodo secundario de su posición original.
6 debe eliminarse, 
copie el valor de su hijo en el nodo y elimine el 
árbol final hijo
Caso III
En el tercer caso, el nodo a eliminar tiene dos hijos. En tal caso, siga los pasos a continuación:
- Obtenga el sucesor en orden de ese nodo.
- Reemplace el nodo con el sucesor en orden.
- Retire el sucesor del orden de su posición original.
3 debe eliminarse Copie el valor del sucesor del orden (4) en el nodo 
Elimine el sucesor del orden
Ejemplos de Python, Java y C / C ++
Python Java C C ++ # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)
// Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )
// Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )
// Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); )
Complejidades del árbol de búsqueda binaria
Complejidad del tiempo
| Operación | Mejor complejidad de caso | Complejidad de casos promedio | Peor complejidad del caso |
| Buscar | O (log n) | O (log n) | En) |
| Inserción | O (log n) | O (log n) | En) |
| Supresión | O (log n) | O (log n) | En) |
Aquí, n es el número de nodos del árbol.
Complejidad espacial
La complejidad del espacio para todas las operaciones es O (n).
Aplicaciones de árbol de búsqueda binaria
- En indexación multinivel en la base de datos
- Para clasificación dinámica
- Para administrar áreas de memoria virtual en el kernel de Unix
