Red-Black tree: Split/Concatenate in log (n) time

Question

По словам Рона Вейна, вы можете выполнять разделение и конкатенацию красно-черного дерева в O (log (n)) времени. См. Его артикул: Efficient Implementation of Red-Black Trees with Split and Catenate Operations

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

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

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

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

Answer 1

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

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

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

Я предлагаю все прочитать Tarjans бумаги вместо