algorithm - recorrido - Algoritmo eficiente para determinar si un supuesto árbol binario contiene un ciclo?
recorrido de arboles binarios ejercicios resueltos (10)
Una de mis preguntas favoritas de la entrevista es
En el tiempo O (n) y el espacio O (1), determine si una lista vinculada contiene un ciclo.
Esto se puede hacer usando el algoritmo de búsqueda de ciclos de Floyd .
Mi pregunta es si es posible obtener tan buenas garantías de tiempo y espacio al intentar detectar si un árbol binario contiene un ciclo. Es decir, si alguien te da una definición de struct largo de las líneas de
struct node {
node* left;
node* right;
};
¿Con qué eficiencia puede verificar que la estructura dada sea de hecho un árbol binario y no, digamos, un DAG o una gráfica que contenga un ciclo?
¿Existe un algoritmo que, dada la raíz de un árbol binario, pueda determinar si ese árbol contiene un ciclo en el tiempo O (n) y mejor que el espacio O (n)? Claramente, esto podría hacerse con un DFS o BFS estándar, pero esto requiere espacio O (n). ¿Se puede hacer en el espacio O (√n)? O (log n) espacio? O (el santo grial) en solo O (1) espacio? Tengo curiosidad porque en el caso de una lista enlazada, esto se puede hacer en el espacio O (1), pero nunca he visto un algoritmo correspondientemente eficiente para este caso.
A primera vista, puede ver que este problema se resolvería con una aplicación no determinista del algoritmo de Floyd. Entonces, ¿qué sucede si aplicamos Floyd''s de forma dividida y ramificada?
Bueno, podemos usar Floyd''s desde el nodo base y luego agregar un Floyd''s adicional en cada rama. Así que para cada ruta de terminal tenemos una instancia del algoritmo de Floyd que termina allí. Y si alguna vez surge un ciclo, hay una tortuga que DEBE tener una liebre correspondiente que lo persiga. Así termina el algoritmo. (y como efecto secundario, a cada nodo terminal solo se llega mediante un par de liebre / tortuga, por lo que hay O (n) visitas y, por lo tanto, O (n) tiempo (almacenar los nodos que se han ramificado, esto no aumenta el orden de magnitud de la memoria y evita las explosiones de memoria en el caso de los ciclos) Además, al hacer esto se asegura que la huella de la memoria sea la misma que la cantidad de nodos terminales. La cantidad de nodos terminales es O (log n) pero O (n) en el peor caso.
TL; DR: aplique Floyd''s y sucursal cada vez que tenga la opción de hacer:
tiempo en)
espacio: O (log n)
Como dijo Karl por definición, un "Árbol" está libre de ciclos. Pero todavía me llega el espíritu con el que se hace la pregunta. ¿Por qué necesitas algoritmos sofisticados para detectar ciclos en cualquier gráfico? Simplemente puede ejecutar un BFS o DFS y si visita un nodo que ya está visitado, esto implica un ciclo. Esto se ejecutará en tiempo O (n), pero la complejidad del espacio también es O (n), no sé si se puede reducir.
Como lo mencionó ChingPing, un simple DFS debería hacer el truco. Necesitaría marcar cada nodo como visitado (necesita hacer un mapeo de Referencia de nodo a entero) y si se intenta un reingreso en un nodo ya visitado, eso significa que hay un ciclo.
Sin embargo, esto es O (n) en la memoria.
De acuerdo, después de pensarlo más, creo que encontré una manera, siempre que
- saber el número de nodos por adelantado
- Se pueden hacer modificaciones al arbol binario.
La idea básica es atravesar el árbol con Morris para ordenar el recorrido del árbol y contar el número de nodos visitados, tanto en la fase de visita como en las fases de búsqueda de predecesores individuales. Si alguno de estos supera el número de nodos, definitivamente tiene un ciclo. Si no tiene un ciclo, entonces es equivalente al recorrido de Morris normal y su árbol binario se restaurará.
No estoy seguro si es posible sin conocer la cantidad de nodos de antemano. Lo pensaré más.
Ni siquiera puede visitar cada nodo de un árbol real, honesto a dios, sin ciclo en el espacio O (1), por lo que lo que está pidiendo es claramente imposible. (Los trucos con la modificación de un árbol en el camino no son O (1) espacio).
Si está dispuesto a considerar algoritmos basados en la pila, entonces una caminata de árbol regular se puede modificar fácilmente siguiendo las líneas del algoritmo de Floyd.
No creo que exista un algoritmo para caminar un árbol con menos de O (N) espacio. Y, para un árbol binario (supuestamente), no se necesita más espacio / tiempo (en términos de "orden") para detectar los ciclos que para caminar el árbol. Creo que DFS caminará un árbol en O (N), por lo que probablemente O (N) sea el límite en ambas medidas.
Si asume que el ciclo apunta a un nodo a la misma profundidad o menor profundidad en el "árbol", entonces puede hacer un BFS (versión iterativa) con dos pilas, una para la tortuga (x1) y otra para la liebre ( velocidad x2). En algún momento, la pila de la liebre estará vacía (sin ciclo) o será un subconjunto de la pila de la tortuga (se encontró un ciclo). El tiempo requerido es O (nk), y el espacio es O (lg n) donde n es el número de nodos utilizados, y k el tiempo requerido para verificar la condición del subconjunto que puede estar delimitado por lg (n). Tenga en cuenta que la suposición inicial sobre el ciclo no limita el problema original, ya que se supone que es un árbol, pero para un número finito de arcos que forman un ciclo con nodos anteriores; un enlace a un nodo más profundo en el árbol no formará un ciclo sino que destruirá la estructura del árbol.
Si se puede suponer además que el ciclo apunta a un antepasado, entonces, la condición del subconjunto se puede cambiar al verificar que ambas pilas sean iguales, lo que es más rápido.
es posible probar en el espacio logarítmico si dos vértices de una gráfica pertenecen al mismo componente conectado (Reingold, Omer (2008), "Conectividad no dirigida en el espacio de registro", Diario de la ACM 55 (4): Artículo 17, 24 páginas, doi: 10.1145 / 1391289.1391291). Un componente conectado es cíclico; por lo tanto, si puede encontrar dos vértices en un gráfico que pertenecen al mismo componente conectado, hay un ciclo en el gráfico. Reingold publicó el algoritmo 26 años después de que se planteara por primera vez la cuestión de su existencia (ver http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29 ). Tener un algoritmo de espacio O (1) suena poco probable dado que tomó 25 años encontrar una solución de espacio de registro. Tenga en cuenta que elegir dos vértices de un gráfico y preguntar si pertenecen a un ciclo equivale a preguntar si pertenecen a un componente conectado.
Este algoritmo se puede extender a una solución de espacio de registro para gráficos con grado 2 (OP: "árboles"), ya que es suficiente para verificar cada par de un nodo y uno de sus hermanos inmediatos si pertenecen al mismo conecte el componente, y estos pares se pueden enumerar en el espacio O (log n) utilizando el descenso de árbol recursivo estándar.
Se las arregló para hacerlo bien!
- Tiempo de ejecución: O (n). Sospecho que pasa a través de un borde como máximo una cantidad constante de veces. No hay pruebas formales.
- Espacio: O (1). Solo almacena unos pocos nodos. No crea nuevos nodos o bordes, solo los reorganiza.
- Destructivo: si. Aplana el árbol, cada nodo tiene el sucesor inorder como su hijo derecho, y nulo como el izquierdo.
El algoritmo intenta aplanar el árbol binario moviendo todo el subárbol izquierdo del nodo actual hacia arriba, convirtiéndolo en el nodo más a la derecha del subárbol, y luego actualizando el nodo actual para encontrar más subárboles izquierdos en los nodos recién descubiertos. Si conocemos tanto al hijo izquierdo como al predecesor del nodo actual, podemos mover todo el subárbol en algunas operaciones, de manera similar a insertar una lista en otra. Tal movimiento conserva la secuencia en orden del árbol e invariablemente hace que el árbol esté más inclinado hacia la derecha.
Hay tres casos dependiendo de la configuración local de los nodos alrededor de la actual: el hijo izquierdo es el mismo que el predecesor, el hijo izquierdo es diferente del predecesor o no hay ningún subárbol izquierdo. El primer caso es trivial. El segundo caso requiere encontrar al predecesor, el tercer caso requiere encontrar un nodo a la derecha con un subárbol izquierdo. La representación gráfica ayuda a entenderlos.
En los dos últimos casos podemos ejecutar ciclos. Como solo recorremos una lista de los niños correctos, podemos usar el algoritmo de detección de ciclos de Floyd para encontrar e informar los bucles. Tarde o temprano, cada ciclo se rotará en tal forma.
#include <cstdio>
#include <iostream>
#include <queue>
#define null NULL
#define int32 int
using namespace std;
/**
* Binary tree node class
**/
template <class T>
class Node
{
public:
/* Public Attributes */
Node* left;
Node* right;
T value;
};
/**
* This exception is thrown when the flattener & cycle detector algorithm encounters a cycle
**/
class CycleException
{
public:
/* Public Constructors */
CycleException () {}
virtual ~CycleException () {}
};
/**
* Biny tree flattener and cycle detector class.
**/
template <class T>
class Flattener
{
public:
/* Public Constructors */
Flattener () :
root (null),
parent (null),
current (null),
top (null),
bottom (null),
turtle (null),
{}
virtual ~Flattener () {}
/* Public Methods */
/**
* This function flattens an alleged binary tree, throwing a new CycleException when encountering a cycle. Returns the root of the flattened tree.
**/
Node<T>* flatten (Node<T>* pRoot)
{
init(pRoot);
// Loop while there are left subtrees to process
while( findNodeWithLeftSubtree() ){
// We need to find the topmost and rightmost node of the subtree
findSubtree();
// Move the entire subtree above the current node
moveSubtree();
}
// There are no more left subtrees to process, we are finished, the tree does not contain cycles
return root;
}
protected:
/* Protected Methods */
void init (Node<T>* pRoot)
{
// Keep track of the root node so the tree is not lost
root = pRoot;
// Keep track of the parent of the current node since it is needed for insertions
parent = null;
// Keep track of the current node, obviously it is needed
current = root;
}
bool findNodeWithLeftSubtree ()
{
// Find a node with a left subtree using Floyd''s cycle detection algorithm
turtle = parent;
while( current->left == null and current->right != null ){
if( current == turtle ){
throw new CycleException();
}
parent = current;
current = current->right;
if( current->right != null ){
parent = current;
current = current->right;
}
if( turtle != null ){
turtle = turtle->right;
}else{
turtle = root;
}
}
return current->left != null;
}
void findSubtree ()
{
// Find the topmost node
top = current->left;
// The topmost and rightmost nodes are the same
if( top->right == null ){
bottom = top;
return;
}
// The rightmost node is buried in the right subtree of topmost node. Find it using Floyd''s cycle detection algorithm applied to right childs.
bottom = top->right;
turtle = top;
while( bottom->right != null ){
if( bottom == turtle ){
throw new CycleException();
}
bottom = bottom->right;
if( bottom->right != null ){
bottom = bottom->right;
}
turtle = turtle->right;
}
}
void moveSubtree ()
{
// Update root; if the current node is the root then the top is the new root
if( root == current ){
root = top;
}
// Add subtree below parent
if( parent != null ){
parent->right = top;
}
// Add current below subtree
bottom->right = current;
// Remove subtree from current
current->left = null;
// Update current; step up to process the top
current = top;
}
Node<T>* root;
Node<T>* parent;
Node<T>* current;
Node<T>* top;
Node<T>* bottom;
Node<T>* turtle;
private:
Flattener (Flattener&);
Flattener& operator = (Flattener&);
};
template <class T>
void traverseFlat (Node<T>* current)
{
while( current != null ){
cout << dec << current->value << " @ 0x" << hex << reinterpret_cast<int32>(current) << endl;
current = current->right;
}
}
template <class T>
Node<T>* makeCompleteBinaryTree (int32 maxNodes)
{
Node<T>* root = new Node<T>();
queue<Node<T>*> q;
q.push(root);
int32 nodes = 1;
while( nodes < maxNodes ){
Node<T>* node = q.front();
q.pop();
node->left = new Node<T>();
q.push(node->left);
nodes++;
if( nodes < maxNodes ){
node->right = new Node<T>();
q.push(node->right);
nodes++;
}
}
return root;
}
template <class T>
void inorderLabel (Node<T>* root)
{
int32 label = 0;
inorderLabel(root, label);
}
template <class T>
void inorderLabel (Node<T>* root, int32& label)
{
if( root == null ){
return;
}
inorderLabel(root->left, label);
root->value = label++;
inorderLabel(root->right, label);
}
int32 main (int32 argc, char* argv[])
{
if(argc||argv){}
typedef Node<int32> Node;
// Make binary tree and label it in-order
Node* root = makeCompleteBinaryTree<int32>(1 << 24);
inorderLabel(root);
// Try to flatten it
try{
Flattener<int32> F;
root = F.flatten(root);
}catch(CycleException*){
cout << "Oh noes, cycle detected!" << endl;
return 0;
}
// Traverse its flattened form
// traverseFlat(root);
}
Visitó Aware
Necesitarías redefinir la estructura como tal (voy a dejar los punteros fuera de esto):
class node {
node left;
node right;
bool visited = false;
};
Y use el siguiente algoritmo recursivo (obviamente, volver a trabajarlo para usar una pila personalizada si su árbol podría crecer lo suficiente):
bool validate(node value)
{
if (value.visited)
return (value.visited = false);
value.visited = true;
if (value.left != null && !validate(value.left))
return (value.visited = false);
if (value.right != null && !validate(value.right))
return (value.visited = false);
value.visited = false;
return true;
}
Comentarios: Técnicamente tiene espacio O (n); Debido al campo extra en la estructura. El peor de los casos sería también O (n + 1) si todos los valores están en un solo lado del árbol y todos los valores están en el ciclo.
Profundo consciente
Al insertarlo en el árbol, puede hacer un seguimiento de la profundidad máxima:
struct node {
node left;
node right;
};
global int maximumDepth = 0;
void insert(node item) { insert(root, item, 1); }
void insert(node parent, node item, int depth)
{
if (depth > maximumDepth)
maximumDepth = depth;
// Do your insertion magic, ensuring to pass in depth + 1 to any other insert() calls.
}
bool validate(node value, int depth)
{
if (depth > maximumDepth)
return false;
if (value.left != null && !validate(value.left, depth + 1))
return false;
if (value.right != null && !validate(value.right, depth + 1))
return false;
return true;
}
Comentarios: El espacio de almacenamiento es O (n + 1) porque estamos almacenando la profundidad en la pila (así como la profundidad máxima); El tiempo sigue siendo O (n + 1). Esto haría mejor en árboles inválidos.