Concatenando / Fusão / Unir duas árvores AVL

Question

Suponha que eu tenho duas árvores AVL e que cada elemento da primeira árvore é menor, então qualquer elemento da segunda árvore. Qual é a maneira mais eficiente para concatenar-los em uma árvore AVL single? Eu procurei em todos os lugares, mas não encontraram nada de útil.

Answer 1

Assumindo que você pode destruir as árvores de entrada:

1. remover o elemento mais à direita para a árvore esquerda, e usá-lo para construir um novo nó raiz, cujo filho esquerdo é a árvore esquerda, e cujo filho direito é a árvore direita: O (log n)
2. determinar e definir esse fator de equilíbrio do nó: O (log n). Em violação (temporária) do invariante, o factor de equilíbrio pode estar fora da gama {-1, 0, 1}
3. girar para obter o fator de volta o equilíbrio na gama: O (log n) rotações: O (log n)

Assim, toda a operação pode ser realizada em O (N log N).

Edit: Pensando bem, é mais fácil raciocinar sobre as rotações no seguinte algoritmo. Também é bastante provável mais rápido:

1. determinar a altura de ambas as árvores:. O (log n)
   Assumindo que a árvore certa é mais alto (o outro caso é simétrica):
2. remover o elemento mais à direita da árvore left (rotação e ajustar a sua altura computadorizada se necessário). Vamos n ser esse elemento. O (N log N)
3. Na árvore direita, navegar esquerda até chegar a um nó cujo subárvore é no máximo um 1 mais alto do que left. Vamos r ser esse nó. O (N log N)

4. substituir esse nó com um novo nó com o valor de n, e subárvores left e r. O (1)
   Por construção, o novo nó é AVL balanceada, e seu mais alto sub 1 de r.

5. incrementar o equilíbrio do seu pai em conformidade. O (1)

6. e reequilíbrio, como você faria depois de inserir. O (N log N)

Answer 2

Uma solução ultra-simples (que funciona sem quaisquer suposições nas relações entre as árvores) é o seguinte:

1. Faça um merge sort de ambas as árvores em um array fundido (simultaneamente iterate ambas as árvores).
2. Criar uma árvore AVL da matriz -. Levar o elemento do meio para ser a raiz, e aplicar de forma recursiva para metades direita e esquerda

Ambos os passos são O (n). O grande problema com isso é que leva O (n) espaço extra.

Answer 3

A melhor solução que eu li para este problema pode ser encontrada aqui . Está muito perto de resposta meriton 's se você corrigir esse problema:

No terceiro passo do algoritmo navega esquerda até chegar o nó cuja árvore sub tem a mesma altura da árvore esquerda . Isso nem sempre é possível, (veja a imagem contra-exemplo). O caminho certo para fazer esta etapa é de dois achado para uma sub-árvore com h altura ou h+1 onde h é a altura da árvore esquerda

Answer 4

Eu suspeito que você só tem que andar uma árvore (esperemos que o menor) e individualmente adicionar cada um de seus elementos para a outra árvore. As operações de exclusão / AVL insert não são projetados para lidar com a adição de uma sub-árvore toda de uma vez.