Есть ли реализация бинарного дерева поиска, аннотированного размером поддерева

Question

Я исследовал древовидную структуру данных, описанную по этой ссылке (внизу):

http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/

Упоминается, что эта структура данных может быть пальцем. Тем не менее, после дальнейших исследований пальмовых деревьев я обнаружил, что в них отсутствуют «пальцы», которые делают пальчиковые деревья пальцами. Вместо этого кажется, что это просто аннотированное двоичное дерево (с размером поддерева).

Знаете ли вы о существующей реализации (на любом языке) этой структуры данных, которую я мог бы использовать в качестве ссылки для моей собственной реализации (хотя, предпочтительно, не реализация на функциональном языке программирования) ?

Или, что было бы наиболее оптимальным способом доукомплектации аннотаций размера поддерева в существующую древовидную структуру данных?

Спасибо!

Answer 1

Подсчитанные B-деревья Саймона Тэтхама похожи.если счетчик узлов заменяется на ширину буфера, как в tweak , они обеспечивают такие операции, как ropes .

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

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

Answer 2

У меня есть проект на github, который называется Boost.Intrusive Annotated Trees , цель которого - обеспечить общую поддержку аннотаций, таких как подсчет поддеревьев в Boost.Intrusive. Подсчет поддеревьев был моим первоначальным вариантом использования.

В настоящее время для него требуются шаблоны переменных C ++ 11 и поддерживается только rbtree, но он работает, и я надеюсь снять оба эти ограничения вовремя Обновление : теперь собирается с C ++ 03. По-прежнему поддерживает только rbtree.

При использовании с аннотацией подсчета поддеревьев это похоже на то, что Джордан описывает в ответе выше - он вычисляет (влево + вправо + 1) в каждом узле. Реализация совсем другая - она ​​работает с любыми признаками узла и / или значения; вместо этого обновления аннотации интегрированы в алгоритмы rbtree, что позволяет минимизировать количество пересчетов.

Answer 3

Я реализовал нечто подобное, основываясь на вопросе, который я задал на днях. Я добавил аннотации к узлам boost :: intrusive :: rbtree / avltree, чтобы вычислить размер каждого поддерева (число узлов foreach = node-> left-> count + node-> right-> count + 1). Я выполняю это обновление при вставке / удалении / перебалансировке дерева, используя хук boost value_traits для set_parent, set_left и set_right. Как уже говорилось на сайте, на который вы ссылались, после каждого обновления узла обновляйте размер текущего узла, а затем перемещайтесь вверх по дереву, пока не достигнете корня, обновляя размер каждого узла по мере продвижения.

Проблема возникает, когда вы хотите вставить в дерево в определенной позиции. Практически в тот момент, когда вы это сделаете, вы аннулируете инвариант порядка ключей для древовидной структуры. Это означает, что вы не сможете выполнить эффективный O (log n) поиск по ключу. Но, если вы этого хотите, вам, вероятно, в любом случае не понадобятся аннотации к размеру.