Árbol binario de búsqueda en Java

Problema

El índice de precios va a paso de tortuga

El filtro «precio de … a …» de la tienda busca en un índice de precios, no en todo el catálogo. El índice es un árbol binario: cada precio es un nodo, los más baratos a la izquierda, los más caros a la derecha. Con 1000 precios mezclados el árbol tiene 22 niveles, y escribir y buscar todos los precios cuesta en total 22 990 comparaciones: unas 23 por precio.

Esta mañana el proveedor cambió el formato: el feed llega ahora ordenado por precio. Los mismos 1000 precios, el mismo código, y las comparaciones saltan a 1 000 000: 43 veces más. El árbol tiene ahora 1000 niveles.

¿Por qué importa el orden de la entrada si los precios son los mismos?

La idea

Lo menor a la izquierda, lo mayor a la derecha

Un árbol binario de búsqueda (BST) está hecho de nodos con dos enlaces cada uno, left y right. Hay una sola regla: todo lo que está en el subárbol izquierdo de un nodo es menor que él, y todo lo que está en el derecho es mayor.

Así, buscar es una búsqueda binaria sin arreglo: en cada nodo comparas y saltas un subárbol entero. Añadir sigue el mismo camino hasta llegar a un hueco vacío y cuelga ahí el nodo nuevo. No se mueve nada, a diferencia de insertar en un arreglo ordenado.

boolean add(int price) {
    Node parent = null;
    Node cur = root;
    int level = 1;
    while (cur != null) {
        compares++;
        if (price == cur.price) return false;
        parent = cur;
        cur = price < cur.price ? cur.left : cur.right;
        level++;
    }
    Node node = new Node(price);
    if (parent == null) root = node;
    else if (price < parent.price) parent.left = node;
    else parent.right = node;
    size++;
    depth = Math.max(depth, level);
    return true;
}

boolean add(int price) {
    Node parent = null;
    Node cur = root;
    int level = 1;
    while (cur != null) {
        compares++;
        if (price == cur.price) return false;
        parent = cur;
        cur = price < cur.price ? cur.left : cur.right;
        level++;
    }
    Node node = new Node(price);
    if (parent == null) root = node;
    else if (price < parent.price) parent.left = node;
    else parent.right = node;
    size++;
    depth = Math.max(depth, level);
    return true;
}

List<Integer> sorted() {
    List<Integer> out = new ArrayList<>();
    walk(root, out);
    return out;
}

private void walk(Node node, List<Integer> out) {
    if (node == null) return;
    walk(node.left, out);
    out.add(node.price);
    walk(node.right, out);
}

Paso a paso, en palabras

Un índice de precios vacío. Cada precio baja desde la raíz: el más barato va a la izquierda, el más caro a la derecha.
49 llega primero. El árbol está vacío, así que 49 se convierte en la raíz.
12 < 49: a la izquierda. Ahí está vacío, así que 12 pasa a ser el hijo izquierdo de 49. 89 va a la derecha.
24: más barato que 49 (izquierda), más caro que 12 (derecha). Dos comparaciones, y queda en el nivel 3.
32: 49, 12, 24 y a la derecha. Tres comparaciones con 7 precios: cada una salta un subárbol entero.
walk: subárbol izquierdo, el nodo, subárbol derecho. Los precios salen ordenados: 6 12 24 32 49 89 159.

El número de comparaciones es el número de niveles del camino. Si el árbol es bajo, con unos log₂ n niveles, toda búsqueda es O(log n).

Míralo

Tu propio árbol

Un nodo guarda el precio y los dos enlaces:

class Node {
    int price;
    Node left;
    Node right;

    Node(int price) {
        this.price = price;
    }
}

add baja desde la raíz y recuerda el último nodo (parent). Cuando llega a un hueco vacío, cuelga el nodo nuevo a la izquierda o a la derecha de parent. El mismo precio no entra dos veces. level cuenta los niveles del camino, para que el árbol sepa qué profundidad tiene:

boolean add(int price) {
    Node parent = null;
    Node cur = root;
    int level = 1;
    while (cur != null) {
        compares++;
        if (price == cur.price) return false;
        parent = cur;
        cur = price < cur.price ? cur.left : cur.right;
        level++;
    }
    Node node = new Node(price);
    if (parent == null) root = node;
    else if (price < parent.price) parent.left = node;
    else parent.right = node;
    size++;
    depth = Math.max(depth, level);
    return true;
}

contains sigue el mismo camino, pero no cuelga nada:

boolean contains(int price) {
    Node cur = root;
    while (cur != null) {
        compares++;
        if (price == cur.price) return true;
        cur = price < cur.price ? cur.left : cur.right;
    }
    return false;
}

El precio más barato está lo más a la izquierda y el más caro lo más a la derecha (el árbol no está vacío):

int min() {
    Node node = root;
    while (node.left != null) node = node.left;
    return node.price;
}

int max() {
    Node node = root;
    while (node.right != null) node = node.right;
    return node.price;
}

Recorrido en orden: primero el subárbol izquierdo, luego el nodo y luego el subárbol derecho. Así los precios salen ordenados. Aquí usa recursión, porque cada subárbol es otra vez un árbol:

List<Integer> sorted() {
    List<Integer> out = new ArrayList<>();
    walk(root, out);
    return out;
}

private void walk(Node node, List<Integer> out) {
    if (node == null) return;
    walk(node.left, out);
    out.add(node.price);
    walk(node.right, out);
}

PriceTree tree = new PriceTree();
for (int price : new int[] { 49, 12, 89, 24, 6, 159, 32 }) {
    tree.add(price);
}
System.out.println("en orden: " + tree.sorted());
System.out.println("más barato: " + tree.min() + ", más caro: " + tree.max());
for (int price : new int[] { 32, 50 }) {
    tree.compares = 0;
    boolean found = tree.contains(price);
    System.out.println(price + ": " + (found ? "sí" : "no") + ", comparaciones: " + tree.compares);
}

en orden: [6, 12, 24, 32, 49, 89, 159]
más barato: 6, más caro: 159
32: sí, comparaciones: 4
50: no, comparaciones: 2

El 32 se encuentra con 4 comparaciones: 49, 12, 24, 32. Para el 50 bastan 2: 49, luego 89, y a la izquierda de 89 no hay nada, así que el 50 no está.

Pruébalo

¿Cuántas comparaciones?

PriceTree tree = new PriceTree();
for (int price : new int[] { 50, 30, 70, 20, 40, 60, 80 }) {
    tree.add(price);
}
tree.compares = 0;
tree.contains(65);
System.out.println(tree.compares);

Respuesta

Pruébalo

Completa

El precio más barato:

int min() {
    Node node = root;
    while (node. != null) node = node.left;
    return node.price;
}

La idea

Entrada ordenada: el árbol se vuelve una cadena

Volvamos al feed. Cuando los precios llegan ordenados, cada uno nuevo es más caro que todos los anteriores. Pasa por todos los nodos hacia la derecha y se cuelga en el extremo derecho. Nunca va nada a la izquierda, y el árbol es una cadena: una lista enlazada con enlaces vacíos inútiles.

boolean add(int price) {
    Node parent = null;
    Node cur = root;
    int level = 1;
    while (cur != null) {
        compares++;
        if (price == cur.price) return false;
        parent = cur;
        cur = price < cur.price ? cur.left : cur.right;
        level++;
    }
    Node node = new Node(price);
    if (parent == null) root = node;
    else if (price < parent.price) parent.left = node;
    else parent.right = node;
    size++;
    depth = Math.max(depth, level);
    return true;
}

Paso a paso, en palabras

El feed del proveedor envía los mismos 7 precios, pero ordenados: 6, 12, 24, 32, 49, 89, 159.
Cada precio nuevo es más caro que todos los anteriores, así que siempre va a la derecha. Nada va nunca a la izquierda.
El precio número i pasa por los i anteriores: 0 + 1 + … + 6 = 21 comparaciones. El árbol es una cadena de 7 niveles.
contains(159) recorre los 7 nodos, como una lista enlazada. Con 1000 precios: 1000 niveles.
Los mismos precios, equilibrados: 3 niveles en vez de 7. Los árboles AVL y los árboles rojo-negro mantienen esta forma con rotaciones.

El precio número i pasa por i nodos. Con n precios eso son 0 + 1 + … + (n − 1) al escribir, y otro tanto más n al buscar: exactamente n² comparaciones. Es la misma trampa que el mal pivote de quicksort: entrada ordenada y el peor caso.

El programa del problema: los mismos 1000 precios, una vez ordenados y otra mezclados:

static int[] shuffled(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = 100 + i;
    long x = 2026;
    for (int i = n - 1; i > 0; i--) {
        x = x * 48271 % 2147483647;
        int j = (int) (x % (i + 1));
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    return a;
}

static String report(int[] prices) {
    PriceTree tree = new PriceTree();
    for (int p : prices) tree.add(p);
    for (int p : prices) tree.contains(p);
    return "profundidad " + tree.depth + ", comparaciones " + tree.compares;
}

int[] feed = new int[1000];
for (int i = 0; i < 1000; i++) feed[i] = 100 + i;
System.out.println("ascendentes: " + report(feed));
System.out.println("mezclados: " + report(shuffled(1000)));

ascendentes: profundidad 1000, comparaciones 1000000
mezclados: profundidad 22, comparaciones 22990

Ejecuta las dos entradas en el navegador:

Precios en orden mezclado O(n log n)
Precios en orden ascendente O(n²)

Algoritmo	n = 10	n = 1000	n = 5000	n = 100.000
Precios en orden mezclado	56	22.990	157.880	4.029.826
Precios en orden ascendente	100	1.000.000	25.000.000	≈ 10.000.000.000

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

Con entrada mezclada, una búsqueda pasa en promedio por unos 2 · ln n − 3 nodos (unos 12 con 1000 precios), lo que crece como log n, y todo junto es O(n log n). Con entrada ordenada es O(n²): con 1000 precios, 1 000 000 de comparaciones frente a 22 990. Esta es la diferencia entre el caso promedio y el peor caso, y los datos reales suelen venir justo ordenados: por precio, por fecha, por número.

La idea

Un árbol equilibrado

Mezclar la entrada ayuda, pero no siempre se puede: los precios llegan uno a uno mientras la tienda funciona. Un árbol equilibrado se arregla solo: después de cada alta comprueba si una rama se ha vuelto mucho más larga que la otra y la reorganiza. Así la altura se mantiene en O(log n) con cualquier entrada, y cada búsqueda, alta y baja es O(log n).

La reorganización es una rotación: un nodo y su hijo intercambian los puestos. En una rotación a la derecha, el hijo izquierdo pasa a ser el padre, el padre antiguo pasa a ser su hijo derecho, y el subárbol derecho del hijo se mueve a la izquierda del padre antiguo. La regla «lo menor a la izquierda» sigue valiendo, y una rama se acorta en un nivel.

Más precisamente, para curiosos

Una rotación a la derecha alrededor del 32 en la cadena 32 → 24 → 12 (cada uno es el hijo izquierdo del anterior):

      32               24
     /                /  \
   24        →      12    32
   /
 12

El 24 pasa a ser la raíz y el 32 queda a su derecha. El orden de los valores es el mismo: 12, 24, 32.

AVL (Adelson-Velsky y Landis, 1962) guarda en cada nodo la altura de su subárbol. Si las alturas de los dos hijos se diferencian en más de 1, hace una o dos rotaciones. El árbol es muy bajo (como mucho unos 1,44 · log₂ n), así que buscar es rápido, pero añadir a veces cuesta más trabajo.

Un árbol rojo-negro colorea sus nodos y cumple dos reglas: un nodo rojo no tiene hijos rojos, y todo camino desde la raíz hasta un hueco vacío pasa por el mismo número de nodos negros. Así una rama es como mucho el doble de larga que otra, y la altura es como mucho 2 · log₂ n. Para añadir y quitar hacen falta cambios de color y, como mucho, dos o tres rotaciones.

Qué hacen los lenguajes:

Java: TreeMap y TreeSet son árboles rojo-negro. Además de get y put, tienen las operaciones ordenadas: firstKey, floorKey (la mayor hasta una clave dada), subMap(from, to). Ordenan por Comparable o por un Comparator que les pases.
C#: SortedSet<T> es un árbol rojo-negro, y SortedDictionary<TKey, TValue> está construido sobre él. SortedSet tiene Min, Max y GetViewBetween(from, to). Cuidado con SortedList<TKey, TValue>: son dos arreglos ordenados, así que buscar es O(log n), pero añadir en medio es O(n).
Python: no hay un árbol equilibrado incorporado. El módulo bisect busca en una lista ordenada en O(log n), pero insort inserta en O(n), porque desplaza los elementos. El paquete sortedcontainers (SortedList, SortedDict) se instala aparte y no es un árbol: guarda una lista de listas ordenadas de unos mil elementos cada una.
JavaScript: no hay un árbol ordenado incorporado. Map y Set conservan el orden de inserción, no el orden por valor. Queda un arreglo ordenado con búsqueda binaria, o una biblioteca.

Pruébalo

Encuentra el error

Alguien reescribió add. Entran cinco precios, pero el recorrido muestra solo algunos, y la búsqueda no encuentra el 6 ni el 24:

boolean add(int price) {
    Node parent = null;
    Node cur = root;
    int level = 1;
    while (cur != null) {
        compares++;
        if (price == cur.price) return false;
        parent = cur;
        cur = price < cur.price ? cur.left : cur.right;
        level++;
    }
    Node node = new Node(price);
    if (parent == null) root = node;
    else if (price > parent.price) parent.left = node;
    else parent.right = node;
    size++;
    depth = Math.max(depth, level);
    return true;
}

PriceTree tree = new PriceTree();
for (int price : new int[] { 49, 12, 89, 24, 6 }) {
    tree.add(price);
}
System.out.println("en orden: " + tree.sorted());
System.out.println("6: " + (tree.contains(6) ? "sí" : "no"));
System.out.println("24: " + (tree.contains(24) ? "sí" : "no"));

en orden: [49, 6]
6: no
24: no

¿En qué línea está el error?

Elige la línea con el error.

Ejercicio

Un precio deja de ser válido

Resuelve este ejercicio en tu propio editor.

Quitar del índice. Añade remove(price), que devuelve si quitó un precio. Hay tres casos:

el nodo es una hoja: basta con descolgarlo;
tiene un hijo: el hijo ocupa su lugar;
tiene dos hijos: busca el siguiente mayor precio (el más a la izquierda del subárbol derecho), ponlo en el lugar del quitado y quítalo del subárbol derecho. No tiene hijo izquierdo, así que es uno de los dos primeros casos.

Mete los precios 49, 12, 89, 24, 6, 159, 32 y quita el 12 (dos hijos), el 49 (la raíz, dos hijos) y el 70 (no está):

-12: [6, 24, 32, 49, 89, 159]
-49: [6, 24, 32, 89, 159]
-70: ninguno
raíz: 89

Más ejercicios

Precios en un rango. Escribe between(from, to), que devuelva en orden los precios de from a to, sin recorrer todo el árbol: no vayas a la izquierda desde un nodo menor que from, ni a la derecha desde uno mayor que to.
Lo mejor dentro del presupuesto. Escribe floor(budget): el precio más caro que no pase del presupuesto. Compáralo con floorKey en Java o GetViewBetween en C#.
Altura con recursión. Escribe height(node) como 1 más la mayor de las alturas de los dos hijos. Ejecútalo en la cadena de 1000 precios ordenados. ¿Qué pasa en Python? ¿Y con 100 000 precios en Java?

Test

Ponte a prueba

1. El árbol guarda los precios 49, 12, 89, 24, 6, 159 y 32. ¿En qué orden los da un recorrido en orden?49 12 6 24 32 89 15949 12 89 24 6 159 326 12 24 32 49 89 159

2. ¿Por qué una tabla hash no sirve para «todos los productos entre 20 € y 60 €» y un árbol sí?Porque una tabla hash es más lenta al buscarPorque el hash reparte los precios cercanos en cubetas al azar, mientras que el árbol los mantiene ordenadosLas dos sirven igual de bien

3. Un árbol binario de búsqueda corriente recibe 1000 precios en orden ascendente. ¿Cuántos niveles tiene?5001000Unos 10

4. ¿Qué es cierto de TreeMap en Java y SortedDictionary en C#?Los dos son árboles rojo-negro: la altura se mantiene en O(log n) con cualquier entradaSolo TreeMap está equilibradoLos dos son tablas hash con las claves ordenadas

Árbol binario de búsqueda

Cookies