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:
-
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. -
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.
-
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)
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:
- Realizamos um percurso em ordem em
e para obter duas listas ordenadas. - Intercalamos essas duas listas em uma única lista ordenada.
- 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.
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).