Mesclando duas árvores de pesquisa binária

Estou procurando um algoritmo para mesclar duas árvores de pesquisa binária de tamanho e alcance arbitrários. A maneira óbvia de implementar isso seria encontrar subárvores inteiras cujo intervalo pode caber em um nó externo arbitrário na outra árvore. No entanto, o pior caso de tempo de execução para esse tipo de algoritmo parece estar na ordem de O(n+m)onde ne mé o tamanho de cada árvore, respectivamente.

No entanto, me disseram que isso poderia ser feito em O(h), onde hé a altura da árvore com a altura maior. E eu estou completamente perdido em como isso é possível. Eu tentei experimentar girar uma das árvores primeiro, mas girar uma árvore em uma espinha já é O (h).

ds.algorithms ds.data-structures tree efritz
fonte

Eu não sei erick, eu tenho a mesma pergunta também.

Para ser justo, essa foi uma pergunta feita em uma lição de casa de Algoritmos. Acontece que O (h) é muito rigoroso em um tempo de execução, pois a pergunta esqueceu de fornecer mais informações necessárias: que todas as chaves de uma árvore eram menores que todas as chaves da árvore correta.

efritz

Estou faltando alguma coisa, a fusão de árvores binárias não seria fácil O(log n)com uma simples função de nó de movimentação?

@ AT Sim, mas não sabíamos que as chaves de um BST eram mutuamente exclusivas do outro.

efritz

Esta é uma árvore vermelho-preta, não uma BST. Um preto vermelho (assim como árvores e montes AVL) são tipos especiais de árvores que mantêm uma propriedade vinculada à altura. BSTs de baunilha podem ser uma única coluna. Tente inserir uma série de números que não diminua ou não aumente no BST e você verá que a altura dessas árvores é realmente n. Somente árvores binárias completas ou completas têm uma altura logarítmica em relação ao número total de nós.

efritz

Respostas:

No ArXiv: 1002.4248 , John Iacono e Özgür Özkan descrevem um algoritmo relativamente simples para mesclar duas árvores de pesquisa binária no tempo amortizado de ; a análise é a parte mais difícil. [ Atualização: Como Joe observa corretamente em sua resposta, esse algoritmo é devido a Brown e Tarjan.] Eles também descrevem uma estrutura de dados de dicionário mais complicada, baseada em listas de pulos tendenciosas, que suporta mesclagens no tempo amortizado de . $O(\log^2 n)$ $O(\log n)$

Por outro lado, um limite de pior caso de é impossível. Considere duas árvores de pesquisa binária com nós, um armazenando números inteiros pares entre e , o outro armazenando números inteiros ímpares entre e . A mesclagem das duas árvores cria uma nova árvore de pesquisa binária que armazena todos os números inteiros entre e . Em qualquer dessas árvores, uma fração constante dos nós tem paridade diferente dos pais. (Prova: o pai de uma folha ímpar deve ser par.) Assim, a mesclagem das árvores pares e ímpares requer a alteração de ponteiros . $O(\log n)$ $n$ $2$ $2n$ $1$ $2n-1$ $1$ $2n$ $\Omega(n)$

Jeffε
fonte

Uma observação: se eu li a descrição neste documento corretamente, essas árvores não suportam inserção e exclusão. A mesclagem segue apenas o procedimento para mesclar árvores de busca por dedos (descritas na resposta de Joe). O conjunto restrito de operações permite uma análise melhor que a .

O (\lg^{2} n)

$O(\lg^2 n)$

O (n \lg \frac{m}{n})

$O(n \lg \frac{m}{n})$

Jbapple

A análise aprimorada deve-se à amortização, não à restrição das operações permitidas. Inserções e exclusões podem ser suportadas com divisões e mesclagens (na verdade "junções") no mesmo limite de tempo amortizado .

O (l o g n)

$O(log n)$

21412 Jeff Jeff

Por curiosidade, o tempo é afetado se as árvores são armazenadas em matrizes em vez de listas vinculadas (que eu assumo ser o que você quis dizer quando disse "alterando ... ponteiros ")?

Ω (n)

$\Omega(n)$

mtahmed

Por padrão, "árvores de pesquisa binária" são estruturas baseadas em ponteiro (não "listas vinculadas"); cada nó aponta para seus dois filhos e possivelmente para o pai. Mas o limite inferior não depende da representação precisa. Existem maneiras de mesclar duas árvores de pesquisa binária de nó , portanto, qualquer algoritmo baseado em comparação precisa de pelo menos comparações para escolher o caminho certo.

(\binom{2 n}{n})

$\binom{2n}{n}$

n

$n$

\log_{2} (\binom{2 n}{n}) \geq 2 n - O (\log n)

$\log_2 \binom{2n}{n} \ge 2n - O(\log n)$

Jeffε

@ Jɛ ﬀ E: Concordo que divisões e junções são suportadas, mas não acho que a criação ou destruição de árvores seja. Por exemplo, se eu quiser excluir "x" do alfabeto, não recebo apenas "a..wyz", mas também "x". O tamanho do universo (que é , consulte a seção 2.1) não muda. Além disso, a introdução da seção 1 observa que os conjuntos devem particionar o universo, o que eu interpreto (talvez incorretamente) para significar que cada elemento do universo está em alguma árvore. Então, do jeito que eu li, essa construção não funciona em universos ilimitados. É assim que devo escrever meu comentário acima.

n

$n$

jbapple

Você pode achar útil essa referência: Brown e Tarjan, um algoritmo de mesclagem rápida , no qual os autores mostram como mesclar árvores binárias balanceadas (AVL) em ideal para algoritmos baseados em comparação). e são os comprimentos das listas classificadas representadas pelas árvores de pesquisa binária e supõe-se que . $O(n \log \frac{m}{n})$ $m$ $n$ $m \geq n$

Você também pode ver uma discussão sobre diferentes técnicas para mesclar conjuntos ordenados na seção 11.5 deste documento, sobre árvores de pesquisa por dedo

Joe
fonte

Tanto o

tempo limite e o limite inferior correspondente assumem que

O (n \log \frac{m}{n})

$O(n\log \frac{m}{n})$

m \geq n

$m\ge n$

21412 Jeff Jeff

Eu pensei que isso estava implícito no prazo, mas editei a pergunta para torná-la explícita.

31712 Joe

Você pode mesclar árvores no pior caso, $\bf\mathcal{O}(1)$ enquanto ainda suporta: inserir, excluir e pesquisar em . $\mathcal{O}(log\ n)$

Brodal, Gerth Stølting, Christos Makris e Kostas Tsichlas. 'Listas classificadas por catenabilidade em tempo constante puramente funcional no pior dos casos' . Em Anais da 14ª Conferência sobre Simpósio Anual Europeu - Volume 14, 172–183. ESA'06. Londres, Reino Unido, Reino Unido: Springer-Verlag, 2006. [ PDF ]

AT
fonte

Sua estrutura de dados suporta junção em O (1) tempo amortizado, não mesclagem. Todos os elementos em uma árvore devem ser menores que todos os elementos na outra.

Jeffε

Ahh verdade. Teve que reler o artigo: "Join (

), une as duas árvores em uma árvore. As árvores

são ordenadas no sentido de que todos os elementos de

são menores ou maiores que o menor ou menor. elemento maior de

. Suponha, sem perda de generalidade, que

. Nesse caso, a árvore

é anexada à árvore

, e o resultado dessa operação é a árvore

T_{i}

$T_i$

T_{j}

$T_j$

T_{i}

$T_i$

T_{j}

$T_j$

T_{j}

$T_j$

T_{i}

$T_i$

w (T_{i}) = w (T_{j})

$w(T_i) = w(T_j)$

T_{j}

$T_j$

T_{i}

$T_i$

T_{i} \cdot T_{j}

$T_i \centerdot T_j$

T_{i}

$T_i$