Исключение Stackoverflow при прохождении BST - PullRequest
Новая
       20

Исключение Stackoverflow при прохождении BST

4 голосов
/ 10 ноября 2011

Я реализовал BST (дерево двоичного поиска) на основе ссылок для одного из моих назначений. Я написал весь свой класс, и все работает хорошо, но мое задание просит меня указать время выполнения для: 

a.  A sorted list of 50000, 75000, and 100000 items
b.  A random list of 50000, 75000, and 100000 items

Хорошо, я могу вставить числа, но также просит вызвать методы FindHeight() и CountLeaves() в дереве. Моя проблема в том, что я реализовал две функции, используя recursion. Поскольку у меня такой большой список номеров, я получаю исключение stackoverflow.

Вот мое определение класса: 

template <class TItem>
class BinarySearchTree
{
public:
    struct BinarySearchTreeNode
    {
    public:
        TItem Data;
        BinarySearchTreeNode* LeftChild;
        BinarySearchTreeNode* RightChild;
    };

    BinarySearchTreeNode* RootNode;

    BinarySearchTree();
    ~BinarySearchTree();

    void InsertItem(TItem);

    void PrintTree();
    void PrintTree(BinarySearchTreeNode*);

    void DeleteTree();
    void DeleteTree(BinarySearchTreeNode*&);

    int CountLeaves();
    int CountLeaves(BinarySearchTreeNode*);

    int FindHeight();
    int FindHeight(BinarySearchTreeNode*);

    int SingleParents();
    int SingleParents(BinarySearchTreeNode*);

    TItem FindMin();
    TItem FindMin(BinarySearchTreeNode*);

    TItem FindMax();
    TItem FindMax(BinarySearchTreeNode*);
};

FindHeight () Реализация 

template <class TItem>
int BinarySearchTree<TItem>::FindHeight()
{
    return FindHeight(RootNode);
}

template <class TItem>
int BinarySearchTree<TItem>::FindHeight(BinarySearchTreeNode* Node)
{
    if(Node == NULL)
        return 0;

    return 1 + max(FindHeight(Node->LeftChild), FindHeight(Node->RightChild));
}

Реализация CountLeaves () 

template <class TItem>
int BinarySearchTree<TItem>::CountLeaves()
{
    return CountLeaves(RootNode);
}

template <class TItem>
int BinarySearchTree<TItem>::CountLeaves(BinarySearchTreeNode* Node)
{
    if(Node == NULL)
        return 0;
    else if(Node->LeftChild == NULL && Node->RightChild == NULL)
        return 1;
    else
        return CountLeaves(Node->LeftChild) + CountLeaves(Node->RightChild);
}

Я пытался придумать, как я могу реализовать два метода без рекурсии, но я в полном замешательстве. У кого-нибудь есть идеи?

Ответы [ 5 ]

3 голосов
/ 10 ноября 2011

Рекурсия на дереве с 100 000 узлов не должна быть проблемой, если она сбалансирована.Глубина может быть только 17, что не будет использовать слишком много стека в показанных реализациях.(log2(100,000) = 16.61).Похоже, что код, который строит дерево, неправильно его уравновешивает.

2 голосов
/ 10 ноября 2011

Я нашел эту страницу очень поучительной, потому что она говорит о механике преобразования функции, использующей рекурсию, в функцию, использующую итерацию.

В ней также есть примеры, показывающие код.

1 голос
/ 10 ноября 2011

Периодически балансируйте свое дерево. Если ваше дерево получает стекопоток в FindHeight (), это означает, что ваше дерево way несбалансировано. Если дерево сбалансировано, оно должно иметь глубину около 20 узлов для 100000 элементов.

Самый простой (но довольно медленный) способ перебалансировки несбалансированного бинарного дерева - это выделить массив TItem, достаточно большой для хранения всех данных в дереве, вставить все свои данные в него в отсортированном порядке, и удалите все узлов. Затем перестройте дерево из массива рекурсивно. Корень - это узел посередине. root->left - середина левой половины, root->right - середина правой половины. Повторите рекурсивно. Это самый простой способ перебалансировки, но он медленный и временно требует много памяти. С другой стороны, вам нужно делать это только тогда, когда вы обнаружите, что дерево очень несбалансировано (глубина вставки превышает 100).

Другой (лучший) вариант - балансировать во время вставки. Наиболее интуитивный способ сделать это - отслеживать, сколько узлов находится под текущим узлом. Если правый дочерний узел имеет более чем в два раза больше дочерних узлов, чем левый дочерний элемент, «поверните» влево И наоборот. Есть инструкции, как сделать, чтобы дерево вращалось по всему интернету. Это делает вставки немного медленнее, но тогда у вас не будет случайных массивных срывов, которые создает первый вариант. С другой стороны, вы должны постоянно обновлять все «дочерние» значения во время поворота, что не тривиально.

1 голос
/ 10 ноября 2011

Может быть, вам нужно рассчитать это при выполнении вставки.Сохраните высоту узлов, то есть добавьте целочисленное поле, подобное высоте, в объекте Node.Также есть счетчики высоты и листьев для дерева.Когда вы вставляете узел, если его родитель является (был) листом, количество листьев не изменяется, но если нет, то увеличивается число листьев на 1. Кроме того, высота нового узла равна высоте родительского элемента + 1, следовательно, если это большечем текущая высота дерева, затем обновите его.Это домашнее задание, поэтому я не помогу с настоящим кодом

1 голос
/ 10 ноября 2011

Для подсчета листьев без рекурсии используйте концепцию итератора, подобную используемой в STL для дерева RB, лежащего в основе std::set и std::map ... Создайте для вас функции begin() и end()дерево, которое идентифицирует упорядоченный первый и последний узел (в этом случае самый левый узел, а затем самый правый узел).Затем создайте функцию с именем

BinarySearchTreeNode* increment(const BinarySearchTreeNode* current_node)

, которая для данного current_node будет возвращать указатель на следующий узел в дереве.Помните, что для реализации этой реализации вам понадобится дополнительный указатель parent в вашем типе node, чтобы помочь в процессе итерации.

Ваш алгоритм для increment() будет выглядеть примерно так:

  1. Проверьте, есть ли правый дочерний элемент для текущего узла.
  2. Если есть правый потомок, используйте цикл while, чтобы найти самый левый узел этого правого поддерева.Это будет «следующий» узел.В противном случае перейдите к шагу № 3.
  3. Если на текущем узле нет правого потомка, проверьте, является ли текущий узел левым потомком своего родительского узла.
  4. Еслишаг № 3 является истинным, тогда «следующий» узел является родительским узлом, так что вы можете остановиться на этом этапе, в противном случае перейти к следующему шагу.
  5. Если шаг № 3 был ложным, то текущий узелправый ребенок родителя.Таким образом, вам нужно будет продолжать переходить к следующему родительскому узлу, используя цикл while, пока вы не наткнетесь на узел, который является левым потомком его родительского узла.Родителем этого левого дочернего узла будет «следующий» узел, и вы можете остановиться.
  6. Наконец, если шаг № 5 возвращает вас к корню, то текущий узел является последним узлом вдерево, и итератор достиг конца дерева.

Наконец, вам понадобится функция bool leaf(const BinarySearchTreeNode* current_node), которая будет проверять, является ли данный узел листовым узлом.Таким образом, функция счетчика может просто выполнить итерацию по дереву и найти все конечные узлы, возвращая окончательный счет, как только он будет сделан.

Если вы хотите измерить максимальную глубину несбалансированного дерева без рекурсии, вы, вфункция insert() вашего дерева, необходимо отслеживать глубину, на которой был вставлен узел.Это может быть просто переменная вашего типа node, которая устанавливается при вставке узла в дерево.Затем вы можете перебрать все три и найти максимальную глубину листового узла.

Кстати, сложность этого метода, к сожалению, будет O (N) ... нигде не так хорошо, как O(журнал N).

...