Есть ли реализация бинарного дерева поиска, аннотированного размером поддерева
Я исследовал древовидную структуру данных, описанную по этой ссылке (внизу):
http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/
Упоминается, что эта структура данных может быть пальцем. Тем не менее, после дополнительных исследований вокруг пальчиковых деревьев, я обнаружил, что в них отсутствуют "пальцы", которые делают пальчиковые деревья пальцами. Вместо этого кажется, что это просто аннотированное двоичное дерево (с размером поддерева).
Знаете ли вы о существующей реализации (на любом языке) этой структуры данных, которую я мог бы использовать в качестве ссылки для моей собственной реализации (хотя, предпочтительно, не реализации на функциональном языке программирования)?
Или, каков был бы наиболее оптимальный способ переоборудования аннотаций размера поддерева в существующую древовидную структуру данных?
Спасибо!
3 ответа
Счетные B-деревья Саймона Тэтхэма похожи. если счетчик узлов заменяется шириной буфера, как в твике, они обеспечивают операции, такие как веревки.
на самом деле, прочитав, что страница, на которую вы ссылаетесь, я вижу, что она использовалась как таблица элементов или таблица строк для редактора
в статье " Позиционные дельта-деревья для согласования обновлений с оптимизированным для чтения хранилищем данных" авторы представляют дерево, поведение которого в отношении инвариантов, которые оно содержит между узлами в дереве, демонстрирует поразительное сходство с анфиладами ксанаду, к которым рассчитывается B- Дерево тоже похоже.
У меня есть проект на github под названием https://github.com/je4d/BoostIntrusiveAnnotatedTrees, цель которого - обеспечить общую поддержку для аннотаций, таких как подсчет поддеревьев в Boost.Intrusive. Подсчет поддерево был моим первоначальным вариантом использования.
В настоящее время для него требуются шаблоны переменных C++11 и поддерживается только rbtree, но он работает, и я надеюсь, что со временем оба этих ограничения будут устранены. Обновление: теперь выполняется сборка с C++03. До сих пор поддерживает только rbtree.
При использовании с аннотацией подсчета поддеревьев это похоже на то, что Джордан описывает в ответе выше - он вычисляет (влево + вправо +1) в каждом узле. Реализация совершенно иная - она работает с любыми признаками узла и / или значения; вместо этого обновления аннотаций интегрированы в алгоритмы rbtree, что позволяет минимизировать количество пересчетов.
Я реализовал нечто подобное на основе вопроса, который я задал на днях. Я добавил аннотации к узлам boost::intrusive::rbtree/avltree, чтобы вычислить размер каждого поддерева (число узлов foreach = node->left->count + node->right->count + 1). Я выполняю это обновление для вставки / удаления / перебалансировки дерева, используя хук boost value_traits для set_parent, set_left и set_right. Как уже говорилось на сайте, на который вы ссылались, после каждого обновления узла обновляйте размер текущего узла, а затем перемещайтесь вверх по дереву, пока не дойдете до корня, обновляя размер каждого узла по мере продвижения.
Проблема возникает, когда вы хотите вставить в дерево в определенной позиции. Практически в тот момент, когда вы это сделаете, вы аннулируете инвариант порядка ключей для древовидной структуры. Это означает, что вы не сможете выполнить эффективный O(log n) поиск по ключу. Но, если вы этого хотите, вам, вероятно, в любом случае не понадобятся аннотации к размеру.