Если интересен механизм, то в моей голове это происходит так - берется родитель который станет корнем, ищутся все его потомки, и к примеру копируются(или права на владения передаются) в отдельное дерево, а из этого очищаются(или становятся не валидными). Да, как и сказано в статье, а также показано на иллюстрации. К примеру на 20м уровне данные исключительно с приоритетом 20; на уровне 15 с приоритетом 15 и так далее.
Родитель, как и ребенок, означает родительский узел, как и в обычном дереве типа бинарного. В примере профилей, и даже на иллюстрации показаны возможные методы создания ребер(связей), например хранение указателя\индекса. Можно и не брать, и не хранить. В таком случае выйдет однонаправленное дерево, если вам угодно.
Согласен, в Insert() связи устанавливаются неявно. Чтобы скорее ответить на ваш комментарий, я взял пример из своего проекта, где связь вычисляется напрямую из данных. Пожалуй верная реализация без отстраненных данных будет такой Insert(priority, data, &parent) // Или индексы родителя в случаях с Memory извиняюсь, не доглядел.
Интересная идея. Тогда думаю и vector можно не хранить, если минимальный приоритет всегда 0, просто хранить максимум одной переменной. Однако конкретно мне нужно дерево для сохранения связей родитель-ребенок, а это как я знаю и образует дерево. В таком случае спасибо за обратную связь!
Окей, конечно, я могу написать функции если это столь не очевидно(в разделе "Итог" и "Работа функций с профилями" уже приведены все нужные параметры), далее на ваших примерах:
SAPT позволяет добавлять в структуру элементы с неким параметром "приоритет" и некими данными(ключом); Insert(priority, data) Получать и удалять узел с максимальным \ минимальным приоритетом; GetMax() -> node; GetMin() -> node Remove(node) Перебирать элементы на одном уровне(с одним приоритетом), в глубину, снизу вверх и сверху вниз(является двунаправленным); IterateLevel(level) {}; IterateUp() {}; IterateDown() {} Искать родителя\ребенка от ребенка\родителя, бонусом по индексу в уровне; FindByIndex(level, fragment, index) -> node FindParent(child) -> parent FindChildren(parent) -> children[] Легко делить структуру на несколько; Divide(startNode) -> dividedPart Дерево не ориентировано на частые изменения приоритета \ добавление новых элементов; Сортирует данные по заданному приоритету при вставке, данные связаны между собой;
Вся статья о работе и организации структуры, не понимаю проблемы. По моему быстрее статью прочитать, чем короткое описание ждать.
Профили я привел лишь как пример, они являются как бы разными примерами реализации структуры, хоть и считаю профили отдельной, доп. частью, структуры. Но для большего понимания я старался как можно лучше объяснить всю свою идею. А описывать там кажется нечего, примеры структур представляющих узлы дерева. А если говорить про переменные - важные описаны в статье, а остальные полностью описывают себя своими названиями.
Если я верно понял, вы имеете ввиду описание реализации дерева. Однако в статье я написал лишь про концепт(если хотите идею) как структуры, так и работы с ней, и упомянул это в самом начале(про это еще немного в конце комментария).
Зачем нужна структура - думаю как в случае с другими структурами, каждый придумает конкретное применение себе сам, а я отдаленно привел пример со своим проектом. Если имеется ввиду общее назначение - для сортировки по приоритетам. Приоритет самый простой, как например в бинарном дереве, но разрешаются дубликаты, в моем примере данные("клетки") уникальны, и объединить их в кластер без потерь трудно и выглядит для меня бессмысленным. Меняться может все, но без серьезных логических потерь в сложности только при инициализации или полном пересчете дерева(для понимания потерь стоит представить дерево и вспомнить работу с функциями разных профилей). Если ну очень сильно грубо говорить то конечно, можно сравнить дерево с массивом или связным списком. Насчет сложности - половина моих итоговых подсчетов унаследована от массивов, ведь с ними напрямую связаны вся структура, и отдельно уровни.
Не упомянул я реализацию по двум причинам: - Я в программировании не профессионал, я только учусь, и показывать примеры, возможно, плохо организованного или отдаленного кода не хочется, хотя это меньшая из причин. - Я хотел рассказать вам о идее(концепции) такой структуры и поделиться своим проектом, постарался описать все функции как можно подробнее, но без технических деталей и реализации. Я постарался как можно яснее объяснить идею работы функций, и попробовать передать абстрактное представление структуры программистом через иллюстрацию.
Ваш первый вопрос довольно неконкретный, я затрудняюсь на него ответить. Очевидно хранит данные, но почти уверен это не тот ответ который вы надеялись услышать. Пример реализации функций работы с деревом я привел в статье, либо описал их идею, на примере фрагментации. Static - подразумевает, негативно влияющую на сложность, реакцию на изменение данных дерева динамически(я к этому отсылался в разделе о фрагментации). Если сравнивать с привычными обществу деревьями - это узкое место SAPT. В том числе по этой причине я указал специфичность задач, которым подходит структура. Хотя безусловно этот концепт можно модифицировать, сместив фокус на динамичность. Abstract - на эту тему я коротко высказался в начале статьи. Я имел ввиду, возможно не очевидное(потому приправленное иллюстрацией), представление структуры, а также различность реализации дерева с обычными деревьями, уровни физичны, некоторые вычисления опираются на закономерности выведенные только по причине такого представления программистом. Priority - возможно, это не самое важное ключевое слово, однако хотелось подчеркнуть именно работу с приоритетами - дерево сортируется именно по ним. Tree - также хочется добавить - независимо от реализации дерева, я опирался на идею о том, что родители и дети связаны между собой, потому назвал структуру не иначе как деревом. Хотя она идет вразрез с многими устоявшимися представлениями о реализации деревьев.
Если интересен механизм, то в моей голове это происходит так - берется родитель который станет корнем, ищутся все его потомки, и к примеру копируются(или права на владения передаются) в отдельное дерево, а из этого очищаются(или становятся не валидными).
Да, как и сказано в статье, а также показано на иллюстрации. К примеру на 20м уровне данные исключительно с приоритетом 20; на уровне 15 с приоритетом 15 и так далее.
Родитель, как и ребенок, означает родительский узел, как и в обычном дереве типа бинарного. В примере профилей, и даже на иллюстрации показаны возможные методы создания ребер(связей), например хранение указателя\индекса.
Можно и не брать, и не хранить. В таком случае выйдет однонаправленное дерево, если вам угодно.
Согласен, в Insert() связи устанавливаются неявно. Чтобы скорее ответить на ваш комментарий, я взял пример из своего проекта, где связь вычисляется напрямую из данных. Пожалуй верная реализация без отстраненных данных будет такой
Insert(priority, data, &parent) // Или индексы родителя в случаях с Memoryизвиняюсь, не доглядел.Интересная идея. Тогда думаю и vector можно не хранить, если минимальный приоритет всегда 0, просто хранить максимум одной переменной. Однако конкретно мне нужно дерево для сохранения связей родитель-ребенок, а это как я знаю и образует дерево. В таком случае спасибо за обратную связь!
Окей, конечно, я могу написать функции если это столь не очевидно(в разделе "Итог" и "Работа функций с профилями" уже приведены все нужные параметры), далее на ваших примерах:
SAPT позволяет добавлять в структуру элементы с неким параметром "приоритет" и некими данными(ключом);
Insert(priority, data)Получать и удалять узел с максимальным \ минимальным приоритетом;
GetMax() -> node; GetMin() -> nodeRemove(node)
Перебирать элементы на одном уровне(с одним приоритетом), в глубину, снизу вверх и сверху вниз(является двунаправленным);
IterateLevel(level) {}; IterateUp() {}; IterateDown() {}Искать родителя\ребенка от ребенка\родителя, бонусом по индексу в уровне;
FindByIndex(level, fragment, index) -> nodeFindParent(child) -> parent
FindChildren(parent) -> children[]
Легко делить структуру на несколько;
Divide(startNode) -> dividedPartДерево не ориентировано на частые изменения приоритета \ добавление новых элементов;
Сортирует данные по заданному приоритету при вставке, данные связаны между собой;
Вся статья о работе и организации структуры, не понимаю проблемы. По моему быстрее статью прочитать, чем короткое описание ждать.
Профили я привел лишь как пример, они являются как бы разными примерами реализации структуры, хоть и считаю профили отдельной, доп. частью, структуры. Но для большего понимания я старался как можно лучше объяснить всю свою идею.
А описывать там кажется нечего, примеры структур представляющих узлы дерева. А если говорить про переменные - важные описаны в статье, а остальные полностью описывают себя своими названиями.
Если я верно понял, вы имеете ввиду описание реализации дерева. Однако в статье я написал лишь про концепт(если хотите идею) как структуры, так и работы с ней, и упомянул это в самом начале(про это еще немного в конце комментария).
Зачем нужна структура - думаю как в случае с другими структурами, каждый придумает конкретное применение себе сам, а я отдаленно привел пример со своим проектом. Если имеется ввиду общее назначение - для сортировки по приоритетам.
Приоритет самый простой, как например в бинарном дереве, но разрешаются дубликаты, в моем примере данные("клетки") уникальны, и объединить их в кластер без потерь трудно и выглядит для меня бессмысленным.
Меняться может все, но без серьезных логических потерь в сложности только при инициализации или полном пересчете дерева(для понимания потерь стоит представить дерево и вспомнить работу с функциями разных профилей).
Если ну очень сильно грубо говорить то конечно, можно сравнить дерево с массивом или связным списком. Насчет сложности - половина моих итоговых подсчетов унаследована от массивов, ведь с ними напрямую связаны вся структура, и отдельно уровни.
Не упомянул я реализацию по двум причинам:
- Я в программировании не профессионал, я только учусь, и показывать примеры, возможно, плохо организованного или отдаленного кода не хочется, хотя это меньшая из причин.
- Я хотел рассказать вам о идее(концепции) такой структуры и поделиться своим проектом, постарался описать все функции как можно подробнее, но без технических деталей и реализации.
Я постарался как можно яснее объяснить идею работы функций, и попробовать передать абстрактное представление структуры программистом через иллюстрацию.
Спасибо за комментарий!
Ваш первый вопрос довольно неконкретный, я затрудняюсь на него ответить.
Очевидно хранит данные, но почти уверен это не тот ответ который вы надеялись услышать.
Пример реализации функций работы с деревом я привел в статье, либо описал их идею, на примере фрагментации.
Static - подразумевает, негативно влияющую на сложность, реакцию на изменение данных дерева динамически(я к этому отсылался в разделе о фрагментации). Если сравнивать с привычными обществу деревьями - это узкое место SAPT. В том числе по этой причине я указал специфичность задач, которым подходит структура. Хотя безусловно этот концепт можно модифицировать, сместив фокус на динамичность.
Abstract - на эту тему я коротко высказался в начале статьи. Я имел ввиду, возможно не очевидное(потому приправленное иллюстрацией), представление структуры, а также различность реализации дерева с обычными деревьями, уровни физичны, некоторые вычисления опираются на закономерности выведенные только по причине такого представления программистом.
Priority - возможно, это не самое важное ключевое слово, однако хотелось подчеркнуть именно работу с приоритетами - дерево сортируется именно по ним.
Tree - также хочется добавить - независимо от реализации дерева, я опирался на идею о том, что родители и дети связаны между собой, потому назвал структуру не иначе как деревом. Хотя она идет вразрез с многими устоявшимися представлениями о реализации деревьев.