Я не уверен в формулировке вашего вопроса, если вы заинтересованы в объединении или объединении или обоим, или если вас интересуют только постоянные структуры данных, общие для OCaml, а также в эфемерных структурах.
Реализация red-black trees with fingers is described by Heather D. Booth in a chapter from her thesis. С пальцами красно-черное дерево размера n можно разделить на два дерева размером p и q в амортизированном O (lg (min (p, q))), а два красно-чёрных дерева размером p и q могут быть объединены в одну и ту же границу. Кроме того, элемент может быть добавлен или удален на любом конце дерева rb в течение времени O (1). С помощью этих операций можно добиться амортизации O (p lg (q/p)) объединения времени (для p < q), что является теоретически оптимальным по информации. Возможно, ключевая идея получить эти границы - это обращение к указателям ребенка на левый и правый шипы.
Оценки, указанные выше, амортизируются в традиционном смысле. Для функционального языка, такого как OCaml, можно пожелать иметь границы, которые применяются, когда структура данных используется постоянно. Я не думаю, что описание Бута достигнет всех этих границ, когда деревья будут использоваться постоянно. Например, вставка пальцем может принимать ω (1) перекраски. Это можно решить с помощью lazy recolorings discussed in Driscoll et al.'s "Making Data Structures Persistent".
С другой стороны, я думаю, что анализ Бута может показать, что конкатенация по-прежнему O (lg (max (p, q))) даже при постоянном использовании. Я менее оптимистично отношусь к объединенному объединению.
Операции с асимптотически оптимальными временными границами возможны в функциональной настройке. Эти described by Hinze & Paterson достигают границ в амортизированном (но постоянном) смысле, treaps described by Blandford & Blelloch achieve the bounds in a randomized sense, и те described by Kaplan & Tarjan достигают их в худшем случае. Последние также предлагают O (lg lg (min (p, q))) конкатенация, хотя Hinze & Патерсон сомневаются в этом утверждении. Эти деревья не являются прямым ответом на ваш вопрос, который специфичен для красно-черных деревьев, но они, надеюсь, дают вкус того, что возможно, и документ H & P содержит код и has been verified correct using Coq, который может извлекаться в код OCaml.
Еще две указатели, которые могут вас заинтересовать: Brodal et al. presented search trees with O(lg n) find, insert, and delete and O(1) concat even in a functional setting. Кроме того, Atallah et al. claim to describe a red-black tree that has amortized O(1) concat (presumably ephemerally only), но Buchsbaum and Goodrich claim that there are several flaws in that structure.
одно замечание о пользе красно-черных деревьев: в одном из комментариев на одном из ответов на этот вопрос, вы говорите:
Единственное преимущество красно-черного дерева является то, что вспомогательная информация (красная или черная) только 1 бит для каждой ветви. Добавляя высоту, вы потеряли это преимущество и могли бы просто использовать вместо этого сбалансированное по высоте дерево.
Есть и другие преимущества. Например, некоторые структуры данных, используемые в вычислительной геометрии, основаны на двоичных деревьях поиска, но имеют высокую стоимость вращения дерева. Red-black trees can be rebalanced in at most 3 rotations per insert and delete, а AVL trees can take Ω(lg n) rotations for these operations. As Ralf Hinze noticed, Okasaki's rebalancing scheme for red-black trees (код ML, Haskell, Java, and Ada) не предлагает такую же привязку и может в конечном итоге делать Ω (lg n) вращения при вставке. (Okasaki не делает делецию.)
Кроме того, деревья с балансировкой высоты (и даже деревья AVL) могут быть сохранены, чтобы использовать только один бит информации о балансе на узел. У некоторых деревьев есть только две возможные позиции баланса на каждом узле, например односторонние сбалансированные по высоте деревья, но деревья с четырьмя возможными положениями баланса на каждом узле могут хранить один бит информации о балансе у каждого ребенка, так как initially explained by Brown и более поздние expanded upon by Haeupler et al.
Edit:
В ответ на ваш конкретный запрос в конце вашего вопроса, то здесь есть описание алгоритма для конкатенации два красно-черных дерев. Требуется время O (lg (max (| L |, | R |))), которое слишком велико, чтобы получить асимптотически оптимальное время объединения, описанное выше. Для сравнения, я ожидаю, что the "join" implementation for AVL sets in OCaml's 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 и высоту черного q q, и предположите, что w.l.o.g. p ≤ q.
Из корня R следуйте за левыми детьми, пока не достигнете черного узла 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 новым красным деревом, корень которого является корнем родителя C, левым ребенком из которого является C, перекрашенный черный, а правый ребенок - это черное дерево, состоящее из родного брата C, бабушки и дедушки C корень и дядя С, в этот заказ. Это не увеличивает черную высоту бабушки и дедушки C, но она меняет цвет на красный, что может сделать его корнем или красным ребенком красного родителей, поэтому мы должны снова перебалансироваться и так далее. дерево
- найти черную высоту обоих деревьев: O (LG | L |) + O (Л.Г. | R |)
- Трассировка вниз R в нужном месте: O (Lg | R | - Л.Г. | L |)
- Повороты весь путь обратно до корня: O (LG | Р | - LG | L |)
ни один из них не больше, чем O (Lg | R | + LG | L |) = O (lg (max (| L |, | R |)))
Чтобы сделать это O (lg (min (| L |, | R |))), сначала переверните указатели позвоночника. Тогда вам не нужна черная высота большего дерева, вам нужно только подсчитывать черные узлы спинного хребта до тех пор, пока не останется одно дерево из позвоночника. Затем используйте исходную (не Окасаки) схему балансировки, чтобы убедиться, что вы только перебалансировали O (1) узлы. Наконец, отметьте остальную часть позвоночника, которая не нуждается в перебалансировке для ленивого повторного окрашивания, если это необходимо позже.
Кто-то голосовал, чтобы закрыть мой вопрос как «вне темы». С каких пор деревья RB с темы переполнения стека ?! –