Árboles

Un árbol es una estructura jerárquica: los nodos se conectan mediante aristas y siempre hay uno especial, la raíz, del que cuelga todo lo demás. Es la diferencia esencial con el grafo, que no tiene raíz ni jerarquía. Desde la raíz hay un único camino hasta cualquier otro nodo, así que un árbol no tiene ciclos.

• Raíz: el nodo del que cuelga el árbol. Es el único sin padre, y todo árbol no vacío tiene exactamente uno.
• Hoja: nodo sin hijos, es decir, el final de una rama.
• Nodo interno: el que no es hoja, porque tiene al menos un hijo.
• Subárbol: cualquier nodo con todo lo que cuelga de él es a su vez un árbol completo. Esa autosemejanza es lo que permite que casi todos los algoritmos sobre árboles sean recursivos.
• Árbol vacío: el que no tiene ningún nodo. No tiene niveles.

Estas cinco medidas se confunden con facilidad y son de las que más se preguntan. Dos parejas concentran casi todo el error: orden frente a grado, y profundidad frente a altura.

El orden es el máximo potencial y el grado es el máximo real. Un árbol de orden 5 cuyos nodos no pasen nunca de tres hijos tiene grado 3.

El nivel de un nodo es su distancia a la raíz contada por generaciones. La numeración admite dos convenios: empezar la raíz en nivel 0 o empezarla en nivel 1. Conviene fijarse en cuál usa el enunciado antes de contar.

Recorrer un árbol en profundidad es bajar por una rama hasta el fondo antes de pasar a la siguiente. El esquema es siempre recursivo y siempre visita las mismas tres cosas: la raíz del subárbol actual (R), su subárbol izquierdo (I) y su subárbol derecho (D). Lo único que cambia es en qué momento se atiende a la raíz, y de ahí salen los tres nombres.

Fijado el orden, la regla se aplica de nuevo en cada nodo al que se llega, no solo en la raíz del árbol. Ese es el punto donde falla todo el mundo al trazarlos a mano.

funcion inorden(nodo):
    si nodo = nulo: salir
    inorden(nodo.izquierdo)     // I
    visitar(nodo)               // R
    inorden(nodo.derecho)       // D

// Sobre este árbol:
//              50
//            /    \
//          30      70
//         /  \       \
//       20    40       80
//
// Preorden  (RID):  50, 30, 20, 40, 70, 80
// Inorden   (IRD):  20, 30, 40, 50, 70, 80
// Postorden (IDR):  20, 40, 30, 80, 70, 50

En preorden la raíz del árbol es siempre el primer elemento de la salida; en postorden es siempre el último. Con esos dos anclajes se descarta media pregunta de examen sin trazar nada.

El recorrido en anchura, o por niveles, no baja por una rama: visita todos los nodos de un nivel antes de pasar al siguiente. Es el contrapunto de los tres anteriores y se contrasta con ellos con frecuencia.

El detalle que conviene retener es la estructura auxiliar. Los recorridos en profundidad son recursivos y se apoyan, aunque sea de forma implícita, en una pila (la de llamadas). El recorrido en anchura se apoya en una cola: se saca un nodo, se visita y se encolan sus hijos.

funcion anchura(raiz):
    cola = [raiz]
    mientras cola no este vacia:
        nodo = dequeue(cola)
        visitar(nodo)
        si nodo.izquierdo != nulo: enqueue(cola, nodo.izquierdo)
        si nodo.derecho  != nulo: enqueue(cola, nodo.derecho)

// Sobre el mismo árbol del punto anterior:
// Anchura:  50, 30, 70, 20, 40, 80

Profundidad se implementa con pila (o recursión); anchura, con cola. Es la pregunta corta más repetida sobre recorridos.

Un árbol binario tiene orden 2: ningún nodo pasa de dos hijos. El árbol binario de búsqueda (ABB) añade una condición de orden: en todo nodo, lo que cuelga a su izquierda es menor que él y lo que cuelga a su derecha es mayor.

De esa condición salen sus dos propiedades útiles. La primera es que buscar consiste en comparar y bajar por un lado, descartando la otra mitad en cada paso. La segunda es que recorrerlo en inorden (IRD) devuelve todos los elementos ordenados de menor a mayor, lo cual es una consecuencia directa de la definición: primero se visita todo lo menor, luego el nodo, luego todo lo mayor.

El O(log n) del árbol binario de búsqueda solo se cumple si el árbol está equilibrado. Insertar claves ya ordenadas lo degenera en una lista y lo deja en O(n): esa es exactamente la razón de existir de los árboles autobalanceables.

Un árbol autobalanceable detecta por sí mismo cuándo se está desequilibrando y se recoloca. La herramienta para recolocarse son las rotaciones: reordenaciones locales de dos o tres nodos que cambian quién es el padre de quién sin alterar el orden de las claves.

El factor de equilibrio de un nodo es la diferencia entre la altura de su subárbol izquierdo y la de su subárbol derecho. Mientras ese valor se mantenga en −1, 0 o +1 en todos los nodos, el árbol se considera equilibrado; en cuanto se sale de ahí, se dispara una rotación.

• AVL: el clásico. Mantiene el factor de equilibrio en −1, 0 o +1 en todos los nodos, con lo que queda muy equilibrado y la búsqueda es rápida, a costa de rotar más a menudo.
• Árbol rojo-negro: admite más desequilibrio que el AVL a cambio de rotar menos, lo que lo hace preferible cuando hay muchas inserciones y borrados. Es una implementación habitual de conjuntos y diccionarios ordenados.
• Árbol AA: una variante simplificada del rojo-negro, con menos casos que tratar al reequilibrar.
• Árbol splay: no garantiza equilibrio, sino que lleva a la raíz el último elemento accedido. Así los elementos usados con frecuencia quedan siempre cerca.
• Árbol de Fibonacci: caso particular de AVL, el que tiene el menor número posible de nodos para una altura dada. Sirve para demostrar la peor forma admisible de un AVL.

Los árboles multicamino rompen el límite de dos hijos por nodo. El motivo no es teórico sino físico: en los gestores de bases de datos y en los sistemas de ficheros el coste dominante no son las comparaciones sino los accesos a disco, y cada nodo se corresponde con un bloque leído. Si en cada nodo caben muchas claves, el árbol es mucho menos alto y hacen falta muchas menos lecturas para llegar al dato.

El árbol B es la forma básica. Se define por su orden M, que es el número máximo de hijos por nodo, y está siempre equilibrado: todas las hojas quedan a la misma altura, porque el árbol crece por la raíz y no por las hojas. Sus claves se mantienen ordenadas dentro de cada nodo, y las inserciones y borrados se resuelven en tiempo logarítmico.

El árbol B+ es la variante que usan de hecho los índices de las bases de datos. Sus nodos internos guardan solo claves y punteros, sin datos, de modo que caben más claves por bloque y el árbol es aún más bajo. Todos los datos viven en las hojas, y las hojas están enlazadas entre sí, lo que permite recorrer un rango de valores seguido sin volver a subir por el árbol.

El árbol B* aprieta más la ocupación: su algoritmo de inserción reparte las claves con los nodos vecinos antes de dividir un nodo lleno, de manera que garantiza una ocupación mínima de dos tercios en lugar de la mitad. Sale un árbol más denso y con menos nodos desaprovechados.

El árbol B+ es el que hace rápidas las consultas por rango (fechas entre dos valores, importes mayores que uno dado), porque sus hojas están encadenadas y basta recorrerlas en línea.