Я не уверен по формулировке вашего вопроса, заинтересованы ли вы в объединении или объединении множеств или в обоих, или если вы заинтересованы только в постоянных структурах данных, которые распространены в OCaml или также в эфемерных структурах.
Реализация красно-черных деревьев с пальцами описана Хизер Д. Бут в главе из ее диссертации .Пальцами красно-черное дерево размера n можно разбить на два дерева размером p и q за время амортизации O (lg (min (p, q))), и два красно-черных дерева размера p и q можносоединены в той же границе.Кроме того, элемент может быть добавлен или удален на любом конце rb-дерева за время амортизации O (1).С помощью этих операций можно получить амортизированное объединение времени O (p lg (q / p)) (для p Указанные выше границы амортизируются в традиционном смысле.Для функционального языка, такого как OCaml, может потребоваться ограничение, которое применяется, когда структура данных используется постоянно.Я не думаю, что описание Бута достигнет всех тех границ, когда деревья используются постоянно.Например, вставка в палец может занять ω (1) перекрашивание.Это может быть решено с помощью ленивых перекрашиваний, обсуждаемых в Driscoll et al. «Создание структур данных постоянными» .
С другой стороны, я думаю, что анализ Бута может показать, что конкатенация все ещеO (lg (max (p, q))) даже при постоянном использовании.Я менее оптимистичен в отношении границы объединения.
Операции над множествами с асимптотически оптимальными временными границами возможны в функциональной обстановке.Те , которые описаны Hinze & Paterson , достигают границ в амортизированном (но настойчивом) смысле, трэпы , описанные Blandford & Blelloch, достигают границ в рандомизированном смысле , а эти описанные Kaplan & Tarjan достичь их в худшем случае.Последние также предлагают конкатенацию O (lg lg (min (p, q))), хотя Хинце и Патерсон сомневаются в этом утверждении.Эти деревья не являются прямым ответом на ваш вопрос, который характерен для красно-черных деревьев, но мы надеемся, что они дают представление о том, что возможно, и статья H & P содержит код, и был подтвержден с помощью Coq , который может быть извлечен в код OCaml.
Еще два указателя, которые могут вас заинтересовать: Brodal et al.представлены деревья поиска с O (lg n) поиск, вставка и удаление и O (1) concat даже в функциональной настройке .Кроме того, Atallah et al.утверждают, что описывают красно-черное дерево с амортизированным O (1) конкатом (предположительно, только эфемерно) , но Бухсбаум и Гудрич утверждают, что в этой структуре есть несколько недостатков .
Последнее замечание о полезности красно-черных деревьев: в одном из комментариев к одному из ответов на этот вопрос вы говорите:
Единственное преимущество красно-черного дерева заключается в том, чтовспомогательная информация (красная или черная) имеет только 1 бит на ветвь.Добавив высоту, вы потеряли это преимущество и могли бы вместо этого просто использовать сбалансированное по высоте дерево.
Есть и другие преимущества.Например, некоторые структуры данных, используемые в вычислительной геометрии, основаны на бинарных деревьях поиска, но имеют высокую стоимость вращения деревьев. Красно-черные деревья могут быть перебалансированы максимум за 3 поворота на каждую вставку и удалить , тогда как Деревья AVL могут принимать Ω (lg n) поворотов для этих операций . Как заметил Ральф Хинце , Схема ребасинга Окасаки для красно-черных деревьев (код доступен в ML , Haskell , Java,и Ada ) не предлагает ту же границу и может в конечном итоге делать Ω (lg n) поворотов при вставке.(Okasaki не представляет удаление.)
Кроме того, сбалансированные по высоте деревья поиска (и даже деревья AVL) могут храниться так, чтобы использовать только один бит информации о балансе на узел. Некоторые деревья имеют только две возможные позиции баланса в каждом узле, например, односторонние сбалансированные по высоте деревья, но деревья с максимум четырьмя возможными позициями баланса на узел могут хранить один бит информации о балансе у каждого дочернего элемента, как , первоначально объясненное как Браун и позже , расширенный Хауплером и др.
Edit:
В ответ на ваш конкретный запрос в конце вашего вопроса приведено описание алгоритма объединения двух красно-черных деревьев. Требуется время O (lg (max (| L |, | R |))), которое слишком велико для получения асимптотически оптимального времени объединения, которое я описал выше. Для сравнения я ожидаю, что реализация "соединения" для наборов AVL в stdlib OCaml получает производительность O (h1-h2), где h1 - высота более высокого дерева, хотя на самом деле она объединяет два дерева AVL, заданные элемент, который помещается между ними, в то время как алгоритм ниже должен найти и удалить этот элемент миномета из одного из его аргументов. Этого можно избежать, только сохраняя элементы на листьях, как в дереве B +, но у этого есть космическое наказание за то, что нужно хранить кучу указателей на элементы в неконечных узлах, чтобы вести поиск. В любом случае, это не приведет к постоянному времени соединения для деревьев такой же высоты, как код соединения AVL в stdlib OCaml, поскольку вам все равно придется вычислять высоту черного для каждого дерева, как объяснено ниже.
Учитывая два непустых красно-черных дерева L и R, мы создадим новое красно-черное дерево, которое является объединением L и R. Это займет время, пропорциональное O (lg
(max (| L |, | R |))), где | L | обозначает количество узлов в L.
Сначала удалите самый большой элемент из L, c. Затем найдите черную высоту L и R. Под «черной высотой» я подразумеваю количество черных узлов на любом пути из
корень листа. Согласно красно-черным инвариантам дерева, это константа на всех путях любого данного дерева. Назовите черную высоту L р и черную высоту Р q и предположим,
w.l.o.g. p & le; д.
От корня R следуйте по левым потомкам до достижения черного узла R 'с высотой p. Создайте новое красное дерево C с корневым элементом c, левым потомком L и правым
ребенок R '. Поскольку L является красно-черным деревом само по себе, его корень черный, и цветовые инварианты не нарушаются при или ниже C. Кроме того, высота черного C
это р.
Однако мы не можем просто соединить 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, в
этот порядок. Это не увеличивает черную высоту прародителя 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 |))), сначала поменяйте местами указатели позвоночника. Тогда вам не нужна черная высота большего дерева, вам нужно только считать черные узлы позвоночника, пока одно дерево не выйдет из позвоночника. Затем используйте оригинальную (не Okasaki's) схему перебалансировки, чтобы убедиться, что вы перебалансируете только O (1) узлов. Наконец, отметьте остальную часть позвоночника, которая не нуждается в перебалансировке для ленивого перекрашивания при необходимости позже.