Data Structure & Algorithms
Binary Search Trees, búsqueda, inserción y eliminación, traversals inorder, altura y diferencias entre BST simples, AVL y Red-Black trees.
Un Binary Search Tree o BST mantiene claves ordenadas mediante este invariante:
claves del subárbol izquierdo < clave del nodo < claves del subárbol derechoLa regla debe cumplirse para subárboles completos, no solo para los hijos directos.
10
/ \
5 15
/ \ \
3 7 20Buscar, insertar y eliminar cuestan O(h), donde h es la altura del árbol. Solo son O(log n) cuando la altura permanece logarítmica.
Un BST necesita decidir qué ocurre si una clave ya existe:
La elección forma parte del contrato. Esta nota rechazará duplicados para mantener un ejemplo claro.
Para reutilizar el árbol con distintos tipos, separa el orden del dato:
type Comparator<T> = (a: T, b: T) => number;a va antes que b;a va después.El comparador debe ser consistente y transitivo. Si a < b y b < c, también debe cumplirse a < c.
class TreeNode<T> {
left: TreeNode<T> | null = null;
right: TreeNode<T> | null = null;
constructor(public value: T) {}
}Compara la clave buscada con el nodo actual:
class BinarySearchTree<T> {
private root: TreeNode<T> | null = null;
constructor(private readonly compare: Comparator<T>) {}
has(value: T): boolean {
let current = this.root;
while (current) {
const order = this.compare(value, current.value);
if (order === 0) return true;
current = order < 0 ? current.left : current.right;
}
return false;
}
}La búsqueda no “descarta la mitad” necesariamente. Descarta un subárbol, cuyo tamaño depende del balance. En un árbol degenerado puede quedar casi todo el trabajo.
Recorre el mismo camino de búsqueda hasta encontrar una referencia null.
insert(value: T): boolean {
const node = new TreeNode(value);
if (!this.root) {
this.root = node;
return true;
}
let current = this.root;
while (true) {
const order = this.compare(value, current.value);
if (order === 0) return false;
if (order < 0) {
if (!current.left) {
current.left = node;
return true;
}
current = current.left;
} else {
if (!current.right) {
current.right = node;
return true;
}
current = current.right;
}
}
}Antes de cada iteración, si la clave existe o puede insertarse, su posición válida está dentro del subárbol de current.
El mínimo está en el camino más a la izquierda; el máximo, a la derecha.
private minNode(node: TreeNode<T>): TreeNode<T> {
let current = node;
while (current.left) {
current = current.left;
}
return current;
}Costo: O(h) en el peor caso.
Eliminar requiere conservar el invariante. Hay tres casos.
No tiene hijos. Se reemplaza por null.
5 nullEl hijo ocupa la posición del nodo eliminado.
5 7
\ →
7Se reemplaza el valor por su inorder successor, el mínimo del subárbol derecho, y luego se elimina ese sucesor.
10 12
/ \ / \
5 15 → 5 15
/ \ \
12 20 20remove(value: T): boolean {
let removed = false;
const removeNode = (node: TreeNode<T> | null, target: T): TreeNode<T> | null => {
if (!node) return null;
const order = this.compare(target, node.value);
if (order < 0) {
node.left = removeNode(node.left, target);
return node;
}
if (order > 0) {
node.right = removeNode(node.right, target);
return node;
}
removed = true;
if (!node.left) return node.right;
if (!node.right) return node.left;
const successor = this.minNode(node.right);
node.value = successor.value;
node.right = removeNode(node.right, successor.value);
return node;
};
this.root = removeNode(this.root, value);
return removed;
}La segunda eliminación del sucesor vuelve a asignar removed = true, pero eso no cambia el resultado. En una clase de producción convendría separar una función interna que no altere el indicador para mantener responsabilidades más limpias.
La versión recursiva usa O(h) de call stack.
En un BST, inorder produce claves en orden creciente según el comparador.
inorder(): T[] {
const result: T[] = [];
const stack: TreeNode<T>[] = [];
let current = this.root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop()!;
result.push(current.value);
current = current.right;
}
return result;
}Tiempo: O(n), porque visita cada nodo. Memoria adicional: O(h) por el stack.
Todas las operaciones principales dependen de h:
| Operación | Árbol balanceado | Árbol degenerado |
|---|---|---|
| Buscar | O(log n) | O(n) |
| Insertar | O(log n) | O(n) |
| Eliminar | O(log n) | O(n) |
| Mínimo/máximo | O(log n) | O(n) |
| Traversal completo | O(n) | O(n) |
Insertar claves ya ordenadas en un BST sin balance:
1
\
2
\
3
\
4La estructura se comporta como una linked list.
Un árbol balanceado mantiene su altura proporcional a log n. No significa que cada nodo tenga exactamente la misma cantidad de elementos a ambos lados.
Mantiene una diferencia de altura estricta entre subárboles y realiza rotaciones después de insertar o eliminar.
Mantiene reglas de color que limitan la altura sin exigir un balance tan estricto.
O(log n) garantizado para búsqueda, inserción y eliminación;Las rotaciones cambian la forma sin romper el orden inorder:
30 20
/ → / \
20 10 30
/
10No necesitas memorizar todos los casos de colores para comprender el objetivo: impedir que la altura se vuelva lineal.
| Necesidad | Array ordenado | BST balanceado |
|---|---|---|
| Buscar | O(log n) | O(log n) |
| Insertar/eliminar | O(n) por desplazamientos | O(log n) |
| Acceso por índice | O(1) | No directo |
| Localidad de memoria | Buena | Peor por nodos |
| Iteración ordenada | Directa | Inorder O(n) |
Si los datos se construyen una vez y se consultan mucho, un array ordenado puede ser más simple y rápido en la práctica.
O(1), sin orden de claves útil para rangos.O(log n) garantizado y consultas como menor, mayor, predecessor, successor o rango.Elegir depende de las operaciones, no solo del lookup individual.
El orden permite podar subárboles:
El costo es O(h + k) en un árbol balanceado, donde k es la cantidad de resultados devueltos.
O(log n).O(h).h en O(log n).¿Por qué un BST construido con valores aleatorios suele ser rápido, pero eso no ofrece una garantía de peor caso?
Porque un orden de inserción aleatorio suele producir una altura cercana a log n en promedio, pero existe una entrada válida, como valores ordenados, que produce altura n. Sin auto-balance, el peor caso sigue siendo O(n).