Árbol binario enhebrado
Los enlaces vacíos apuntan al sucesor o al predecesor. Sigue el recorrido en inorden saltando por los hilos, sin pila.
Visitados: —
1// Nodo<E>: E dato; Nodo<E> izq, der;2// boolean hiloIzq, hiloDer; (true: el enlace es un hilo)3public void inorden() {4 Nodo<E> act = masIzquierda(raiz);5 while (act != null) {6 visitar(act.dato);7 if (act.hiloDer)8 act = act.der; // hilo: salta al sucesor9 else10 act = masIzquierda(act.der); // baja al subárbol derecho11 }12}13 14private Nodo<E> masIzquierda(Nodo<E> n) {15 while (n != null && !n.hiloIzq)16 n = n.izq; // bajar por la izquierda17 return n;18}Empiezo buscando el nodo más a la izquierda: el menor.
Un árbol binario de n nodos tiene n + 1 enlaces a null. Un árbol enhebrado los aprovecha: el derecho apunta al sucesor en inorden y el izquierdo, al predecesor. Un bit por enlace indica si es un hijo o un hilo.
Así el recorrido en inorden no necesita recursión ni pila: el recursivo usaría una pila tan alta como el árbol (3), y aquí la memoria extra es constante.
En un árbol binario de n nodos hay n + 1 enlaces a null. Un árbol enhebrado los reutiliza como hilos: un enlace derecho vacío apunta al sucesor en inorden y uno izquierdo vacío, al predecesor. Cada nodo guarda además dos marcas que dicen si cada enlace es un hijo o un hilo.
Con los hilos, el recorrido en inorden no necesita recursión ni pila. Se empieza por el nodo más a la izquierda y, después de visitar cada nodo, si su enlace derecho es un hilo se salta por él, y si es un hijo se baja a ese subárbol hasta su nodo más a la izquierda.
Escribe los valores de un árbol de búsqueda o elige uno de ejemplo, y sigue el recorrido en el dibujo y en el código Java. El inorden inverso hace lo mismo al revés con los hilos izquierdos.
En el árbol de búsqueda con 50, 30, 70, 20, 40, 60 y 80, ¿a dónde apuntan los hilos derechos?
- El inorden es 20, 30, 40, 50, 60, 70, 80.
- Las hojas no tienen hijo derecho: 20 → 30, 40 → 50 y 60 → 70.
- 80 es el último: su hilo derecho es null.
- 30, 50 y 70 tienen hijo derecho real, así que no tienen hilo derecho.
20 → 30, 40 → 50, 60 → 70 y 80 → null
Preguntas frecuentes
¿Para qué sirve enhebrar un árbol?
Para recorrerlo en inorden sin pila y encontrar el sucesor o el predecesor de un nodo sin volver a la raíz. Aprovecha enlaces que de otro modo estarían a null.
¿Cómo se sabe si un enlace es un hijo o un hilo?
Cada nodo lleva dos booleanos, hiloIzq e hiloDer. Sin ellos no se podría distinguir un hijo de un hilo, porque los dos son referencias a nodos.
¿Cuánto cuesta el recorrido en inorden de un árbol enhebrado?
O(n): cada enlace se sigue como mucho una vez. La memoria extra es O(1), frente a O(h) de la versión recursiva, donde h es la altura del árbol.
¿Qué pasa con los hilos al insertar un nodo?
El nuevo nodo hereda un hilo de su padre y el padre pasa a tener un hijo real. Por ejemplo, un hijo derecho nuevo apunta con su hilo derecho al antiguo sucesor del padre y con el izquierdo, al padre.