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

Вы даже не можете посетить каждый узел настоящего честного дерева без циклов в пространстве 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: «деревья»), поскольку достаточно проверить для каждой пары узла и одного из его ближайших братьев и сестер, принадлежат ли они к одному и тому же connect, и эти пары можно перечислить в пространстве O (log n), используя стандартный рекурсивный спуск по дереву.

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

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

Узнали о посещении

Вам нужно будет переопределить структуру как таковую (я не буду указывать здесь указатели):

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), если все значения находятся на одной стороне дерева и каждое значение находится в цикле.

Учитывать глубину

При вставке в дерево можно было отслеживать максимальную глубину:

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

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

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

Алгоритм пытается сгладить двоичное дерево, перемещая все левое поддерево текущего узла над ним, делая его крайним правым узлом поддерева, а затем обновляя текущий узел, чтобы найти дальнейшие левые поддеревья во вновь обнаруженных узлах. Если мы знаем и левого потомка, и предшественника текущего узла, мы можем переместить все поддерево за несколько операций, аналогично вставке списка в другой. Такой ход сохраняет упорядоченную последовательность дерева и неизменно делает его более наклонным вправо.

Есть три случая в зависимости от локальной конфигурации узлов вокруг текущего: левый дочерний элемент такой же, как и предшественник, левый дочерний элемент отличается от предшественника или нет левого поддерева. Первый случай тривиален. Во втором случае требуется найти предшественника, в третьем случае нужно найти узел справа с левым поддеревом. Графическое представление помогает понять их.

В последних двух случаях мы можем зацикливаться. Поскольку мы просматриваем только список правильных дочерних элементов, мы можем использовать алгоритм обнаружения циклов Флойда, чтобы находить и сообщать о циклах. Рано или поздно каждый цикл превратится в такую ​​форму.

#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);

}

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

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

Однако это O (n) в памяти.

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

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

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

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

Хорошо, после дальнейших размышлений, я считаю, что нашел способ, при условии, что вы

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

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

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