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

Судя по формулировке вашего вопроса, я не уверен, интересует ли вас объединение наборов или конкатенация, или и то, и другое, или вас интересуют только постоянные структуры данных, которые распространены в 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 , достигают границ в амортизированном (но устойчивом) смысле, treaps, описанные Blandford и Blelloch, достигают границ в рандомизированном смысле , а те описанные Kaplan & Tarjan , достигают их в наихудшее время. Последние также предлагают конкатенацию O (lg lg (min (p, q))), хотя Хинце и Патерсон сомневаются в этом утверждении. Эти деревья не являются прямым ответом на ваш вопрос, который относится к красно-черным деревьям, но они, надеюсь, дают представление о том, что возможно, и документ H&P включает код, а был проверен с помощью Coq ], который можно извлечь в код OCaml.

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

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

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

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

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

Изменить:

В ответ на ваш конкретный запрос в конце вашего вопроса, вот описание алгоритма конкатенации двух красно-черных деревьев. Требуется время O (lg (max (| L |, | R |))), что слишком долго, чтобы получить асимптотически оптимальное время объединения, которое я описал выше. Для сравнения, я ожидаю, что реализация «соединения» для наборов AVL в stdlib OCaml получит производительность 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 ≤ q.

От корня 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 |) )), сначала переверните указатели корешка. Тогда вам не нужна черная высота большего дерева, вам нужно только подсчитывать черные узлы корешка, пока одно дерево не выйдет из корешка. Затем используйте исходную (не схему Окасаки) схему ребалансировки, чтобы убедиться, что вы перебалансируете только O (1) узлов.Наконец, отметьте остальную часть позвоночника, которая не требует повторной балансировки для ленивого перекрашивания, если это потребуется позже.