São dadas duas árvores AVL e . Escreva uma função que faça a intercalação (merge) das duas árvores AVL fornecidas gerando, ao final, uma árvore AVL válida. Dado que a primeira árvore tem nós e a segunda árvore tem nós, sua função de intercalação deve levar tempo . Suponha que os números de nós e das árvores também sejam dados como entrada.

Passo 1

Beleza, vamos lá! Você me pediu para resolver um exercício sobre árvores AVL. O enunciado diz que temos duas árvores AVL, chamadas e , com respectivamente e nós. Precisamos escrever uma função que una essas duas árvores em uma única árvore AVL válida, garantindo que essa operação seja feita em tempo . Para isso, vamos precisar entender o que é uma árvore AVL, como elas funcionam e como podemos combinar duas delas de forma eficiente.

Passo 2

Primeiro, vamos lembrar o que é uma árvore AVL. Uma árvore AVL é um tipo de árvore binária de busca (BST) que mantém um equilíbrio para garantir que as operações de busca, inserção e remoção sejam eficientes, com complexidade . O equilíbrio é mantido garantindo que a diferença de altura entre as subárvores esquerda e direita de qualquer nó seja no máximo 1.

Passo 3

Agora, para unir duas árvores AVL e , precisamos garantir que a árvore resultante também seja uma árvore AVL válida. Uma abordagem eficiente para isso, que atenda ao requisito de tempo , é realizar um percurso em ordem (in-order traversal) nas duas árvores para obter duas listas ordenadas de elementos. Depois, mergeamos essas listas em uma única lista ordenada. Por fim, construímos uma nova árvore AVL balanceada a partir dessa lista combinada.

Passo 4

Vamos detalhar cada uma dessas etapas:
  1. Percurso em Ordem nas Árvores AVL: Como as árvores AVL são árvores binárias de busca, um percurso em ordem vai nos dar os elementos em ordem crescente. Fazemos isso para e , obtendo duas listas ordenadas de elementos.
  2. Intercalação das Listas Ordenadas: Com as duas listas ordenadas, podemos intercalá-las em uma única lista ordenada. Como as listas já estão em ordem, podemos fazer isso de forma eficiente percorrendo ambas simultaneamente.
  3. Construção da Árvore AVL a Partir da Lista Ordenada: Com a lista combinada e ordenada, construímos uma nova árvore AVL balanceada. Uma maneira eficiente de fazer isso é selecionar o elemento do meio da lista como raiz, e recursivamente fazer o mesmo para os sublistas da esquerda e da direita, garantindo o balanceamento da árvore.

Passo 5

Vamos agora esboçar como seria essa função em termos de código (pseudocódigo):
def merge_avl_trees(T1, m, T2, n):

Passo 6

list1 = in_order_traversal(T1)
list2 = in_order_traversal(T2)

Passo 7

merged_list = merge_sorted_lists(list1, list2)

Passo 8

merged_avl = sorted_list_to_avl(merged_list)
return merged_avl

Passo 9

Explicando cada função utilizada:
  • in_order_traversal(tree): Realiza um percurso em ordem na árvore e retorna uma lista dos elementos em ordem crescente.
  • merge_sorted_lists(list1, list2): Recebe duas listas já ordenadas e retorna uma única lista ordenada contendo todos os elementos de ambas as listas.
  • sorted_list_to_avl(sorted_list): Constrói uma árvore AVL balanceada a partir de uma lista ordenada. Ele escolhe o elemento do meio como raiz e faz isso recursivamente para as sublistas esquerda e direita.

Passo 10

Quanto à complexidade de tempo:
  • O percurso em ordem nas duas árvores leva e respectivamente.
  • A intercalação das duas listas ordenadas leva .
  • A construção da árvore AVL a partir da lista ordenada também leva .
Portanto, toda a operação respeita a complexidade de tempo conforme solicitado.

Resposta

Seguinte, para unir as duas árvores AVL e com e nós respectivamente em tempo , seguimos estes passos:
  1. Realizamos um percurso em ordem em e para obter duas listas ordenadas.
  2. Intercalamos essas duas listas em uma única lista ordenada.
  3. Construímos uma nova árvore AVL balanceada a partir da lista combinada.
Assim, a função de intercalação retorna uma árvore AVL válida resultante da união das duas árvores iniciais, respeitando a complexidade de tempo .

Exercícios relacionados

Implemente uma rotação dupla à direita sem utilizar uma rotação esquerda e depois uma direita.
Mostre uma árvore AVL que possua um nó cuja remoção resulta em uma árvore não-AVL , tal que não possa ser balanceada por meio de uma única rotação (simples ou dupla). Desenhe a árvore , especifique o nó a a ser removido, e explique por quê a árvore resultante não pode ser balanceada com uma única rotação.
Suponha que, agora, todo nó da árvore AVL tem um novo campo chamado parent que nada mais é que um ponteiro para nó pai. Como a raiz não tem pai, seu campo parent aponta para nulo).
Implemente todas as funções da árvore AVL vistas em sala iterativamente (sem usar recursão) e atualize os campos parent de cada nó adequadamente.
Projete um contador assíncrono de módulo 13 crescente (contagem de 0 a 12).