Красно-черное дерево: разделение/объединение в лог(n) раз

По словам Рона Вейна, вы можете разделить и объединить красно-черные деревья за время O (log (n)). См. его статью: Эффективная реализация красно-черных деревьев с операциями разделения и объединения

Однако я все еще не уверен, что время работы сплита действительно верно.

Идея состоит в том, что split использует конкатенации log(n) в наихудшем случае. Эти конкатенации выполняются быстро, так как мы можем найти узел p, запомнив p из последней конкатенации.

Проблема в том, что конкатенация запускает алгоритм исправления (балансировки), который, насколько мне известно, требует O(log n) (см. шаг 5 в псевдокоде для конкатенации). Это дает мне время работы log(n)*log(n), так как расщепление приведет к конкатенации log(n) в наихудшем случае.

Рон Вейн не принимает во внимание алгоритм исправления в своей аргументации. Что я упустил в своем анализе, или алгоритм неверен?


concatenation split algorithm red-black-tree binary-search-tree
person Theis F. Hinz    schedule 13.03.2015    source источник
comment
Вероятно, это аргумент амортизации, который подразумевает, что не все исправления действительно дороги.   -  person Niklas B.    schedule 13.03.2015
comment
Хорошая мысль, но это было так, конечный результат, по крайней мере, был бы в амортизированном времени, а это не так. Так что не думайте, что это так. Но спасибо за ответ   -  person Theis F. Hinz    schedule 13.03.2015
comment
Это не то, что я имею в виду. Если вы можете ограничить общую работу по исправлению внутри операции разделения (например, с помощью амортизации), вы получите правильную границу для наихудшего случая для разделения.   -  person Niklas B.    schedule 13.03.2015
comment
Ах, я вижу - Хорошая мысль. Но не видно, что это правда.   -  person Theis F. Hinz    schedule 13.03.2015
comment
Однако, когда мы спускаемся по дереву, мы можем легко пройти одновременно по самому правому пути T1 и самому левому пути T2 и найти узлы, которые имеют ту же черную высоту, что и κ. Таким образом, каждая операция катенации выполняется за постоянное амортизированное время, а общее время выполнения всей процедуры равно O(C log n).   -  person Niklas B.    schedule 13.03.2015
comment
Да, я понимаю это. Это говорит о том, что узел p можно найти, спускаясь по T1 и T2, пока вы спускаетесь по дереву. Но конкатенации log(n) по-прежнему добавляют красные опорные узлы, которые мы должны исправить. И это не входит в этот аргумент. Я ошибаюсь?   -  person Theis F. Hinz    schedule 13.03.2015
comment
Да, авторы утверждают, что конкаты могут быть выполнены за постоянное амортизированное время при данных обстоятельствах. Полный аргумент находится в ссылке Tar83a.   -  person Niklas B.    schedule 13.03.2015
comment
Хорошо. Спасибо. Я заказал книгу, и надеюсь получить ее в ближайшее время. Спасибо за помощь   -  person Theis F. Hinz    schedule 13.03.2015
comment
На самом деле она есть в Google Книгах, так что вы сможете просмотреть интересные страницы.   -  person Niklas B.    schedule 13.03.2015

Ответы (1)


arrow_upward
1
arrow_downward

В будущем. Если у кого-то снова возникнет та же проблема: у Тарьяна есть некоторые важные отличия в алгоритме по сравнению с тем, что делает Рон Вейн. Я до сих пор не смог увидеть, что Вейн прав в своем алгоритме, но Тарьян прав. Поэтому я предлагаю вам использовать его вместо этого.

Первый важный момент заключается в том, что алгоритм балансировки стоит O(log(d)), где d — глубина, с которой вы начинаете балансировку. Алгоритм Тарьяна тогда отличается тем, что начинается с разделенного ключа и движется по пути к корню. Сделав это, вы увидите, что поддеревья, которые вы объединяете, имеют примерно одинаковую глубину. Таким образом, "d" всегда будет маленьким. Таким образом, это можно сделать гораздо быстрее.

Во-вторых, Тарьян предлагает расширить все узлы таким образом, чтобы они знали свой ранг (черная глубина своих поддеревьев + он сам). Делая это, мы можем узнать, какое дерево самое большое за время O(1). Также можно найти разницу в высоте за время O(1).

Я предлагаю всем прочитать статью Тарьяна вместо статьи Вейна.

person Theis F. Hinz    schedule 10.04.2015
comment
Пожалуйста, не могли бы вы опубликовать ссылку на алгоритм Тарьяна? У меня есть некоторые проблемы, чтобы найти его. - person Leonardo Saracini; 28.01.2018