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

17

Стандартная библиотека OCaml имеет замечательную реализацию Set , которая использует очень эффективный алгоритм разделения и покоя для вычисления union двух наборов. Я считаю, что он берет целые поддеревья (а не только отдельные элементы) из одного набора и вставляет их в другой набор, при необходимости перебалансируя.

Мне интересно, требуется ли эта информация о высоте, которая хранится в дереве AVL, который использует OCaml, или если это также возможно с красно-черными деревьями. Например, можно ли более эффективно конкатенировать пару красно-черных деревьев, чем просто повторять по второму дереву, добавляя его элементы в конец первого дерева?

    
задан Jon Harrop 05.07.2010 в 03:49
источник
  • Кто-то проголосовал, чтобы закрыть мой вопрос как «вне темы». С каких пор деревья RB с темы переполнения стека ?! –  Jon Harrop 05.07.2010 в 22:44

4 ответа

39

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

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

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

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

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

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

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

  

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

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

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

Edit:

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

    
ответ дан jbapple 11.07.2010 в 19:45
  • Upvote исправил вашу проблему с кармой. Есть ли шанс, что вы можете вернуться и отредактировать? Это похоже на потенциально хороший ответ, который может быть значительно улучшен с помощью интерактивных ссылок. –  msandiford 12.07.2010 в 03:21
  • Замечательно, спасибо! –  Jon Harrop 12.07.2010 в 03:26
  • @spong: да, я сделаю это прямо сейчас. Спасибо за напоминание. –  jbapple 12.07.2010 в 03:28
  • +1. для хорошо исследованного ответа! –  Jul 12 '10 at 2:16 12.07.2010 в 04:16
3

Поскольку вы, кажется, говорите о 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), проверить: Ссылка

Также проверьте: Ссылка , проблема 14.2.     

ответ дан Aryabhatta 05.07.2010 в 22:27
  • Похоже, что они делали это только в O (log n), увеличивая дерево с информацией о высоте в каждом узле, после чего оно больше не является обычным красно-черным деревом. –  Jon Harrop 05.07.2010 в 22:47
  • @Jon. Даже с этой информацией мы можем считать это красно-черным деревом. Это не меняет того факта, что вставки / удаления и т. Д. Все еще O (logn), а цвета узлов следуют за инвариантами дерева rb. В любом случае, я не вижу, как еще :-) –  06.07.2010 в 06:19
  • @Moron: Единственное преимущество красно-черного дерева заключается в том, что вспомогательная информация (красная или черная) только 1 бит для каждой ветви. Добавляя высоту, вы потеряли это преимущество и могли бы просто использовать вместо этого сбалансированное по высоте дерево. –  Jon Harrop 06.07.2010 в 16:14
  • @Jon: Если Тарьян и Слатор подумают, что достаточно важно опубликовать статью, я не могу ее легко отбросить :-). В любом случае вы можете сделать это в O (log ^ 2 (n)), если не поддерживать информацию о высоте и которая по-прежнему превосходит линейное время. –  Jul 6 '10 at 14:23 06.07.2010 в 16:23
  • @Jon: Я не рассматривал детали алгоритма, но всякий раз, когда вам нужна высота, просто пересчитайте его в O (logn). В худшем случае это сделает алгоритм O (log ^ 2 (n)). –  Jul 6 '10 at 14:39 06.07.2010 в 16:39
Показать остальные комментарии
1

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

    
ответ дан cos 13.07.2012 в 02:39
0

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

    
ответ дан ony 05.07.2010 в 16:00