Какой инвариант поддерживает RRB-деревья?

Relaxed Radix Balanced Trees (RRB-деревья) - это обобщение неизменяемых векторов (используемых в Clojure и Scala), которые имеют "эффективно постоянную" индексацию и время обновления. RRB-деревья поддерживают эффективную индексацию и обновление, но также обеспечивают эффективную конкатенацию (log n).

Авторы представляют структуру данных таким образом, что мне трудно следовать. Я не совсем уверен, что такое инвариант, который поддерживается каждым node.

В разделе 2.5 описывается их алгоритм. Я думаю, что они гарантируют, что индексирование в node потребует только дополнительных шагов линейного поиска после поиска по методу радикса. Я не понимаю, как они вывели формулу для дополнительных шагов, и я думаю, что, возможно, я не уверен, что означает каждая из переменных (в частности, "всего p ветвей дерева" ).

Как работает алгоритм конкатенации RRB-дерева?

Ответ 1

Они описывают инвариант в разделе 2.4 "Однако, как упоминалось ранее Узлы B-Trees не облегчают поиск оснований. Вместо этого мы выбрали начальный инвариант, позволяющий размеру node варьироваться от m и m 􀀀 1. Это определяет семейство сбалансированных деревьев, начиная с хорошо известные 2-3 дерева, 3-4 дерева и (для m = 32) 31-32 деревьев. Эта инвариант обеспечивает балансировку и обеспечивает поиск ветки radix в в большинстве случаев. Иногда требуется несколько шагов линейного поиска после поиска radix, чтобы найти правильную ветвь. Дополнительные шаги требуют увеличения на более высоких уровнях.

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

Ответ 2

@mcdowella правильно, что они говорят о расслабленных узлах. Но если вы разделяете и соединяете узлы, диапазон от m до m-1 означает, что вам иногда приходится настраивать до узлов m-1 (m-2?), Чтобы добавить или удалить один элемент из node. Это кажется ужасно неэффективным. Я думаю, что они означали между m и (2 м) - 1, потому что это позволяет разделять узлы на 2, когда они становятся слишком большими, или два узла, соединенных в один, когда они слишком малы, но при этом не требуется менять третий node. Так что опечатка о том, что "2" отсутствует в "2 м" в документе. Жан Никлас Лоранж оспаривает тезис, поддерживает меня на этом.

Кроме того, все строгие узлы имеют одинаковую длину, которая должна быть степенью 2. Причина этого - оптимизация в Rich Hickey Clojure PersistentVector. Ну, я думаю, что важно упаковать все строгие узлы слева (подробнее об этом позже), поэтому вам не нужно угадывать, какая ветвь дерева спускается. Но возможность бит-сдвига и бит-маска вместо деления - прекрасный бонус. Я не успел выполнить операцию get() на расслабленном Scala Vector, но расслабленный вектор Paguro примерно в 10 раз медленнее, чем строгий. Поэтому он прилагает все усилия, чтобы быть как можно более строгим, даже производя 2 строгих уровня, если вы повторно вставляете в 0.

Их дерево также имеет ровную высоту - все листовые узлы равны расстоянию от корня. Я думаю, что это все равно будет работать, если бы расслабленные деревья должны были находиться внутри, скажем, одного уровня друг друга, хотя и не были уверены, что вы купите вас.

У ослабленных узлов могут быть строгие дети, но не наоборот.

Строгие узлы должны быть заполнены слева (с низким индексом) без пробелов. Любые неполные строгие узлы должны быть на правом (высокоиндексном) краю дерева. Все узлы строгого листа всегда могут быть заполнены, если вы добавляете их в фокус или хвост (подробнее об этом ниже).

Вы можете увидеть большинство инвариантов, выполнив поиск методов debugValidate() в Paguro implementation. Это не их бумага, но она в основном основана на ней. Фактически, переменные "display" в Scala реализация не упоминаются в документе. Если вы собираетесь изучать этот материал, вы, вероятно, захотите начать с хорошего взгляда на Clojure PersistentVector, поскольку Дерево RRB имеет внутри него. Две отличия между этим и деревом RRB: 1. Дерево RRB позволяет "расслабленным" узлам и 2. Дерево RRB может иметь "фокус" вместо "хвоста". Оба фокуса и хвоста - небольшие буферы (возможно, такого же размера, как строгий лист node), причем разница заключается в том, что фокус, вероятно, будет локализован в любую область, в которую был вставлен последний вектор/добавлен, в то время как хвост всегда находится на конец (PerSistentVector может быть добавлен только, никогда не вставлен). Эти 2 отличия - это то, что позволяет O (log n) произвольные вставки и удаления, плюс операции O (log n) split() и join().