Более быстрое объединение трэпоподобных структур данных с примерно одинаковым размером

Учитывая два дерева AVL и и значение такое что , легко построить новое дерево AVL, содержащее и значения в и за время , где обозначает высоту дерева (до тех пор, пока деревья хранят свою высоту).Т 2 т г ∀ х ∈ T 1 , ∀ у ∈ Т 2 , х < т г < у т т Т 1 Т 2 О ( 1 + | ч ( Т 1 ) - ч ( Т 2 ) | ) ч ( Т ) $T_1$$T_2$$t_r$$\forall x \in T_1, \forall y \in T_2, x < t_r < y$$t_r$$T_1$$T_2$$O(1+|h(T_1) - h(T_2)|)$$h(T)$$T$

Это также возможно для красно-черных деревьев, и я предполагаю много других видов сбалансированных деревьев.

Возможно ли это для трэпов или трэп-подобных структур данных? Что если мы пропустим ?$t_r$

В документе Treaps в Algorithmica показано, как это сделать за ожидаемое время . Если есть способ выполнить ожидаемое соединение O (1) на трэпах (или трэп-подобных структурах данных) с примерно одинаковым размером (или корневым приоритетом), я думаю, что можно было бы использовать хитрость Kaplan & Tarjan для начальной загрузки шипы для создания трепсов (или трэп-подобных структур данных) с двойным логарифмическим соединением.$O(\min(h(T_1),h(T_2)))$

Нет, это невозможно сделать с обычными трепами, если приоритеты случайны.

Точное утверждение, которое я сделаю, состоит в том, что для выполнения такого слияния двух трепов одинакового размера со случайными приоритетами требуется обновление указателей в ожидании.$\Theta(\log n)$

Вот примерный набросок:

Рассмотрим количество указателей, которые вы должны изменить в ожидании выполнения операции. Проще доказать границу если мы не вставляем а просто объединяем и . Рассмотрим правый отдел позвоночника от и отдел позвоночника от . Цвет элементов красный, а элементов синий. Закажите по приоритету. Мы должны менять указатель каждый раз, когда цвет меняется в этой последовательности. Поскольку оба шипа имеют размерt r T 1 T 2 S 1 T 1 S 2 T 2 S 1 S 2 S 1 ∪ S 2 Θ ( log n ) Θ ( log n ) Θ ( log n ) t $\Theta(\log n)$$t_r$$T_1$$T_2$$S_1$$T_1$$S_2$$T_2$$S_1$$S_2$$S_1 \cup S_2$$\Theta(\log n)$с высокой вероятностью, а приоритеты являются случайными, нетрудно увидеть, что количество изменений цвета в последовательности также равно . Поэтому нам нужно обновить указатели для слияния (без добавления ).$\Theta(\log n)$$\Theta(\log n)$$t_r$

Теперь добавление во время слияния не очень помогает. Количество изменений указателя в этом случае может быть ограничено снизу следующим образом: Порядок по приоритету. Удалите все, что меньше в последовательности. Тогда количество изменений цвета в полученной последовательности является нашей нижней границей. Так как имеет случайный приоритет, ожидаемая высота поддерева, укорененного в нем в конечном трэпе, равна , поэтому он имеет только узлов с более низким приоритетом, чем ожидалось, поэтому мы потеряли только указатель изменяется в нашей нижней границе при добавлении .$t_r$$S_1 \cup S_2 \cup \{t_r\}$$t_r$$t_r$$O(1)$$O(1)$$S_1 \cup S_2$$O(1)$$t_r$

Тем не менее, возможно, есть способ получить структуру данных, похожую на «трещотку», которая допускает постоянные ожидаемые слияния времени.

Обновление: см. Ниже обновление о неправильности этой операции соединения

Вот очень грубый набросок возможного решения:

Я думаю, что у меня может быть решение этой проблемы с использованием типа случайно сбалансированного B + -дерева. Как и у ловушек, эти деревья имеют уникальное представление. В отличие от трэпов, они хранят несколько ключей несколько раз. Возможно, это можно исправить, используя трюк из «Biased Search Trees» Бента и др., В котором каждый ключ хранится только на самом высоком (то есть ближайшем к корню) уровне, на котором он появляется).

Дерево для упорядоченного набора уникальных значений создается путем первого связывания каждого значения с потоком битов, аналогично тому, как каждое значение в трэпе связано с приоритетом. Каждый узел в дереве содержит как ключ, так и поток битов. Нелистовые узлы содержат, кроме того, натуральное число, указывающее высоту дерева, укорененного в этом узле. Внутренние узлы могут иметь любое ненулевое количество дочерних узлов. Как и в случае B + -деревьев, каждый несамопересекающийся путь от корня до листа имеет одинаковую длину.

Каждый внутренний узел содержит (как в B + -деревьях) самый большой ключ k своего потомка. Каждый из них также содержит натуральное число i, указывающее высоту дерева с корнем в v , и поток битов, связанных с k, начиная с i + 1- го бита и далее. Если каждый ключ в дереве с корнем v имеет один и тот же первый бит в своем потоке битов, каждый дочерний элемент v является листом, а i равно 1 . В противном случае дочерние элементы v являются внутренними узлами, каждый из которых имеет одинаковый i- й бит в потоке битов, связанном с их ключом.$v$$k$$i$$v$$k$$i+1$$v$$v$$i$$1$$v$$i$

Чтобы создать дерево из отсортированного списка ключей со связанными битовыми потоками, сначала соберите ключи в смежные группы на основе первого бита в их потоках. Для каждой из этих групп создайте родителя с ключом и потоком битов самого большого ключа в группе, но исключая первый бит потока. Теперь сделайте ту же процедуру группировки новых родителей, чтобы создать бабушку и дедушку. Продолжайте, пока не останется только один узел; это корень дерева.

Следующий список ключей и (начало) битовых потоков представлен деревом под ним. В префиксах битового потока - «.» значит любой бит. То есть любой поток битов для ключа A с нулем в первую очередь создает то же дерево, что и любой другой, при условии, что поток битов другого ключа не отличается.

A 0...
B 00..
C 10..
D 0...
E 0011
F 1...
G 110.
H 0001


        ____H____
       /         \
      E           H
      |          / \
    __E__       G   H
   /  |  \      |   |
  B   C   E     G   H
 / \  |  / \   / \  |
A   B C D   E F   G H

Каждый дочерний элемент определенного внутреннего узла имеет одинаковый бит в первую очередь своего потока битов. Это называется «цвет» родителя - 0 красный, 1 зеленый. У ребенка есть «аромат» в зависимости от первого бита его потока битов - 0 - вишня, 1 - мята. Листья имеют вкус, но не имеют цвета. По определению узел вишни не может иметь зеленого родителя, а узел мяты не может иметь красного родителя.

$n$$2^{1-n}$ ${n-1}\choose{i-1}$$(n+1)/2$$n \geq 2$$\leq \frac{3}{4}n$$O(\lg n)$

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

$1/2$$1/2$$O(1)$$1/4$и последующие рекурсивные вызовы всегда выполняются на деревьях разных цветов, поэтому применяется один и тот же анализ.

$1/2$$O(1)$

$O(1)$

a 01110
b 110..
c 10...
d 00000

Дерево, созданное им, [a,b]имеет высоту 2, дерево, созданное им, [c,d]имеет высоту 2, а дерево, созданное им, joinEqual (tree [a,b]) (tree [c,d])имеет высоту 3. Однако дерево, созданное им, [a,b,c,d]имеет высоту 5.

Вот код, который я использовал, чтобы найти эту ошибку .