Al terminar esta nota
- Insertar respetando invariantes
- Recorrer in-order
- Entender el riesgo de desbalance
Una regla recursiva
Cada nodo es la raíz de otro árbol. Para insertar, compará, elegí izquierda o derecha y repetí hasta encontrar un lugar vacío.
js
function insert(node, value) {
if (!node) return { value, left: null, right: null };
if (value < node.value) node.left = insert(node.left, value);
if (value > node.value) node.right = insert(node.right, value);
return node;
}El recorrido revela el orden
Recorrer izquierda, nodo y derecha produce los valores ordenados. Es una consecuencia directa del invariante.
js
function inOrder(node, result = []) {
if (!node) return result;
inOrder(node.left, result);
result.push(node.value);
return inOrder(node.right, result);
}Un árbol también puede ser una lista
Insertar valores ya ordenados genera una rama larga. La búsqueda deja de ser O(log n) y cae a O(n). Árboles AVL o red-black se rebalancean.
Visualizador de árbol binario● interactivo
8
310
1614
47
Probá el peor caso
Compará el árbol producido por 5, 3, 8, 2, 4 con el producido por 2, 3, 4, 5, 8.
Mostrar una pista
Observá la altura máxima de cada árbol.