Подтвердить что ты не робот

Эффективный алгоритм, чтобы определить, содержит ли предполагаемое двоичное дерево цикл?

Один из моих любимых вопросов -

В 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) пространстве, но я никогда не видел соответствующего эффективного алгоритма для этого случая.

4b9b3361

ОТВЕТЫ

Ответ 1

Вы не можете даже посещать каждый node реального, честного до бога, без цикла дерева в пространстве O (1), поэтому то, что вы просите, явно невозможно. (Трюки с изменением дерева по пути не являются O (1) пространством).

Если вы готовы рассмотреть алгоритмы на основе стека, то регулярное древовидное движение может быть легко модифицировано по линиям алгоритма Флойда.

Ответ 2

можно проверить в логарифмическом пространстве, если две вершины графа принадлежат одной и той же компоненте связности (Рейнгольд, Омер (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) с использованием стандартного рекурсивного спуска дерева.

Ответ 3

Если вы предполагаете, что цикл указывает на node на той же глубине или меньшей глубине в "дереве", вы можете сделать BFS (итеративную версию) двумя стеками, один для черепахи (x1) и один для зайца (скорость x2). В какой-то момент стек Hare будет либо пустым (без цикла), либо быть подмножеством стека черепах (найден цикл). Требуемое время - O (n k), а пространство O (lg n), где n - количество используемых узлов, а k - время, необходимое для проверки условия подмножества, которое может быть ограничено сверху lg (n). Заметим, что исходное предположение о цикле не ограничивает исходную задачу, так как предполагается, что это дерево, но для конечного числа дуг, которые образуют цикл с предыдущими узлами; ссылка на более глубокое node в дереве не образует цикл, а разрушает древовидную структуру.

Если можно предположить, что цикл указывает на предка, то условие подмножества можно изменить, проверяя, что оба стека равны, что быстрее.

Ответ 4

На первый взгляд вы можете видеть, что эта проблема будет решена путем недетерминированного применения алгоритма Флойда. Итак, что произойдет, если мы применим Floyd по-разветвленному?

Ну, мы можем использовать Floyd из базы node, а затем добавить дополнительный Floyd в каждую ветку. Поэтому для каждого конечного пути мы имеем экземпляр алгоритма Флойда, который заканчивается там. И если цикл когда-либо возникает, есть черепаха, которая ДОЛЖНА иметь соответствующего зайца, преследующего его. Таким образом, алгоритм заканчивается. (и в качестве побочного эффекта каждый терминал node достигается только одной парой зайцев/черепах, поэтому происходит O (n) посещений и, следовательно, время O (n). (храните узлы, которые были разветвлены, t увеличивает порядок памяти и предотвращает выбросы памяти в случае циклов) Кроме того, это делает память таким же, как и количество терминальных узлов. Количество конечных узлов равно O (log n), но O (n) в худшем случае.

TL; DR: применяйте Floyd и ветку каждый раз, когда у вас есть выбор:
время: O (n)
пространство: O (log n)

Ответ 5

Посетил 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). Это сделало бы лучше на недействительных деревьях.

Ответ 6

Как сказал Карл по определению, "Дерево" не содержит циклов. Но все же я получаю дух, в котором задается вопрос. Зачем вам нужны фантастические алгоритмы для обнаружения цикла на любом графике. Вы можете просто запустить BFS или DFS, и если вы посещаете уже посещенный node, это подразумевает цикл. Это будет выполняться в O (n) времени, но сложность пространства также O (n), не знаю, можно ли это уменьшить.

Ответ 7

Как упоминалось ChingPing, простая DFS должна сделать трюк. Вам нужно будет пометить каждый node как посещенный (необходимо выполнить некоторое сопоставление из ссылки node в Integer), и если повторная попытка будет предпринята на уже посещенном Node, это означает, что есть цикл.

Это O (n) в памяти, хотя.

Ответ 8

Я не верю, что существует алгоритм для ходьбы по дереву с меньшим, чем O (N) пространством. И для двоичного дерева (якобы) он не требует больше пространства/времени (в терминах "порядок" ) для обнаружения циклов, чем для того, чтобы ходить по дереву. Я считаю, что DFS будет ходить по дереву в O (N) времени, поэтому, возможно, O (N) является пределом в обеих измерениях.

Ответ 9

Хорошо после того, как я подумал, я считаю, что нашел способ, если вы

  • заранее знать количество узлов
  • может вносить изменения в двоичное дерево

Основная идея состоит в том, чтобы пересечь дерево с помощью Morris inorder tree traversal и подсчитать количество посещенных узлов как на этапе посещения, так и отдельные фазы поиска предшественника. Если какое-либо из них превышает количество узлов, у вас определенно есть цикл. Если у вас нет цикла, то это эквивалентно простому обходу Морриса, и ваше двоичное дерево будет восстановлено.

Я не уверен, что это возможно, не зная количества узлов заранее. Подумайте об этом больше.

Ответ 10

Удалось это сделать правильно!

  • Время выполнения: O (n). Я подозреваю, что он проходит через край не более постоянного количества раз. Нет формальных доказательств.
  • Пространство: O (1). Сохраняет только несколько узлов. Не создает новые узлы или ребра, только переупорядочивает их.
  • Разрушительный: Да. Он сглаживает дерево, каждый node имеет преемника inorder в качестве его правого дочернего элемента, а null - как левый.

Алгоритм пытается сгладить двоичное дерево, перемещая все левое поддерево текущего 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);

}