Один из моих любимых вопросов -
В O (n) времени и O (1) пространстве определите, содержит ли связанный список цикл.
Это можно сделать, используя алгоритм поиска циклов Floyd.
Мой вопрос в том, можно ли получить такие хорошие временные и космические гарантии при попытке определить, содержит ли двоичное дерево цикл. То есть, если кто-то дает вам определение struct в строках
struct node {
node* left;
node* right;
};
Насколько эффективно вы можете проверить, что данная структура действительно представляет собой двоичное дерево, а не, скажем, DAG или график, содержащий цикл?
Есть ли алгоритм, который, учитывая корень двоичного дерева, может определить, содержит ли это дерево цикл в O (n) времени и лучше, чем O (n) пространство? Очевидно, что это можно сделать со стандартным DFS или BFS, но для этого требуется O (n) пространство. Можно ли это сделать в пространстве O (& radic; n)? O (log n)? Или (святой Грааль) только в O (1) пространстве? Мне любопытно, потому что в случае связанного списка это можно сделать в O (1) пространстве, но я никогда не видел соответствующего эффективного алгоритма для этого случая.
Вы не можете даже посещать каждый node реального, честного до бога, без цикла дерева в пространстве O (1), поэтому то, что вы просите, явно невозможно. (Трюки с изменением дерева по пути не являются O (1) пространством).
Если вы готовы рассмотреть алгоритмы на основе стека, то регулярное древовидное движение может быть легко модифицировано по линиям алгоритма Флойда.
можно проверить в логарифмическом пространстве, если две вершины графа принадлежат одной и той же компоненте связности (Рейнгольд, Омер (2008), "Непереадресованная связь в лог-пространстве", журнал ACM 55 (4): Статья 17, 24 страницы, doi: 10.1145/1391289.1391291). Связанный компонент является циклическим; поэтому, если вы можете найти две вершины в графе, принадлежащие одному и тому же компоненту связности, на графике есть цикл. Рейнгольд опубликовал алгоритм через 26 лет после того, как был задан вопрос о его существовании (см. http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29). Наличие O (1) пространственного алгоритма кажется маловероятным, учитывая, что потребовалось 25 лет, чтобы найти лог-пространство. Обратите внимание, что выбор двух вершин из графика и вопрос о том, принадлежат ли они циклу, эквивалентно запросу, принадлежат ли они к подключенному компоненту.
Этот алгоритм может быть расширен до логарифмического решения для графов с внеуровневой степенью 2 (OP: "деревья" ), так как достаточно проверить каждую пару a node и одного из ее непосредственных братьев и сестер, если они принадлежат одному компоненту соединения, и эти пары могут быть перечислены в пространстве O (log n) с использованием стандартного рекурсивного спуска дерева.
Если вы предполагаете, что цикл указывает на node на той же глубине или меньшей глубине в "дереве", вы можете сделать BFS (итеративную версию) двумя стеками, один для черепахи (x1) и один для зайца (скорость x2). В какой-то момент стек Hare будет либо пустым (без цикла), либо быть подмножеством стека черепах (найден цикл). Требуемое время - O (n k), а пространство O (lg n), где n - количество используемых узлов, а k - время, необходимое для проверки условия подмножества, которое может быть ограничено сверху lg (n). Заметим, что исходное предположение о цикле не ограничивает исходную задачу, так как предполагается, что это дерево, но для конечного числа дуг, которые образуют цикл с предыдущими узлами; ссылка на более глубокое node в дереве не образует цикл, а разрушает древовидную структуру.
Если можно предположить, что цикл указывает на предка, то условие подмножества можно изменить, проверяя, что оба стека равны, что быстрее.
На первый взгляд вы можете видеть, что эта проблема будет решена путем недетерминированного применения алгоритма Флойда. Итак, что произойдет, если мы применим Floyd по-разветвленному?
Ну, мы можем использовать Floyd из базы node, а затем добавить дополнительный Floyd в каждую ветку. Поэтому для каждого конечного пути мы имеем экземпляр алгоритма Флойда, который заканчивается там. И если цикл когда-либо возникает, есть черепаха, которая ДОЛЖНА иметь соответствующего зайца, преследующего его. Таким образом, алгоритм заканчивается. (и в качестве побочного эффекта каждый терминал node достигается только одной парой зайцев/черепах, поэтому происходит O (n) посещений и, следовательно, время O (n). (храните узлы, которые были разветвлены, t увеличивает порядок памяти и предотвращает выбросы памяти в случае циклов) Кроме того, это делает память таким же, как и количество терминальных узлов. Количество конечных узлов равно O (log n), но O (n) в худшем случае.
TL; DR: применяйте Floyd и ветку каждый раз, когда у вас есть выбор:
время: O (n)
пространство: O (log n)
Посетил Aware
Вам нужно будет переопределить структуру как таковую (я собираюсь оставить указатели из этого):
class node {
node left;
node right;
bool visited = false;
};
И используйте следующий рекурсивный алгоритм (явно переработав его для использования пользовательского стека, если ваше дерево может расти достаточно большим):
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;
}
Комментарии: Это технически имеет O (n) пространство; из-за дополнительного поля в структуре. В худшем случае для него также будет O (n + 1), если все значения находятся на одной стороне дерева, и каждое значение находится в цикле.
Глубина Aware
При вставке в дерево вы можете отслеживать максимальную глубину:
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;
}
Комментарии: Объем памяти O (n + 1), потому что мы храним глубину в стеке (а также максимальную глубину); время все еще O (n + 1). Это сделало бы лучше на недействительных деревьях.
Как сказал Карл по определению, "Дерево" не содержит циклов. Но все же я получаю дух, в котором задается вопрос. Зачем вам нужны фантастические алгоритмы для обнаружения цикла на любом графике. Вы можете просто запустить BFS или DFS, и если вы посещаете уже посещенный node, это подразумевает цикл. Это будет выполняться в O (n) времени, но сложность пространства также O (n), не знаю, можно ли это уменьшить.
Как упоминалось ChingPing, простая DFS должна сделать трюк. Вам нужно будет пометить каждый node как посещенный (необходимо выполнить некоторое сопоставление из ссылки node в Integer), и если повторная попытка будет предпринята на уже посещенном Node, это означает, что есть цикл.
Это O (n) в памяти, хотя.
Я не верю, что существует алгоритм для ходьбы по дереву с меньшим, чем O (N) пространством. И для двоичного дерева (якобы) он не требует больше пространства/времени (в терминах "порядок" ) для обнаружения циклов, чем для того, чтобы ходить по дереву. Я считаю, что DFS будет ходить по дереву в O (N) времени, поэтому, возможно, O (N) является пределом в обеих измерениях.
Хорошо после того, как я подумал, я считаю, что нашел способ, если вы
Основная идея состоит в том, чтобы пересечь дерево с помощью Morris inorder tree traversal и подсчитать количество посещенных узлов как на этапе посещения, так и отдельные фазы поиска предшественника. Если какое-либо из них превышает количество узлов, у вас определенно есть цикл. Если у вас нет цикла, то это эквивалентно простому обходу Морриса, и ваше двоичное дерево будет восстановлено.
Я не уверен, что это возможно, не зная количества узлов заранее. Подумайте об этом больше.
Удалось это сделать правильно!
Алгоритм пытается сгладить двоичное дерево, перемещая все левое поддерево текущего node до него, делая его самым правым node поддерева, затем обновляя текущий node, чтобы найти дальнейшие левые поддеревья в вновь открытых узлах. Если мы знаем как левого ребенка, так и предшественника текущего node, мы можем переместить все поддерево в несколько операций, аналогично вставке списка в другой. Такое перемещение сохраняет последовательность порядка в дереве и неизменно делает дерево более правильным наклонным.
В зависимости от локальной конфигурации узлов вокруг текущего есть три случая: левый ребенок совпадает с предшественником, левый ребенок отличается от предшественника или не имеет левого поддерева. Первый случай тривиален. Второй случай требует поиска предшественника, третий случай требует поиска node справа с левым поддеревом. Графическое представление помогает понять их.
В последних двух случаях мы можем столкнуться с циклами. Поскольку мы просматриваем только список правильных дочерних элементов, мы можем использовать алгоритм обнаружения цикла Floyd для поиска и представления циклов. Рано или поздно каждый цикл будет повернут в такую форму.
#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 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 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);
}