Comments 12
А делает-то это дерево что? Как вообще с ним работать? Что означают слова Static, Abstract и Priority в его названии?
Ваш первый вопрос довольно неконкретный, я затрудняюсь на него ответить.
Очевидно хранит данные, но почти уверен это не тот ответ который вы надеялись услышать.
Пример реализации функций работы с деревом я привел в статье, либо описал их идею, на примере фрагментации.
Static - подразумевает, негативно влияющую на сложность, реакцию на изменение данных дерева динамически(я к этому отсылался в разделе о фрагментации). Если сравнивать с привычными обществу деревьями - это узкое место SAPT. В том числе по этой причине я указал специфичность задач, которым подходит структура. Хотя безусловно этот концепт можно модифицировать, сместив фокус на динамичность.
Abstract - на эту тему я коротко высказался в начале статьи. Я имел ввиду, возможно не очевидное(потому приправленное иллюстрацией), представление структуры, а также различность реализации дерева с обычными деревьями, уровни физичны, некоторые вычисления опираются на закономерности выведенные только по причине такого представления программистом.
Priority - возможно, это не самое важное ключевое слово, однако хотелось подчеркнуть именно работу с приоритетами - дерево сортируется именно по ним.
Tree - также хочется добавить - независимо от реализации дерева, я опирался на идею о том, что родители и дети связаны между собой, потому назвал структуру не иначе как деревом. Хотя она идет вразрез с многими устоявшимися представлениями о реализации деревьев.
В статье очень не хватает хоть какого-то описания, что же это за структура данных-то и какие операции она выполняет.
Например, приоритетная очередь позволяет добавлять в структуру элементы с неким параметором "приоритет" и неким ключом, выдавать и удалять элемент с максимальным приоритетом и иногда изменять приоритет элемента с данным ключом: Insert(priority, key), GetMax() -> key, RemoveMax(), ChangePriority(key).
Бинарное дерево поиска позволяет добавлять элемент с ключом, удалять элемент по ключу и проверять, есть ли данный ключ в структуре, перебирать элементы в порядке возрастания ключа: Insert(key), remove(key), HasKey(key) -> bool, enumerate()-> key[]. Хеш-таблица далает все тоже самое, кроме перебора элементов по порядку возрастания ключа.
Дерево отрезков умеет изменять значение по индексу и выдавать сумму или максимум на отрезке между заданными индексами... и так далее.
Вот также надо расписать все ваши операции, без этого вообще непонятно, зачем нужна ваша структура и нужна ли она вообще. Что за приоритет, что там меняется вообще, а что неизменно? Может, ваши операции с такой же сложностью выполняются на обычном массиве или связном списке. Может, вам подойдет обычная сортировка подсчетом вместо какой-то структуры данных, если вам надо упорядочить "клетки" по приоритету.
Если я верно понял, вы имеете ввиду описание реализации дерева. Однако в статье я написал лишь про концепт(если хотите идею) как структуры, так и работы с ней, и упомянул это в самом начале(про это еще немного в конце комментария).
Зачем нужна структура - думаю как в случае с другими структурами, каждый придумает конкретное применение себе сам, а я отдаленно привел пример со своим проектом. Если имеется ввиду общее назначение - для сортировки по приоритетам.
Приоритет самый простой, как например в бинарном дереве, но разрешаются дубликаты, в моем примере данные("клетки") уникальны, и объединить их в кластер без потерь трудно и выглядит для меня бессмысленным.
Меняться может все, но без серьезных логических потерь в сложности только при инициализации или полном пересчете дерева(для понимания потерь стоит представить дерево и вспомнить работу с функциями разных профилей).
Если ну очень сильно грубо говорить то конечно, можно сравнить дерево с массивом или связным списком. Насчет сложности - половина моих итоговых подсчетов унаследована от массивов, ведь с ними напрямую связаны вся структура, и отдельно уровни.
Не упомянул я реализацию по двум причинам:
- Я в программировании не профессионал, я только учусь, и показывать примеры, возможно, плохо организованного или отдаленного кода не хочется, хотя это меньшая из причин.
- Я хотел рассказать вам о идее(концепции) такой структуры и поделиться своим проектом, постарался описать все функции как можно подробнее, но без технических деталей и реализации.
Я постарался как можно яснее объяснить идею работы функций, и попробовать передать абстрактное представление структуры программистом через иллюстрацию.
Спасибо за комментарий!
Если я верно понял, вы имеете ввиду описание реализации дерева.
Нет, я имею ввиду описание того, что дерево делает. Какую задачу структура данных решает вообще. Я вам даже кучу примеров описания для других структур привел.
Приоритет самый простой, как например в бинарном дереве,
В бинарном дереве нет приоритетов. Приоритет есть в куче.
Я хотел рассказать вам о идее(концепции) такой структуры и поделиться своим проектом,
Ну вот никому ничего не понятно, потому что неясно, что это вообще за структура и что она делает, зачем она нужна. Вы какие-то детали рассказали, но вообще не те, которые нужны для этого рассказа.
Окей, конечно, я могу написать функции если это столь не очевидно(в разделе "Итог" и "Работа функций с профилями" уже приведены все нужные параметры), далее на ваших примерах:
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
Дерево не ориентировано на частые изменения приоритета \ добавление новых элементов;
Сортирует данные по заданному приоритету при вставке, данные связаны между собой;
Вся статья о работе и организации структуры, не понимаю проблемы. По моему быстрее статью прочитать, чем короткое описание ждать.
Спасибо, стало понятнее.Разделение дерева какими-то свойствами обладает? Например, в отсоединенном куске будут только элементы с меньшим приоритетом?
На одном уровне все элементы с заданным приоритетом?
Искать родителя\ребенка от ребенка\родителя, бонусом по индексу в уровне;
Что значит родитель в этой парадигме? И зачем вам его брать? Дерево - это внутреннее устройство структуры. Вообще говоря, снаружи вы о том что там вообще дерево можете и не знать. В insert() у вас никакого понятия о родителях/детях нет.
Дерево не ориентировано на частые изменения приоритета \ добавление новых элементов;
В таком случае вам не нужно дерево. Вам достаточно std::unordered_map<int, vector<Data>> priority_to_data. И еще в нагрузку к этому vector<> всех приоритетов, которые в структуре есть, чтобы можно было быстро брать следующий, предыдущий приоритет.
С разделением на части только не понятно немного. Возможно каждый кусок будет иметь свой вектор приоритетов и шарить один unordered_map. Если надо совсем быстро, то vector приоритетов тоже будет общим, и каждый кусок будет хранть array_view какой-нибудь на него.
Если интересен механизм, то в моей голове это происходит так - берется родитель который станет корнем, ищутся все его потомки, и к примеру копируются(или права на владения передаются) в отдельное дерево, а из этого очищаются(или становятся не валидными).
Да, как и сказано в статье, а также показано на иллюстрации. К примеру на 20м уровне данные исключительно с приоритетом 20; на уровне 15 с приоритетом 15 и так далее.
Родитель, как и ребенок, означает родительский узел, как и в обычном дереве типа бинарного. В примере профилей, и даже на иллюстрации показаны возможные методы создания ребер(связей), например хранение указателя\индекса.
Можно и не брать, и не хранить. В таком случае выйдет однонаправленное дерево, если вам угодно.
Согласен, в Insert() связи устанавливаются неявно. Чтобы скорее ответить на ваш комментарий, я взял пример из своего проекта, где связь вычисляется напрямую из данных. Пожалуй верная реализация без отстраненных данных будет такой Insert(priority, data, &parent) // Или индексы родителя в случаях с Memory извиняюсь, не доглядел.
Интересная идея. Тогда думаю и vector можно не хранить, если минимальный приоритет всегда 0, просто хранить максимум одной переменной. Однако конкретно мне нужно дерево для сохранения связей родитель-ребенок, а это как я знаю и образует дерево. В таком случае спасибо за обратную связь!
И еще, вы привели какие-то детали реализации касающиеся набора профилей, но ни ссылки на код, ни детального описания реализации нигде нет.
Профили я привел лишь как пример, они являются как бы разными примерами реализации структуры, хоть и считаю профили отдельной, доп. частью, структуры. Но для большего понимания я старался как можно лучше объяснить всю свою идею.
А описывать там кажется нечего, примеры структур представляющих узлы дерева. А если говорить про переменные - важные описаны в статье, а остальные полностью описывают себя своими названиями.
Предлагаю вам взяться за теорему Ферма.
Отчет о проекте эффективного приоритетного дерева SAPT