Существует ли реализация двоичного дерева поиска с указанием размера поддерева?

Question

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

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

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

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

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

Спасибо!

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

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