Создание структуры данных дерева - другой подход - PullRequest
Новая
       19

Создание структуры данных дерева - другой подход

0 голосов
/ 17 января 2012

За прошедшее время я задал много вопросов о древовидных структурах данных, но, похоже, я неправильно понял их в C ++.

В том, как я написал структуру данных, я не мог думатьединственного способа о том, как иметь «конечный» или «начальный» итератор.Как таковой, я пошел к подходу, чтобы включить всю функциональность в качестве методов-членов.Вместо использования стандартного подхода итераторов и алгоритмов.

Теперь цель с моей древовидной структурой состоит в том, чтобы: 1) как можно быстрее переместить ветку от одного дерева к другому.2) каждая ветвь должна быть самостоятельной.И действия, работающие с деревом, также должны быть способны выполняться на ветке.

Я просто создал класс, содержащий вектор.- Внутри вектора находятся другие объекты этого класса.Пример (я публикую здесь только минимальный пример, так как самая большая проблема, с которой я сейчас сталкиваюсь, заключается в том, что класс слишком велик для обработки): 

template <typename ValTy>
class Tree {
private:
    std::vector<std::unique_ptr<Tree> > subtrees;
    ValTy value;
};

Как вы можете видеть из этого, я могу просто взятьчто-то из subtrees - и используйте это либо как дерево, либо скопируйте вокруг.Однако, поскольку дерево верхнего уровня не имеет указаний о том, сколько поддеревьев (или сколько уровней) существует, невозможно указать «конечный итератор»?И как такие алгоритмы, как std :: find () не будут перебирать все дерево (и все его поддеревья)?

Возможно ли использовать эти алгоритмы, при этом сохраняя структуру простого"ветвление"?

Ответы [ 2 ]

1 голос
/ 17 января 2012

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

Итератор end() для этого вектора будет просто пустым стеком.

0 голосов
/ 17 января 2012

Как вы видите, я могу просто извлечь что-то из поддеревьев - и использовать это либо как дерево, либо копировать его.Однако, поскольку дерево верхнего уровня не имеет указаний о том, сколько поддеревьев (или сколько уровней) существует, невозможно указать «конечный итератор»?И как такие алгоритмы, как std :: find (), не будут перебирать все дерево (и все его поддеревья)?

Ну, проблема здесь скорее в концептуальной проблеме.

Я всегда решаю CRUD функциональность в древовидных структурах с помощью рекурсии.Для рекурсии не требуется знание количества поддеревьев, и это одна из вещей, которая позволяет O(log n) вставлять, находить и удалять.

Пример вставки : 

 void insertNode(Node* &treeNode, Node *newNode) {
     if (treeNode) treeNode = newNode;
     else if (newNode->key < treeNode->key) insertNode(treeNode->left, newNode);
     else insertNode(treeNode->right, newNode);
 }

Если вам нужно узнать, сколько уровней в дереве, просто пройдите слева от ребенка до NULL.Используя эти знания, вы можете легко разработать O(log n) алгоритмы подсчета количества детей в дереве.

Деревья предназначены для рекурсивного доступа.Если вы хотите нерекурсивный доступ, возможно, деревья - это не то, что вы ищете?- Какие данные будет хранить эта структура, на какой частоте доступа?

...