algorithm language-agnostic tree memory-management binary-tree

algorithm - Iterando sobre un árbol binario con O(1) Espacio auxiliar



language-agnostic tree (10)

"Estructuras de datos y sus algoritmos", de Harry Lewis y Larry Denenberg, describen el recorrido de inversión de enlaces para el espacio constante de un árbol binario. Para ello no necesita puntero padre en cada nodo. El recorrido utiliza los punteros existentes en el árbol para almacenar la ruta para el seguimiento posterior. Se necesitan 2-3 referencias de nodo adicionales. Más un bit en cada nodo para realizar un seguimiento de la dirección de recorrido (arriba o 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á here .

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

Edición: las respuestas que recibí sobre este tema son posibles si hay punteros a los nodos principales son interesantes y no sabía que esto podría hacerse, pero según cómo se mire, eso puede ser O (n) auxiliar. espacio. Además, en mi caso de uso práctico, no hay punteros a los nodos principales. A partir de ahora, por favor, asuma esto al responder.

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

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

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

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

static void VisitInO1Memory (Node root, Action<Node> 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 restores the node to original state curr.right = null ; } else preorderVisitor (parent) ; right = parent ; parent = parent.right ; } } class Node { public Node left ; public Node right ; }

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

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

En este ejemplo, el tamaño de la pila permanece constante, por lo que no se consume memoria adicional. Por supuesto, como señaló Mehrdad, los enlaces a los padres pueden considerarse 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 atraviesa el árbol, podría asignar un mapeo integral a los nodos donde la raíz es 1, los hijos de la raíz son 2 y 3, los hijos de esos son 4, 5, 6, 7, etc. Luego, recorre cada fila del árbol incrementando un contador y accediendo a ese nodo por su valor numérico. Puede realizar un seguimiento del elemento secundario más alto posible y detener el bucle cuando su contador lo pasa. En cuanto al tiempo, este es un algoritmo extremadamente ineficiente, pero creo que ocupa espacio O (1).

(Tomé prestada la idea de numeración de los montones. Si tiene el nodo N, puede encontrar a los hijos en 2N y 2N + 1. Puede trabajar hacia atrás desde este número para encontrar al padre de un niño).

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

#include <stdio.h> #include <stdlib.h> 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); }

Pido disculpas 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 por 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 primarios o de modificación de la estructura del árbol.

Los punteros de los nodos a sus antepasados ​​se pueden obtener sin almacenamiento adicional (bueno, dos bits por nodo) mediante una estructura denominada árbol de subprocesos. En un árbol con hilos, los enlaces nulos se representan con un poco de estado en lugar de con un puntero nulo. Luego, puede reemplazar los enlaces nulos con punteros a otros nodos: los enlaces de la izquierda apuntan al nodo sucesor en un recorrido de orden, y los enlaces de la derecha al predecesor. Aquí hay un diagrama pesado de Unicode (X representa un nodo de encabezado usado para controlar el árbol):

╭─┬────────────────────────────────────────╮ ╭─────────────────────────▶┏━━━┯━━━┯━━▼┓│ │ │ ╭─╂─ │ X │ ─╂╯ │ │ ▼ ┗━━━┷━━━┷━━━┛ │ │ ┏━━━┯━━━┯━━━┓ │ │ ╭────╂─ │ A │ ─╂──╮ │ │ ▼ ┗━━━┷━━━┷━━━┛ │ │ │ ┏━━━┯━━━┯━━━┓ ▲ │ ┏━━━┯━━━┯━━━┓ │ │ ╭─╂─ │ B │ ─╂────┤ ├────────╂─ │ C │ ─╂───────╮ │ │ ▼ ┗━━━┷━━━┷━━━┛ │ ▼ ┗━━━┷━━━┷━━━┛ ▼ │ │┏━━━┯━━━┯━━━┓ ▲ │ ┏━━━┯━━━┯━━━┓ ▲ ┏━━━┯━━━┯━━━┓ │ ╰╂─ │ D │ ─╂─╯ ╰───╂ │ E │ ─╂╮ │ ╭╂─ │ F │ ─╂╮ │ ┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛▼ │ ▼┗━━━┷━━━┷━━━┛▼ │ ▲ ┏━━━┯━━━┯━━━┓ │ ┏━━━┯━━━┯━━━┓ ▲ ┏━━━┯━━━┯━━━┓│ ╰─╂─ │ G │ ╂──┴─╂─ │ H │ ─╂─┴─╂─ │ J │ ─╂╯ ┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛

Una vez que tenga la estructura, hacer un recorrido en orden es muy, muy fácil:

Inorder-Successor(p) p points to a node. This routine finds the successor of p in an inorder traversal and returns a pointer to that node q ← p.right If p.rtag = 0 Then While q.ltag = 0 Do q ← q.left End While End If Return q

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

Puedes hacerlo destructivamente, desvinculando cada hoja a medida que avanzas. Esto puede ser aplicable en ciertas situaciones, es decir, cuando ya no necesite más el árbol.

Por extensión, podrías construir otro árbol binario al destruir el primero. Necesitaría un poco de microgestión de memoria para asegurarse de que la memoria máxima nunca supere el tamaño del árbol original y quizás un poco constante. Sin embargo, esto probablemente tendría una gran sobrecarga informática.

EDITAR: ¡ Hay una manera! Puede usar los nodos para iluminar el camino de regreso al árbol invirtiéndolos temporalmente. Cuando visita un nodo, apunta su puntero left-child hacia su padre, y su puntero right-child hacia la última vez que giró a la derecha en su camino (que se encuentra en el puntero right-child en este momento). ), y almacene sus hijos reales, ya sea en el puntero right-child del padre ahora redundante o en su estado de cruce respectivamente. El siguiente puntero infantil de la left-child visitó. Debe mantener algunos punteros al nodo actual y sus alrededores, pero nada "no local". Cuando regresas al árbol, inviertes el proceso.

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

Puedes lograr esto si los nodos tienen punteros a sus padres. Cuando regresas al árbol (usando los punteros principales) también pasas el nodo del que vienes. Si el nodo del que viene es el hijo izquierdo del nodo en el que está ahora, atraviesa el hijo derecho. De lo contrario, volver a subir a su padre.

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

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

#include <cstdio> #include <string> 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(); }

Para conservar el árbol y solo usar el espacio O (1) es posible si ...

  • Cada nodo es un tamaño fijo.
  • Todo el árbol 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 un poco, utilizando un enfoque destructivo.
  • ¿Cómo? Puede continuar tomando el nodo más a la izquierda de un árbol (para (;;) node = node-> left etc ..., luego procesarlo y luego eliminarlo. Si el nodo más a la izquierda en el árbol no es un nodo de hoja , luego procesa y elimina el nodo más a la izquierda del nodo derecho. Si un nodo derecho no tiene hijos, entonces lo procesa y lo elimina.

Maneras en que no funcionaría ...

Si usas recursión usarás una pila implícitamente. Para algunos algoritmos (no para este problema) la recursión de la cola le permitiría usar la recursión 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 recursión de la cola del espacio no es posible.

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