Как восстановить BST из файла - PullRequest
Новая
       21

Как восстановить BST из файла

0 голосов
/ 11 февраля 2010

Моя программа на C ++ создает несбалансированный BST из пользовательского ввода и сохраняет его на диск. Это выполняется путем индексации каждого узла путем предварительного обхода и назначения каждому узлу уникального номера. Затем он выводит BST в файл. Это делается путем обхода предварительного заказа, а затем для каждого узла печати для сохранения значения данных, номера индекса левого потомка и номера индекса правого потомка.

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

Ответы [ 5 ]

1 голос
/ 11 февраля 2010

Если вы сохраните двоичное дерево поиска в качестве обхода предварительного заказа, то дерево, которое вы получите, просто вставив элементы по одному за раз, когда вы их считываете, будет тем же деревом, с которого вы начали. Это, конечно, потребовало бы O (n log n) времени. Если вы хотите сохранить внешние узлы (Null), тогда вы можете сделать что-то вроде следующего: 

ReadBSTPreOrder(node ** target) {

    node * n = readNode();
    *target = n;

    if (n == NULL) return;
    ReadBSTPreOrder(&node->left);
    ReadBSTPreOrder(&node->right);
}

Это дает дополнительное преимущество работы с двоичными деревьями, которые также не являются BST. Сохранение значений Null может быть одним битом, если вы хотите поэкспериментировать с представлением, но для этого следует использовать один байтовый тег для нулевого значения и другой тег для записи. Это также избавит вас от записи индексов.

1 голос
/ 11 февраля 2010

Предположим, вы знаете размер дерева (N) заранее. Может быть, это первая строка в файле. Если нет, то это легко адаптировать для динамического изменения размера вектора индекса. Обратите внимание, что это полупсевдокод: 

// Only needed while parsing the file
std::vector<Node*> index(N, NULL);

// We can always create the root node.
// This simplifies the while loop below.
index[0] = createNode(0);

while (!in.eof()) {
    int nodeID = -1, leftID = -1, rightID = -1;
    parseNode(in, &nodeID, &leftID, &rightID);

    // Guaranteed to be non-NULL
    Node* node = index[nodeID];

    // if leftID or rightID is -1, createNode()
    // will simply return NULL.
    index[leftID] = createNode(leftID);
    index[rightID] = createNode(rightID);

    node->setLeftChild(index[leftID]);
    node->setRightChild(index[rightID]);
}

Причина, по которой node = index[nodeID] гарантированно не равен NULL, заключается в индексации / записи / чтении предварительного заказа. Мы предварительно создали корневой узел в начале, а все остальные узлы создаются родителем как левый или правый дочерний элемент.

РЕДАКТИРОВАТЬ: я только что понял, что нам не нужен полный мастер-индекс. Нам нужно только хранить потенциальные правые дочерние узлы для расширения в стеке. Вот эта версия алгоритма: 

// Candidate right-child nodes to expand
std::stack<Node*> rightNodes;

// Pre-create the root node as "left child"
Node* left = createNode(0);

while (!in.eof()) {
    // We already know the next node. It is the previous
    // node's left child (or root), or the nearest
    // parent's right child.
    Node* node;

    if (left != NULL) {
        node = left;
    }
    else {
        node = rightNodes.top();
        rightNodes.pop();
    }

    parseLine(in, &nodeID, &leftID, &rightID);
    assert(node->ID() == nodeID);

    // if leftID or rightID is -1, createNode()
    // will simply return NULL.
    left = createNode(leftID);
    Node* right = createNode(rightID);

    node->setLeftChild(left);
    node->setRigthChild(right);

    if (right != NULL) {
        rightNodes.push(right);
    }
}
1 голос
/ 11 февраля 2010

Считать все узлы в память вместе с левым и правым дочерним индексом (скажем, хеш-таблица). Затем начните с корня (который является первым узлом в файле) и найдите левого и правого потомка по индексу из хеш-таблицы. Повторите тот же процесс для дочерних узлов в режиме DFS или BFS. Либо должно работать.

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

1 голос
/ 11 февраля 2010

Заказ будет проще.Вы можете просто поместить восстановленные узлы в стек, и дочерние элементы, которые будут связаны с родителем, всегда будут самыми верхними записями стека.

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

0 голосов
/ 11 февраля 2010

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

nodes_list = []
For each line i:
    Search for node i in nodes_list
    if(found):
        node_i = found_node
        node_i.set_value(line_value)
    else:
        node_i = new node(i)
        node_i.set_value(line_value)
        nodes_list.add(node_i)
    Search for line_left_node in nodes_list
    if(found):
        node_i.set_left_node(found_node)
    else:
        left_node = new node(line_left_node)
        node_i.set_left_node(left_node)
        nodes_list.add(left_node)
    Search for line_right_node in nodes_list
    if(found):
        node_i.set_right_node(found_node)
    else:
        right_node = new node(line_right_node)
        node_i.set_right_node(right_node)
        nodes_list.add(right_node)
...