Para optimizar la sobrecarga de espacio total para un solo recorrido cuando los nodos carecen de punteros principales, sin pasar iteradores por valor, a expensas de mantener el árbol bloqueado durante su duración, mantenga una pila. La pila se agrega descendiendo la rama izquierda, empujando a medida que avanza. Inicialice su iterador haciendo eso comenzando en el nodo raíz tge. Al obtener el siguiente, devuelva la parte superior de la pila, revísela y agregue comenzando por su hijo derecho. Termine cuando la pila esté vacía. La sobrecarga de espacio es proporcional a la profundidad del árbol para cada recorrido simultáneo, que es el tamaño del árbol en el caso degenerado, aunque en el mundo real debería usar una variante de árbol BS equilibrada, generalmente un árbol rojo-negro.
Para permitir modificaciones en el árbol, excepto en los nodos a los que se hace referencia, permita pasar iteradores por valor a bajo costo y admita múltiples iteradores paralelos para que su iterador sea un puntero de nodo e incluya un puntero principal en cada nodo. Con un hijo derecho, el siguiente nodo es su descendiente más a la izquierda. De lo contrario, es el primer antepasado a la derecha donde el puntero izquierdo del antepasado se refiere a su hijo. Comience en el descendiente más a la izquierda de la raíz y termine cuando presione un puntero NULL padre buscando el antepasado correcto.
Empujar todo el árbol con un recorrido de orden inverso tiene la mayor sobrecarga en el caso promedio, que se multiplica por el número de recorridos simultáneos, y no puede mutar el árbol mientras se itera sobre él.
- ¿Qué es el mapa de bits? ¿Dónde lo usamos?
- ¿Es razonable delegar decisiones importantes sobre algoritmos?
- ¿Qué algoritmo se usa para detectar "No más interruptores posibles, barajar" en la saga Candy Crush?
- ¿Qué es un algoritmo de CTA?
- ¿Qué algoritmo usa Facebook para mostrar la lista de amigos en la página de perfil?
