Junção mais rápida de estruturas de dados do tipo treap com aproximadamente o mesmo tamanho

Dadas duas árvores AVL e T 2 e um valor t r tal que ∀ x ∈ T 1 , ∀ y ∈ T 2 , x < t r < y , é fácil de construir uma nova árvore AVL contendo t r e os valores em T 1 e T 2 , em tempo O ( 1 + | h ( T 1 ) - H ( $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$ , onde h ( T ) indica a altura de uma árvore T (desde que as árvores armazenem sua altura).$O(1+|h(T_1) - h(T_2)|)$$h(T)$$T$

Isso também é possível para árvores preto-vermelho, e eu assumo muitos outros tipos de árvores equilibradas também.

Isso é possível para treaps ou estruturas de dados do tipo treap? E se a gente deixar de fora ?$t_r$

O papel treaps em Algorithmica mostra como fazer isso em esperado tempo. Se existe uma maneira de executar junção O (1) esperada em treaps (ou estruturas de dados semelhantes a treap) com aproximadamente o mesmo tamanho (ou prioridade de raiz), acho que pode ser possível usar um truque de Kaplan & Tarjan no bootstrap os espinhos para fazer treaps (ou estruturas de dados semelhantes a treap) com junção duplamente logarítmica.$O(\min(h(T_1),h(T_2)))$

Não, não é possível fazer isso com Treaps comuns se as prioridades forem aleatórias.

A afirmação exata que farei é que, para realizar essa mesclagem em duas treaps de tamanho igual com prioridades aleatórias, é necessário atualizar os indicadores na expectativa.$\Theta(\log n)$

Aqui está um esboço de prova:

Considere o número de ponteiros que você precisa alterar na expectativa de executar a operação. É mais fácil provar um ligado se não o fizermos inserção t r mas apenas fundir T 1 e T 2 . Considere a espinha direita S 1 de T 1 e da coluna vertebral esquerda S 2 de T 2 . Colora os elementos de S 1 em vermelho e os de S 2 em azul. Ordem S 1 ∪ S $\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$por prioridade. Temos que mudar um ponteiro cada vez que a cor mudar nesta sequência. Como os dois espinhos têm tamanho com alta probabilidade e as prioridades são aleatórias, não é muito difícil perceber que o número de alterações de cores na sequência também é Θ ( log n ) . Então nós precisamos atualizar Θ ( log n ) ponteiros para a fusão (sem adição de t r ).$\Theta(\log n)$$\Theta(\log n)$$\Theta(\log n)$$t_r$

Agora, adicionar ao fazer a mesclagem não ajuda muito. O número de mudanças de ponteiro nesse caso pode ser delimitado da seguinte forma: Ordem S 1 ∪ S 2 ∪ { t r } por prioridade. Exclua tudo menos que t r na sequência. Então, o número de alterações de cores na sequência resultante é o limite inferior. Como t r tem prioridade aleatória, a altura esperada da subárvore enraizada nela na tropa final é O ( 1 ) , portanto, ele possui apenas O ( 1 ) nós de S $t_r$$S_1 \cup S_2 \cup \{t_r\}$$t_r$$t_r$$O(1)$$O(1)$ com prioridade mais baixa do que a expectativa, portanto, perdemos apenasalterações de ponteiro O ( 1 ) em nosso limite inferior ao adicionar t r .$S_1 \cup S_2$$O(1)$$t_r$

Agora, dito isso, provavelmente existe uma maneira de obter uma estrutura de dados "parecida com uma pilha", que permite mesclagens constantes de tempo esperado.

Atualização: veja abaixo uma atualização sobre a incorreta desta operação de associação

Aqui está um esboço muito aproximado de uma possível solução:

Acho que posso ter uma solução para esse problema usando um tipo de árvore B + aleatoriamente balanceada. Como trufas, essas árvores têm uma representação única. Ao contrário de treaps, eles armazenam algumas chaves várias vezes. Talvez seja possível corrigir isso usando um truque das "Árvores de pesquisa enviesada" de Bent et al, de armazenar cada chave apenas no nível mais alto (ou seja, mais próximo da raiz) em que ela aparece)

Uma árvore para um conjunto ordenado de valores exclusivos é criada associando-se primeiro a cada valor a um fluxo de bits, semelhante à maneira como cada valor em um treap é associado a uma prioridade. Cada nó na árvore contém um fluxo de chave e de bit. Os nós que não são folhas contêm, além disso, um número natural que indica a altura da árvore enraizada nesse nó. Nós internos podem ter qualquer número diferente de zero de filhos. Como as árvores B +, todos os caminhos que não se interceptam da raiz até uma folha têm o mesmo comprimento.

Todo nó interno contém (como nas árvores B +) a maior chave k de suas folhas descendentes. Cada um também contém um número natural i, indicando a altura da árvore enraizada em ve fluxo de bits associado a k, a partir do i + 1 º bit em diante. Se toda chave na árvore enraizada em v tem o mesmo primeiro bit em seu fluxo de bits, todo filho de v é uma folha e i é 1 . Caso contrário, os filhos de v são nós internos todos os que têm o mesmo i th bit no fluxo de bits associados com sua chave.$v$$k$$i$$v$$k$$i+1$$v$$v$$i$$1$$v$$i$

Para criar uma árvore a partir de uma lista classificada de chaves com fluxos de bits associados, primeiro colete as chaves em grupos contíguos com base no primeiro bit em seus fluxos. Para cada um desses grupos, crie um pai com a chave e o fluxo de bits da maior chave do grupo, mas excluindo o primeiro bit do fluxo. Agora, faça o mesmo procedimento de agrupamento nos novos pais para criar avós. Continue até que apenas um nó permaneça; essa é a raiz da árvore.

A seguinte lista de chaves e (início de) fluxos de bits é representada pela árvore abaixo dela. Nos prefixos de fluxo de bits, um '.' significa qualquer coisa. Ou seja, qualquer fluxo de bits para a chave A com 0 em primeiro lugar produz a mesma árvore que qualquer outra, assumindo que o fluxo de bits de nenhuma outra chave seja diferente.

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

Todo filho de um nó interno específico tem o mesmo bit em primeiro lugar do seu fluxo de bits. Isso é chamado de "cor" do pai - 0 é vermelho, 1 é verde. A criança tem um "sabor", dependendo do primeiro bit do seu fluxo de bits - 0 é cereja, 1 é hortelã. As folhas têm sabores, mas não cor. Por definição, um nó cereja não pode ter um pai verde e um nó hortelã não pode ter um pai vermelho.

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

Para unir duas árvores de altura igual, verifique primeiro se as raízes são da mesma cor. Nesse caso, corte da raiz esquerda seu filho mais à direita e da raiz direita seu filho mais à esquerda, e junte recursivamente essas duas árvores. O resultado será uma árvore da mesma altura ou uma mais alta, pois as árvores têm o mesmo sabor (veja abaixo). Se o resultado da junção recursiva das duas árvores tiver a mesma altura dos dois filhos cortados, torne-o filho do meio de uma raiz com os filhos restantes da raiz esquerda antes dela e os filhos restantes da raiz direita depois dela. Se for 1 mais alto, faça de seus filhos os filhos do meio de uma raiz, com os filhos restantes da raiz esquerda antes dela e os filhos restantes da raiz direita depois dela. Se as raízes tiverem cores diferentes, verifique se elas têm o mesmo sabor. Se eles fizerem, forneça a eles um novo pai com o fluxo de chaves e bits da raiz direita, eliminando o primeiro bit. Caso contrário, atribua a cada raiz um novo pai com a chave e o fluxo de bits da raiz antiga (excluindo cada primeiro bit) e junte recursivamente essas árvores.

$1/2$$1/2$$O(1)$$1/4$, e as chamadas recursivas subseqüentes sempre estão em árvores com cores diferentes; portanto, a mesma análise se aplica.

$1/2$$O(1)$

$O(1)$

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

A árvore feita por [a,b]tem altura 2, a árvore feita por [c,d]tem altura 2 e a árvore feita por joinEqual (tree [a,b]) (tree [c,d])tem altura 3. No entanto, a árvore feita por [a,b,c,d]tem altura 5.

Aqui está o código que eu usei para encontrar esse erro .