Árbol binario de búsqueda (BST)
Última actualización
Un árbol binario de búsqueda mantiene sus valores ordenados: para cada nodo, todos los valores de su subárbol izquierdo son menores y todos los de su subárbol derecho son mayores. Para insertar o encontrar un valor comienzas en la raíz y avanzas repetidamente a la izquierda o a la derecha según la comparación, de modo que cada paso divide a la mitad el espacio de búsqueda. Pulsa reproducir arriba para ver los valores colocados por comparación y una búsqueda que baja por el árbol.
En un árbol equilibrado estas operaciones se ejecutan en tiempo O(log n). El problema: insertar datos ya ordenados hace que el árbol degenere en una lista enlazada con operaciones O(n), que es exactamente por lo que existen variantes autoequilibradas como los árboles AVL y rojo-negro.
Complejidad temporal y espacial
| Operación | Equilibrado | Peor caso (desbalanceado) |
|---|---|---|
| Búsqueda | O(log n) | O(n) |
| Inserción | O(log n) | O(n) |
| Eliminación | O(log n) | O(n) |
| Espacio | O(n) | O(n) |
Paso a paso (inserción)
| Paso | Qué ocurre |
|---|---|
| 1 | Si el árbol está vacío, el nuevo valor se convierte en la raíz. |
| 2 | En caso contrario, empieza en la raíz. |
| 3 | Si el valor es menor, ve al hijo izquierdo; si es mayor, ve a la derecha. |
| 4 | Repite hasta llegar a un lugar vacío. |
| 5 | Coloca allí el nuevo valor como hoja. |
Ejemplo resuelto
Insertando [5, 3, 8, 1, 4] en un árbol vacío, un valor a la vez:
| Insertar | Camino recorrido | Acción |
|---|---|---|
5 | - | El árbol está vacío, así que 5 se convierte en la raíz. |
3 | 5 | 3 < 5, ve a la izquierda; el lugar está vacío, coloca 3 como hijo izquierdo de 5. |
8 | 5 | 8 > 5, ve a la derecha; el lugar está vacío, coloca 8 como hijo derecho de 5. |
1 | 5 -> 3 | 1 < 5 ve a la izquierda, luego 1 < 3 ve a la izquierda; coloca 1 como hijo izquierdo de 3. |
4 | 5 -> 3 | 4 < 5 ve a la izquierda, luego 4 > 3 ve a la derecha; coloca 4 como hijo derecho de 3. |
Cuándo usar un árbol binario de búsqueda
| Úsalo cuando | Evítalo cuando |
|---|---|
| Necesitas orden más búsquedas rápidas y las inserciones llegan en orden aleatorio. | Tus datos llegan ya ordenados: un BST desbalanceado degrada a O(n) por operación. |
| Quieres que el recorrido en orden devuelva los valores en secuencia ordenada de forma gratuita. | Solo necesitas pruebas de pertenencia sin orden: una tabla hash ofrece búsquedas O(1) en promedio. |
| Necesitas consultas por rango o el sucesor/predecesor de una clave. | Necesitas garantías O(log n): recurre a un árbol autoequilibrado AVL o rojo-negro. |
| El conjunto de datos cambia con frecuencia y actualizar un arreglo ordenado sería costoso. | El conjunto de datos es fijo y de solo lectura: un arreglo ordenado con búsqueda binaria es más simple y aprovecha mejor la caché. |
Código de Binary Search Tree
Una implementación limpia y ejecutable de Binary Search Tree en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Binary Search Tree en Python
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))Código de Binary Search Tree en JavaScript
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));Código de Binary Search Tree en Java
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}Código de Binary Search Tree en C++
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}Código de Binary Search Tree en C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}Preguntas frecuentes sobre el árbol binario de búsqueda
¿Cuál es la complejidad temporal de un árbol binario de búsqueda?
La búsqueda, la inserción y la eliminación son
O(log n) en un árbol equilibrado, porque cada comparación descarta la mitad de los nodos restantes. En el peor caso, un árbol desbalanceado en forma de cadena por inserciones ordenadas, degradan a O(n).¿Cuál es la diferencia entre un árbol binario y un árbol binario de búsqueda?
Un árbol binario es cualquier árbol donde cada nodo tiene como máximo dos hijos, sin regla de orden. Un árbol binario de búsqueda añade la invariante de que los valores del subárbol izquierdo son menores y los del derecho son mayores que el nodo, que es lo que permite búsquedas rápidas.
¿Por qué un árbol binario de búsqueda puede volverse lento?
Si los valores se insertan en orden ordenado (o inverso), cada nuevo nodo va al mismo lado, produciendo un árbol alto y desbalanceado que se comporta como una lista enlazada:
O(n) por operación. Los árboles autoequilibrados (AVL, rojo-negro) rotan nodos para evitarlo.¿Cuál es la diferencia entre un árbol binario de búsqueda y una tabla hash?
Una tabla hash ofrece búsquedas
O(1) en promedio pero almacena las claves sin ningún orden, por lo que no puede responder consultas por rango o de sucesor. Un árbol binario de búsqueda es algo más lento con O(log n) pero mantiene las claves ordenadas, lo que permite recorrerlas en orden y encontrar valores cercanos. Elige un BST cuando el orden importa y una tabla hash cuando solo necesitas pruebas de pertenencia.¿Cuándo debería usar un árbol autoequilibrado en lugar de un BST simple?
Usa un árbol autoequilibrado (AVL, rojo-negro) siempre que no puedas controlar el orden de inserción y necesites un rendimiento
O(log n) garantizado. Un BST simple está bien para enseñar, para conjuntos pequeños o cuando las claves llegan en orden aleatorio, pero no protege contra el peor caso desbalanceado.¿Un recorrido en orden de un BST devuelve valores ordenados?
Sí. Visitar el subárbol izquierdo, luego el nodo y después el subárbol derecho produce las claves en orden ascendente, lo que se sigue directamente de la invariante del BST. Un error común es esperar lo mismo de un árbol binario simple: sin la regla de orden, el recorrido en orden no produce ninguna secuencia significativa.
Recursos relacionados
Más visualizaciones
