Блог

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

 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*amp;);

    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 amp;amp; Node->RightChild == NULL)
        return 1;
    else
        return CountLeaves(Node->LeftChild)   CountLeaves(Node->RightChild);
}
  

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

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

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

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

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

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

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

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

Чтобы подсчитать листья без рекурсии, используйте концепцию итератора, подобную той, которую STL использует для RB-дерева, лежащего в основе std::set и std::map … Создайте для себя функцию begin() and 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 (log N).