Iteración sobre un árbol binario con O (1) espacio auxiliar

¿Es posible iterar sobre un árbol binario en O (1) espacio auxiliar (sin usar una stack, cola, etc.) o se ha demostrado que esto es imposible? Si es posible, ¿cómo se puede hacer?

Editar: Las respuestas que obtuve sobre esto es posible si hay punteros a los nodos padres son interesantes y no sabía que esto podría hacerse, pero dependiendo de cómo lo mires, puede ser O (n) auxiliar espacio. Además, en mi caso de uso práctico, no hay punteros para los nodos principales. A partir de ahora, asum esto al responder.

Caray, tendré que escribirlo de Knuth. Esta solución es de Joseph M. Morris [ Inf. Proc. Letters 9 (1979), 197-200]. Por lo que puedo decir, se ejecuta en el tiempo O (NlogN).

static void VisitInO1Memory (Node root, Action preorderVisitor) { Node parent = root ; Node right = null ; Node curr ; while (parent != null) { curr = parent.left ; if (curr != null) { // search for thread while (curr != right && curr.right != null) curr = curr.right ; if (curr != right) { // insert thread assert curr.right == null ; curr.right = parent ; preorderVisitor (parent) ; parent = parent.left ; continue ; } else // remove thread, left subtree of P already traversed // this restres the node to original state curr.right = null ; } else preorderVisitor (parent) ; right = parent ; parent = parent.right ; } } class Node { public Node left ; public Node right ; } 

Es posible si tiene un enlace al padre en cada niño. Cuando encuentre un niño, visite el subárbol izquierdo. Cuando regrese revise para ver si es el hijo izquierdo de su padre. Si es así, visita el subárbol correcto. De lo contrario, sigue subiendo hasta que seas el niño de la izquierda o hasta que llegues a la raíz del árbol.

En este ejemplo, el tamaño de la stack permanece constante, por lo que no se consume memoria adicional. Por supuesto, como Mehrdad señaló, los enlaces a los padres se pueden considerar O (n) espacio, pero esto es más una propiedad del árbol que una propiedad del algoritmo.

Si no le importa el orden en que recorre el árbol, puede asignar un mapeo integral a los nodos donde la raíz es 1, los secundarios de la raíz son 2 y 3, los hijos de esos son 4, 5, 6, 7, etc. Luego recorre cada fila del árbol al incrementar un contador y acceder a ese nodo por su valor numérico. Puede realizar un seguimiento del elemento hijo más alto posible y detener el ciclo cuando su contador lo pase. En términos de tiempo, este es un algoritmo extremadamente ineficiente, pero creo que toma O (1) espacio.

(Tomé prestada la idea de numerar de montones. Si tienes el nodo N, puedes encontrar los niños en 2N y 2N + 1. Puedes trabajar hacia atrás desde este número para encontrar el padre de un niño).

Aquí hay un ejemplo de este algoritmo en acción en C. Observe que no hay malloc excepto para la creación del árbol, y que no hay funciones recursivas, lo que significa que la stack ocupa espacio constante:

 #include  #include  typedef struct tree { int value; struct tree *left, *right; } tree; tree *maketree(int value, tree *left, tree *right) { tree *ret = malloc(sizeof(tree)); ret->value = value; ret->left = left; ret->right = right; return ret; } int nextstep(int current, int desired) { while (desired > 2*current+1) desired /= 2; return desired % 2; } tree *seek(tree *root, int desired) { int currentid; currentid = 1; while (currentid != desired) { if (nextstep(currentid, desired)) if (root->right) { currentid = 2*currentid+1; root = root->right; } else return NULL; else if (root->left) { currentid = 2*currentid; root = root->left; } else return NULL; } return root; } void traverse(tree *root) { int counter; counter = 1; /* main loop counter */ /* next = maximum id of next child; if we pass this, we're done */ int next; next = 1; tree *current; while (next >= counter) { current = seek(root, counter); if (current) { if (current->left || current->right) next = 2*counter+1; /* printing to show we've been here */ printf("%i\n", current->value); } counter++; } } int main() { tree *root1 = maketree(1, maketree(2, maketree(3, NULL, NULL), maketree(4, NULL, NULL)), maketree(5, maketree(6, NULL, NULL), maketree(7, NULL, NULL))); tree *root2 = maketree(1, maketree(2, maketree(3, maketree(4, NULL, NULL), NULL), NULL), NULL); tree *root3 = maketree(1, NULL, maketree(2, NULL, maketree(3, NULL, maketree(4, NULL, NULL)))); printf("doing root1:\n"); traverse(root1); printf("\ndoing root2:\n"); traverse(root2); printf("\ndoing root3:\n"); traverse(root3); } 

Me disculpo por la calidad del código, esto es en gran medida una prueba de concepto. Además, el tiempo de ejecución de este algoritmo no es ideal, ya que hace mucho trabajo para compensar el hecho de no poder mantener ninguna información de estado. En el lado positivo, esto se ajusta a la factura de un algoritmo de espacio O (1) para acceder, en cualquier orden, a los elementos del árbol sin necesidad de enlaces padre a hijo o modificar la estructura del árbol.

Puedes hacerlo destructivamente, desvinculándote de cada hoja sobre la marcha. Esto puede ser aplicable en ciertas situaciones, es decir, cuando ya no necesita el árbol.

Por extensión, podrías construir otro árbol binario mientras destruyes el primero. Necesitará un poco de microgestión de memoria para asegurarse de que la memoria pico nunca exceda el tamaño del árbol original y quizás un poco de constante. Sin embargo, esto probablemente tendría un poco de sobrecarga de computación.

EDITAR: ¡ Hay una manera! Puede usar los nodos para iluminar el camino de vuelta al árbol invirtiéndolos temporalmente. Cuando visita un nodo, apunta su puntero left-child a su elemento primario, su apuntador right-child a la última vez que tomó un giro a la derecha en su ruta (que se encuentra en el puntero right-child en este momento) ), y almacenar sus hijos reales ya sea en el puntero del right-child del ahora redundante padre o en su estado transversal. el siguiente puntero del left-child visitado por los niños. Debe mantener algunos punteros al nodo actual y sus proximidades, pero nada “no local”. Cuando vuelves al árbol, inviertes el proceso.

Espero poder aclarar esto de alguna manera; esto es solo un boceto. Tendrás que buscarlo en algún lado (estoy seguro de que esto se menciona en algún lugar de El arte de la progtwigción de computadoras).

Para preservar el árbol y solo usar el espacio O (1), es posible si …

  • Cada nodo tiene un tamaño fijo.
  • El árbol completo está en una parte contigua de la memoria (es decir, una matriz)
  • No iteras sobre el árbol, simplemente iteras sobre la matriz

O si destruyes el árbol mientras lo procesas …:

  • A @Svante se le ocurrió esta idea, pero quería expandirme sobre cómo un poco, usando un enfoque destructivo.
  • ¿Cómo? Puede continuar tomando el nodo hoja más a la izquierda en un árbol (para (;;) nodo = nodo-> izquierda, etc., luego procesarlo y luego eliminarlo. Si el nodo situado más a la izquierda del árbol no es un nodo hoja , entonces procesa y elimina el nodo de la hoja más a la izquierda del nodo derecho. Si un nodo derecho no tiene hijos, entonces lo procesa y lo elimina.

Formas de que no funcionaría …

Si usa la recursión usará una stack implícitamente. Para algunos algoritmos (no para este problema) la recursividad de cola le permitiría usar recursividad y tener O (1) espacio, pero dado que cualquier nodo en particular puede tener varios hijos, y por lo tanto hay trabajo por hacer después de la llamada recursiva, O (1 ) la recursividad de la cola del espacio no es posible.

Podría intentar abordar el problema de 1 nivel a la vez, pero no hay forma de acceder a los nodos de un nivel arbitrario sin espacio auxiliar (implícito o explícito). Por ejemplo, puede recurse para encontrar el nodo que desea, pero luego toma el espacio de stack implícito. O puede almacenar todos sus nodos en otra estructura de datos por nivel, pero eso también requiere espacio adicional.

Los punteros desde los nodos hasta sus ancestros se pueden obtener sin (bueno, dos bits por nodo) almacenamiento adicional usando una estructura llamada árbol enhebrado. En un árbol enhebrado, los enlaces nulos están representados por un bit de estado en lugar de un puntero nulo. Luego, puede reemplazar los enlaces nulos con punteros a otros nodos: los enlaces a la izquierda apuntan al nodo sucesor en un recorrido en sentido contrario, y los enlaces a la derecha al predecesor. Aquí hay un diagtwig Unicode pesado (X representa un nodo de cabecera usado para controlar el árbol):

                                          ╭─┬────────────────────────────────────────╮
    ╭───────────────────────── ▶ ┏━━━┯━━━┯━━ ▼ ┓│ │
    │ ╭─╂─ │ X │ │ │ 
    │ ▼ ┗━━━┷━━━┷━━━┛ │
    │ ┏━━━┯━━━┯━━━┓ │
    │ ╭────╂─ │ │ │
    │ ▼ ┗━━━┷━━━┷━━━┛ │ │    
    │ ┏━━━┯━━━┯━━━┓ ▲ │ ┏━━━┯━━━┯━━━┓ │
    │ ╭─╂─ │ B │ │ │ │ │ │
    │ ▼ ┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛ ▼ ┗━━━┷━━━┷━━━┛ ▼ │  
    │┏━━━┯━━━┯━━━┓ ▲ │ ┏━━━┯━━━┯━━━┓ ▲ │
    ╰╂─ │ D │ │ │ │ │ │ │ │ │ │ 
     ┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛ ▼ │ ▼ ┗━━━┷━━━┷━━━┛ ▼ │
                                     ▲ ┏━━━┯━━━┯━━━┓ │ ┏━━━┯━━━┯━━━┓ ▲ ▲
                                     ╰─╂─ │ G │ │ │ J │ │ │ J │ ─╂╯
                                       ┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛

Una vez que tienes la estructura, hacer un recorrido inorden es muy, muy fácil:

 Inorder-Successor ( p )
     p apunta a un nodo.  Esta rutina encuentra el sucesor de p en 
      un recorrido inorden y devuelve un puntero a ese nodo

     qp .right
     Si p .rtag = 0 Entonces
         Mientras q .ltag = 0 Do
             qq .left
         Termine mientras
     Terminara si

     Retorno q
    

Se puede encontrar mucha más información sobre árboles enhebrados en Art of Computer Programming Ch.2 §3.1 o esparcidos por Internet.

Puede lograr esto si los nodos tienen indicadores para sus padres. Cuando camina de nuevo por el árbol (usando los punteros principales), también pasa el nodo del que proviene. Si el nodo del que proviene es el hijo izquierdo del nodo en el que se encuentra ahora, atraviesa al niño correcto. De lo contrario, volverás a su padre.

EDITAR en respuesta a la edición en la pregunta: si desea iterar a través del árbol completo, entonces esto no es posible. Para subir de nuevo al árbol, necesitas saber a dónde ir. Sin embargo, si solo desea iterar a través de una única ruta en el árbol, esto se puede lograr en O (1) espacio adicional. Simplemente itere por el árbol usando un ciclo while, manteniendo un solo puntero al nodo actual. Continúe por el árbol hasta que encuentre el nodo que desea o golpee un nodo hoja.

EDITAR: Aquí está el código para el primer algoritmo (verifique la función iterate_constant_space () y compare con los resultados de la función iterate () estándar):

 #include  #include  using namespace std; /* Implementation of a binary search tree. Nodes are ordered by key, but also * store some data. */ struct BinarySearchTree { int key; // they key by which nodes are ordered string data; // the data stored in nodes BinarySearchTree *parent, *left, *right; // parent, left and right subtrees /* Initialise the root */ BinarySearchTree(int k, string d, BinarySearchTree *p = NULL) : key(k), data(d), parent(p), left(NULL), right(NULL) {}; /* Insert some data */ void insert(int k, string d); /* Searches for a node with the given key. Returns the corresponding data * if found, otherwise returns None.""" */ string search(int k); void iterate(); void iterate_constant_space(); void visit(); }; void BinarySearchTree::insert(int k, string d) { if (k < = key) { // Insert into left subtree if (left == NULL) // Left subtree doesn't exist yet, create it left = new BinarySearchTree(k, d, this); else // Left subtree exists, insert into it left->insert(k, d); } else { // Insert into right subtree, similar to above if (right == NULL) right = new BinarySearchTree(k, d, this); else right->insert(k, d); } } string BinarySearchTree::search(int k) { if (k == key) // Key is in this node return data; else if (k < key && left) // Key would be in left subtree, which exists return left->search(k); // Recursive search else if (k > key && right) return right->search(k); return "NULL"; } void BinarySearchTree::visit() { printf("Visiting node %d storing data %s\n", key, data.c_str()); } void BinarySearchTree::iterate() { visit(); if (left) left->iterate(); if (right) right->iterate(); } void BinarySearchTree::iterate_constant_space() { BinarySearchTree *current = this, *from = NULL; current->visit(); while (current != this || from == NULL) { while (current->left) { current = current->left; current->visit(); } if (current->right) { current = current->right; current->visit(); continue; } from = current; current = current->parent; if (from == current->left) { current = current->right; current->visit(); } else { while (from != current->left && current != this) { from = current; current = current->parent; } if (current == this && from == current->left && current->right) { current = current->right; current->visit(); } } } } int main() { BinarySearchTree tree(5, "five"); tree.insert(7, "seven"); tree.insert(9, "nine"); tree.insert(1, "one"); tree.insert(2, "two"); printf("%s\n", tree.search(3).c_str()); printf("%s\n", tree.search(1).c_str()); printf("%s\n", tree.search(9).c_str()); // Duplicate keys produce unexpected results tree.insert(7, "second seven"); printf("%s\n", tree.search(7).c_str()); printf("Normal iteration:\n"); tree.iterate(); printf("Constant space iteration:\n"); tree.iterate_constant_space(); } 

Las “estructuras de datos y sus algoritmos” de Harry Lewis y Larry Denenberg describen el recorrido de inversión de enlaces para el cruce constante del espacio de un árbol binario. Para esto, no necesita el puntero principal en cada nodo. El recorrido utiliza los punteros existentes en el árbol para almacenar la ruta de seguimiento posterior. Se necesitan 2-3 referencias de nodos adicionales. Además, un poco en cada nodo para realizar un seguimiento de la dirección transversal (hacia arriba o hacia abajo) a medida que avanzamos. En mi implementación de este algoritmo del libro, el perfil muestra que este recorrido tiene mucho menos tiempo de memoria / procesador. Una implementación en java está aquí .

http://en.wikipedia.org/wiki/XOR_linked_list

codifica tu nodo padre en los punteros de la hoja

Creo que no hay manera de que puedas hacer esto, ya que de alguna manera deberías encontrar los nodos donde lo dejaste en un camino e identificar que siempre necesitas O (altura) de espacio.

¿Es posible iterar sobre un árbol binario en O (1) espacio auxiliar?

 struct node { node * father, * right, * left; int value; }; 

Esta estructura te permitirá mover 1 paso en cualquier dirección a través del árbol binario.
¡Pero aún en iteración necesitas mantener el camino!