← Estructuras de datos desde cero · Lección 20/32
Buscar e insertar en un BST
Una sola regla
Un árbol binario de búsqueda (BST, por *binary search tree*) es un árbol binario con una regla: en cada nodo, todo lo que cuelga a su izquierda es menor y todo lo que cuelga a su derecha es mayor. No sólo sus hijos directos: todo el subárbol.
Para insertar no hay que pensar dónde: se compara con la raíz y se baja a la izquierda o a la derecha hasta encontrar un hueco (null). Ahí se cuelga el nodo nuevo. Si el valor ya estaba, aquí se ignora.
El dibujo es el árbol que sale de insertar 8, 3, 10, 1, 6, 14, 4 y 7, en ese orden.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
- La raíz es el 8, el primero que entró; a su izquierda el 3 y a su derecha el 10.
- El 6 quedó a la derecha del 3 (es mayor que 3) pero a la izquierda del 8 (es menor que 8).
- El 4 y el 7 cuelgan del 6. Cambia el orden de la lista y córrelo: los mismos valores dan otro árbol.
Toda la lección en una página
Una sola regla
Un árbol binario de búsqueda (BST, por *binary search tree*) es un árbol binario con una regla: en cada nodo, todo lo que cuelga a su izquierda es menor y todo lo que cuelga a su derecha es mayor. No sólo sus hijos directos: todo el subárbol.
Para insertar no hay que pensar dónde: se compara con la raíz y se baja a la izquierda o a la derecha hasta encontrar un hueco (null). Ahí se cuelga el nodo nuevo. Si el valor ya estaba, aquí se ignora.
El dibujo es el árbol que sale de insertar 8, 3, 10, 1, 6, 14, 4 y 7, en ese orden.
class Nodo {
constructor(valor) {
this.valor = valor;
this.izq = null; // menores
this.der = null; // mayores
}
}
function insertar(raiz, valor) {
if (raiz === null) return new Nodo(valor); // el hueco: aquí va
if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
return raiz; // los repetidos se ignoran
}
let raiz = null;
for (const v of [8, 3, 10, 1, 6, 14, 4, 7]) raiz = insertar(raiz, v);
console.log(raiz.valor, raiz.izq.valor, raiz.der.valor);
console.log(raiz.izq.der.valor);
console.log(raiz.izq.der.izq.valor, raiz.izq.der.der.valor);
- La raíz es el 8, el primero que entró; a su izquierda el 3 y a su derecha el 10.
- El 6 quedó a la derecha del 3 (es mayor que 3) pero a la izquierda del 8 (es menor que 8).
- El 4 y el 7 cuelgan del 6. Cambia el orden de la lista y córrelo: los mismos valores dan otro árbol.
Buscar es bajar por un solo lado
Para buscar se hace lo mismo que para insertar: comparar y bajar. Cada comparación descarta un subárbol entero, así que los pasos no dependen de cuántos nodos hay, sino de la altura del árbol, h. Buscar e insertar cuestan O(h).
Si el árbol está bien repartido, la altura es más o menos log₂ n y la búsqueda es tan rápida como la búsqueda binaria en un arreglo ordenado. La diferencia: aquí meter un valor nuevo también es O(h), y en el arreglo había que recorrer todo para hacerle lugar.
class Nodo {
constructor(valor) {
this.valor = valor;
this.izq = null;
this.der = null;
}
}
function insertar(raiz, valor) {
if (raiz === null) return new Nodo(valor);
if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
return raiz;
}
function armar(valores) {
let raiz = null;
for (const v of valores) raiz = insertar(raiz, v);
return raiz;
}
// Devuelve cuántos nodos visitó; negativo si no lo encontró
function buscar(raiz, valor) {
let nodo = raiz, pasos = 0;
while (nodo !== null) {
pasos++;
if (valor === nodo.valor) return pasos;
nodo = valor < nodo.valor ? nodo.izq : nodo.der;
}
return -pasos;
}
const raiz = armar([8, 3, 10, 1, 6, 14, 4, 7]);
console.log("7:", buscar(raiz, 7));
console.log("14:", buscar(raiz, 14));
console.log("8:", buscar(raiz, 8));
console.log("5:", buscar(raiz, 5));
- El 7 está a 4 pasos: 8 → 3 → 6 → 7.
- El 8 está a 1: es la raíz.
- El 5 no está: se dio cuenta en 4 pasos (8 → 3 → 6 → 4 y luego
null), sin mirar el 10 ni el 14.
En orden sale ordenado, y la trampa de validar
Si recorres el árbol en orden (primero la izquierda, luego el nodo, luego la derecha), los valores salen ordenados de menor a mayor. Es la prueba de que la regla se cumple.
Y una trampa clásica de entrevista: para revisar si un árbol es BST no basta con comparar cada nodo con sus hijos. En el segundo árbol del dibujo, el 6 es mayor que su padre 3 (bien), pero está a la izquierda del 5 y es mayor que 5 (mal). Hay que bajar llevando los límites que cada nodo tiene que respetar.
class Nodo {
constructor(valor) {
this.valor = valor;
this.izq = null;
this.der = null;
}
}
function insertar(raiz, valor) {
if (raiz === null) return new Nodo(valor);
if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
return raiz;
}
function armar(valores) {
let raiz = null;
for (const v of valores) raiz = insertar(raiz, v);
return raiz;
}
function inorden(nodo, salida = []) {
if (nodo === null) return salida;
inorden(nodo.izq, salida);
salida.push(nodo.valor);
inorden(nodo.der, salida);
return salida;
}
function esBST(nodo, min = -Infinity, max = Infinity) {
if (nodo === null) return true;
if (nodo.valor <= min || nodo.valor >= max) return false;
// a la izquierda, el tope es este valor; a la derecha, el piso
return esBST(nodo.izq, min, nodo.valor) && esBST(nodo.der, nodo.valor, max);
}
const raiz = armar([8, 3, 10, 1, 6, 14, 4, 7]);
console.log(inorden(raiz));
console.log(esBST(raiz));
// Armado a mano para que esté mal: el 6 a la izquierda del 5
const malo = new Nodo(5);
malo.izq = new Nodo(3);
malo.izq.der = new Nodo(6);
console.log(inorden(malo));
console.log(esBST(malo));
- El árbol bueno sale
[1, 3, 4, 6, 7, 8, 10, 14]: ordenado. - El malo sale
[3, 6, 5]: el 6 antes del 5 delata el error, yesBSTlo detecta porque el 6 llegó con tope 5.