Конкатенирование красно-черных деревьев

Ответ 1

Я не уверен в формулировке вашего вопроса, если вам интересно установить объединение или конкатенацию или и то, и другое, или если вас интересуют только постоянные структуры данных, общие для OCaml, а также в эфемерных структурах.

Реализация красно-черных деревьев с пальцами описана Хизер Д. Бут в главе из ее тезиса. С пальцами красно-черное дерево размера n можно разделить на два дерева размером p и q в амортизированном O (lg (min (p, q))), а два красно-чёрных дерева размером p и q могут быть объединены в одну и ту же границу. Кроме того, элемент может быть добавлен или удален на любом конце дерева rb в течение времени O (1). С помощью этих операций можно добиться амортизации O (p lg (q/p)) объединения времени (для p < q), что является теоретически оптимальным по информации. Возможно, ключевой идеей получить эти границы является обращение к указателям на левый и правый шипы.

Оценки, указанные выше, амортизируются в традиционном смысле. Для функционального языка, такого как OCaml, можно пожелать иметь границы, которые применяются, когда структура данных используется постоянно. Я не думаю, что описание Booth достигнет всех этих границ, когда деревья будут использоваться постоянно. Например, вставка пальцем может принимать & omega; (1) перекраски. Это можно решить с помощью ленивых перекрасок, обсуждаемых в Driscoll et al. "Создание постоянных структур данных" .

С другой стороны, я думаю, что анализ Бута может показать, что конкатенация по-прежнему равна O (lg (max (p, q))) даже при постоянном использовании. Я менее оптимистично отношусь к объединенному объединению.

Операции с асимптотически оптимальными временными границами возможны в функциональной настройке. Эти описанные Hinze и Paterson, достигают границ в амортизированном (но постоянном) смысле, treaps, описанные Blandford и Blelloch, достигают границ в рандомизированном смысле, и те описанные Капланом и Тарьяном добиться их в худшем случае. Последние также предлагают O (lg lg (min (p, q))) конкатенацию, хотя Hinze и Paterson сомнительны в этом утверждении. Эти деревья не являются прямым ответом на ваш вопрос, который характерен для красно-черных деревьев, но они, надеюсь, дают вкус того, что возможно, а документ H & P содержит код и проверен корректно с использованием Coq, который может извлекаться в OCaml-код.

Еще два указателя, которые могут вас заинтересовать: Brodal et al. отображали деревья поиска с помощью O (lg n), находили, вставляли и удаляли, а O (1) выполняли даже в функциональной настройке. Кроме того, Atallah et al. утверждают, что описывают красно-черное дерево, которое амортизировало O (1) concat (предположительно только эфемерно), но Буксбаум и Гудрич утверждают, что есть несколько недостатков в этой структуре.

Последнее замечание об утилизации красно-черных деревьев: в одном из комментариев к одному из ответов на этот вопрос вы говорите:

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

Есть и другие преимущества. Например, некоторые структуры данных, используемые в вычислительной геометрии, основаны на двоичных деревьях поиска, но имеют высокую стоимость вращения дерева. Красно-черные деревья могут быть перебалансированы не более чем на 3 оборота на вставку и удаление, а деревья AVL могут принимать и Omega; (lg n) вращения для этих операций. Как заметил Ральф Хинзе, Схема балансировки Окасаки для красно-черных деревьев (код доступен в ML, Haskell, Java и Ada) не предлагает такую ​​же привязку и может в конечном итоге делать & Omega; (lg n) вращения на вставки. (Окасаки не дает удаления.)

Кроме того, сохраняемые по высоте деревья поиска (и даже деревья AVL) могут быть сохранены, чтобы использовать только один бит информации о балансе за node. Некоторые деревья имеют только две возможные позиции баланса на каждом node, как односторонние сбалансированные по высоте деревья, но деревья с четырьмя возможными позициями баланса на node могут хранить один бит информации о балансе в каждом ребенке, поскольку изначально объясняется Брауном, а затем расширенный Haeupler et al.

Edit:

В ответ на ваш конкретный запрос в конце вашего вопроса, вот описание алгоритма для конкатенации двух красно-черных деревьев. Требуется время O (lg (max (| L |, | R |))), которое слишком велико, чтобы получить асимптотически оптимальное время объединения, описанное выше. Для сравнения, я ожидаю, что реализация "join" для наборов AVL в OCaml stdlib получает производительность O (h1-h2), где h1 - это высота более высокого дерева, хотя она фактически соединяет два дерева AVL с учетом элемента, который находится между ними, а алгоритм ниже должен найти и удалить этот минометный элемент из одного из его аргументов. Вы могли бы избежать этого, только сохраняя элементы в листьях, как в дереве B +, но это имеет ограничение пространства, связанное с тем, что нужно держать кучу указателей на элементах не-листовых узлов для поиска. В любом случае, это не приведет к постоянному объединению деревьев деревьев одинаковой высоты, таких как код соединения AVL в OCaml stdlib, поскольку вам все равно придется вычислять черную высоту каждого дерева, как описано ниже.

Учитывая два непустых красно-черных дерева L и R, мы создадим новое красно-черное дерево, которое является конкатенацией L и R. Это займет время, пропорциональное O (lg (max (| L |, | R |))), где | L | обозначает число узлов в L.

Сначала удалите наибольший элемент из L, c. Затем найдите черную высоту L и R. Под "черной высотой" я подразумеваю количество черных узлов по любому пути от корень к листу. По красно-черным инвариантам дерева это постоянное по всем путям любого дерева. Вызовите L черной высотой p и R черной высотой q и предположите w.l.o.g. p & le; д.

Из корня R следуйте за левыми дочерними элементами, пока не достигнете черного node R 'с высотой p. Создайте новое красное дерево C с корневым элементом c, левым дочерним L и правым ребенок R '. Так как L является красно-черным деревом сам по себе, его корень черный, а инварианты цвета не нарушаются на уровне или ниже C. Кроме того, черная высота C является p.

Однако мы не можем просто спланировать C обратно на R вместо R '. Во-первых, если p = q, R '- R, но C имеет красный корень. В этом случае просто перекрасьте корень C черного цвета. Это ваш новое конкатенированное дерево.

Во-вторых, если R 'не является корнем, у него может быть красный родитель. Красным родителям не разрешают иметь красных детей, поэтому мы должны балансировать. Здесь мы просто применяем балансировку Окасаки схемы по всему позвоночнику между R '(теперь замененным на C) и корнем R.

Возможны два случая. Если у C нет бабушки и дедушки, цвет C - черный. Теперь дерево действует.

Если C имеет бабушку и дедушку, она должна быть черной и черной высоты p + 1, так как родитель C красный. Замените C grandparent новым красным деревом, корень которого является корнем родителя C, левое потомство которого является C, окрашено в черный цвет, а правый ребенок - это черное дерево, состоящее из C-брата, корня бабушки C и C-дяди, в этот заказ. Это не увеличивает черную высоту бабушки-дедушки C, но она меняет цвет на красный, что может сделать его корнем или красным ребенком красного родительский, так что мы должны снова перебалансироваться и т.д. вплоть до дерева

• Поиск черной высоты обоих деревьев: O (lg | L |) + O (lg | R |)
• Отслеживание R в нужное место: O (lg | R | - lg | L |)
• Вращение полностью назад к корню: O (lg | R | - lg | L |)

Ни одно из них не превосходит O (lg | R | + lg | L |) = O (lg (max (| L |, | R |)))

Чтобы сделать это O (lg (min (| L |, | R |))), сначала переверните указатели позвоночника. Тогда вам не нужна черная высота большего дерева, вам нужно только подсчитывать черные узлы спинного хребта до тех пор, пока не останется одно дерево из позвоночника. Затем используйте исходную (не Окасаки) схему балансировки, чтобы убедиться, что вы только перебалансировали O (1) узлы. Наконец, отметьте остальную часть позвоночника, которая не нуждается в перебалансировке для ленивого повторного окрашивания, если потребуется позже.

Ответ 2

Поскольку вы, кажется, говорите о Concatenate + добавлении в конец, кажется, что у вас есть следующая проблема:

Given two red-black trees T1 and T2, such that keys of T1 <= keys of T2,
find union of the two.

Это называется операции объединения на деревьях, и в этом случае можно выполнить объединение деревьев в O (log n) времени, проверить: http://www.cs.tau.ac.il/~wein/publications/pdfs/rb_tree.pdf

Также проверьте: http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm, проблема 14.2.

Ответ 3

Может делать лучше, чем O (log ^ 2 (n)) при конкатенации и не увеличивать дерево с информацией о высоте в каждом node. Вы можете объединить в 2 * [log (n1) + log (n2)], где n1 и n2 представляют количество узлов в деревьях, которые вы конкатенации. После вычисления высоты в O (log (n)) используйте информацию баланса в каждом node при сходе по дереву, чтобы найти правильную точку конкатенации!

Ответ 4

Вы можете выиграть что-то, когда вы объедините дерево с небольшим перекрытием, но в целом вам придется перезагружать узлы. При балансировке у вас худшая ситуация, так как там, вероятно, правила для вращения после касания только одного node.