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

16

Учитывая два дерева AVL и и значение такое что , легко построить новое дерево AVL, содержащее и значения в и за время , где обозначает высоту дерева (до тех пор, пока деревья хранят свою высоту).Т 2 т гх T 1 , у Т 2 , х < т г < у т т Т 1 Т 2 О ( 1 + | ч ( Т 1 ) - ч ( Т 2 ) | ) ч ( Т ) ТT1T2TрxT1,yT2,x<tr<YTрT1T2О(1+|час(T1)-час(T2)|)час(T)T

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

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

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

jbapple
источник
Вот некоторый код на Haskell, который я написал, показывающий быстрое объединение деревьев AVL примерно одинакового размера: haskell.pastebin.com/nfGV8Ffz
jbapple
Я сомневаюсь, что это возможно, потому что кажется (без доказательства), что ожидаемая глубина нового узла (содержащая значение t_r) больше, чем постоянная, даже в случае, когда h (T_1) = h (T_2).
Цуёси Ито
Цуёси Ито: Я согласен, если вы назначаете новому узлу приоритет так же, как вы назначаете приоритеты другим узлам. Что если вы назначите ему приоритет, который гарантированно будет выше, чем у корневых узлов? Это разрушает природу приоритетов IID, но что, если затем вы пометите другие приоритеты как смещенные, как-то, как пути в постоянных красно-черных деревьях отмечены в конечных точках? Или что, если хранить значения только в листьях трэпа и выполнять соединение без t_r?
JBapple
Узлы в трэпах с n потомками имеют i оставленных потомков с вероятностью 1 / n. Это может способствовать увеличению времени слияния даже для трэпов одинакового размера - выбор нового корня требует перехода к нему, который, поскольку средняя глубина дерева равна Theta (lg n), также занимает время Theta (lg n). Что если в узле treap с n потомками я оставил детей с вероятностью (n выберите i) / 2 ^ n, а значения сохранятся только на листьях, как в B + -дереве. Затем соединение двух одинакового размера перераспределяет небольшое количество элементов из одного дерева в другое в ожидании.
jbapple
Если мои расчеты верны, то ожидаемое количество перераспределяемых элементов равно Theta (sqrt n), которое, если предположить, что все остальное можно было бы обработать (например, свойство поиска по пальцу), все равно потребовало бы времени Theta (lg n) в ожидании. Как насчет использования еще более узкого дистрибутива?
jbapple

Ответы:

3

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

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

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

Рассмотрим количество указателей, которые вы должны изменить в ожидании выполнения операции. Проще доказать границу если мы не вставляем а просто объединяем и . Рассмотрим правый отдел позвоночника от и отдел позвоночника от . Цвет элементов красный, а элементов синий. Закажите по приоритету. Мы должны менять указатель каждый раз, когда цвет меняется в этой последовательности. Поскольку оба шипа имеют размерt r T 1 T 2 S 1 T 1 S 2 T 2 S 1 S 2 S 1S 2 Θ ( log n ) Θ ( log n ) Θ ( log n ) t rΘ(logn)trT1T2S1T1S2T2S1S2S1S2Θ(logn)с высокой вероятностью, а приоритеты являются случайными, нетрудно увидеть, что количество изменений цвета в последовательности также равно . Поэтому нам нужно обновить указатели для слияния (без добавления ).Θ(logn)Θ(logn)tr

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

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


источник
Да, я ищу структуру данных, похожую на треп. Хотя я упомянул столько же в комментариях и своем несуществующем ответе, я не включил его в заголовок или вопрос.
jbapple
Спасибо за Ваш ответ. Я изменил название и текст вопроса, чтобы он был менее двусмысленным.
jbapple
1

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

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

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

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

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

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

Следующий список ключей и (начало) битовых потоков представлен деревом под ним. В префиксах битового потока - «.» значит любой бит. То есть любой поток битов для ключа 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 - мята. Листья имеют вкус, но не имеют цвета. По определению узел вишни не может иметь зеленого родителя, а узел мяты не может иметь красного родителя.

n21n (n1i1)(n+1)/2n234nO(lgn)

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

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

1/2O(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.

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

jbapple
источник