Построить деревья бинарного поиска эффективно - PullRequest
Новая
       4

Построить деревья бинарного поиска эффективно

0 голосов
/ 23 апреля 2020

У меня уже есть какое-то решение проблемы:

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

, за исключением того, что я включите деревья с root минимальным и максимальным значением, но это не моя главная задача. Я хочу подчеркнуть правильное использование семантики перемещения и управления памятью в C ++ (в качестве учебного упражнения).

Мое решение: 

#include <vector>

struct Node{
    int value;
    Node *left = nullptr;
    Node *right = nullptr;
};

std::vector<Node*> createListNodes(int min, int max)
{
    // ordered vector with i.e. {0,1,2,3,4}
    Node *node = new Node;
    if (min == max)
    {
        node->value = min;
        return std::vector<Node*> {node}; // it is a leaf node
    }
    std::vector<Node*> alterantive{};
    for (int i=min; i<=max; i++)
    {
        auto left = createListNodes(min,i-1); // for the left side
        auto right = createListNodes(i+1,max); // for the left side
        if (left.size() == 0) // if node i has just one child and it is in the right
        {
            for (auto elem_right : right)
            {
                alterantive.emplace_back(new Node{i,nullptr,elem_right});
            }
        }
        else if (right.size() == 0) // if node i has just one child and it is in the left
        {
            for (auto elem_left : left)
            {   
                alterantive.emplace_back(new Node{i,elem_left,nullptr});
            }
        }
        for (auto elem_left : left)
        {
            for (auto elem_right : right)
            {
                alterantive.emplace_back(new Node{i,elem_left,elem_right});
            }
        }
    }
    return alterantive;

}

int main()
{
    int N = 4;
    std::vector<Node*> combinations = createListNodes(0, N);
}

Поэтому хотелось бы знать:

  1. Улучшения, которые я мог бы внести в свой базовый c дизайн, я бы предпочел пока не использовать умные указатели, а только сырые, чтобы сделать их более эффективными с точки зрения памяти (копируя меньшее количество значений с одной стороны на другую. ..)
  2. Общие улучшения в коде, хотя мой основной упор делается на управление памятью, утечки памяти ...
...