São dadas duas árvores AVL T1 e T2. 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 m nós e a segunda árvore tem n nós, sua função de intercalação deve levar tempo O(m+n). Suponha que os números de nós m e n 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 T1 e T2, com respectivamente m e n 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 O(m+n). 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(log n). 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 T1 e T2, 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 O(m+n), é 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 T1 e T2, 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 O(m) e O(n) respectivamente.
  • A intercalação das duas listas ordenadas leva O(m+n).
  • A construção da árvore AVL a partir da lista ordenada também leva O(m+n).
Portanto, toda a operação respeita a complexidade de tempo O(m+n) conforme solicitado.

Resposta

Seguinte, para unir as duas árvores AVL T1 e T2 com m e n nós respectivamente em tempo O(m+n), seguimos estes passos:
  1. Realizamos um percurso em ordem em T1 e T2 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 O(m+n).

Exercícios relacionados