Lista Árvores AVL

Prévia do material em texto

LISTA Árvores AVL
Estruturas de Dados II
Prof. Murilo Ybanez
Implemente as operações de inserção e remoção em uma árvore AVL.
Suponha que T seja uma árvore AVL inicialmente vazia, e considere a inserção dos elementos 10, 20, 30, 5, 15 e 2 em T, nesta ordem. Qual das seqüências abaixo corresponde ao percurso de T em pré-ordem? (POSCOMP)
10, 5, 2, 20, 15, 30
20, 10, 5, 2, 15, 30
2, 5, 10, 15, 20, 30
30, 20, 15, 10, 5, 2
15, 10, 5, 2, 20, 30
Árvores binárias podem ser usadas para guardar e recuperar informações com número de operações proporcional à altura da árvore. Quais das seguintes figuras representam árvores binárias de altura balanceada ou do tipo AVL (Adelson-Velski e Landis): (POSCOMP)
Somente (I) e (IV) são árvores binárias AVL.
Somente (I) é árvore binária AVL.
Somente (I), (II) e (III) são árvores binárias AVL.
Somente (II) e (III) são árvores binárias AVL.
Todas (I), (II), (III) e (IV) são árvores binárias AVL.
Desenhe as seguintes árvores respeitando a seqüência apresentada. Indique em cada nó qual a diferença entre as alturas das sub-árvores. Diga quais delas são árvores AVL.
10, 3, 30, 7, 9, 50, 1, 60
50, 30, 20, 80, 40, 60, 90, 200, 85, 45, 70, 100
30, 20, 50, 60, 10, 5, 15, 40, 70
Elabore um programa que, dada uma árvore binária de busca, imprime o fator de balanceamento de todos os nós.
Elabore um programa que, dada uma árvore binária de busca, retorna se ela é uma árvore AVL.
Partindo de uma árvore AVL vazia, realize a inserção da seguinte seqüência de chaves: 99, 44, 71, 80, 74, 63, 59, 120, 98, 150.
Para a árvore AVL a seguir, realize as inserções das chaves 49, 60, 65 e, em seguida, a remoção das chaves 45 e 41. Mostre todas as rotações e o formato da árvore após cada operação.
�
Seja uma árvore AVL T. Considere a inserção de um nó q em T, que tornou T desregulada. Seja p o nó desregulado mais próximo das folhas.
Qual o valor exato de |alt(esq(p)) - alt(dir(p))|? Por que não pode ser nem mais nem menos?
Supondo alt(dir(p)) > alt(esq(p)) então existe um filho direito u de p. Por que necessariamente temos | alt(dir(u)) - alt(esq(u))| = 1? Por que não pode ser 2? Por que não pode ser 0?
De acordo com o item b, quando alt(dir(p)) > alt(esq(p)) existem dois sub-casos a serem considerados: alt(dir(p)) = alt(esq(p)) + 1 ou alt(esq(p)) = alt(dir(p)) + 1. Para cada um dos sub-casos, apresente a transformação que regula p (diga qual e apresente um esquema).
Por que a regulagem de p (nó desregulado mais próximo das folhas) regula toda a árvore ?
 Sobre operações em árvores binárias de busca, responda:
A operação de remoção em uma árvore binária de busca é comutativa? Justifique sua resposta.
A operação de remoção em uma árvore AVL é comutativa? Justifique sua resposta.
Obs: A operação de comutação garantiria que remover x e depois y ou remover y e depois x geraria a mesma árvore.
 Suponha que seja inserido um valor x em uma árvore AVL e logo em seguida removido. A árvore resultante é igual à inicial? Justifique sua resposta.
LISTA Árvores AVL
Respostas
Questão 9
a) 2. Como p é o primeiro nó no caminho de volta para a raiz que ficou desbalanceado, o fator de balanceamento antes da inserção era -1, e a inserção ocorreu na sua sub-árvore à esquerda de p, ou +1, e a inserção ocorreu na sub-árvore à direita de p. Nos dois casos, o módulo do fator de balanceamento será 2.
b) Como p ficou desbalanceado, e a questão assume que a árvore ficou maior para o lado direito, isto significa que o nó q foi inserido na sub-árvore à direita de p, cuja raiz é u. E para que tenha havido o desbalanceamento, a altura desta sub-árvore tem de ter aumentado, o que só ocorre se o fator de balanceamento de u antes era 0 e se tornou 1 ou -1.
c) A figura 1 ilustra o primeiro caso, e a figura 2, o segundo. 
d) A regulagem de p, seja usando rotação simples ou dupla, diminui em 1 a altura da sub-árvore com raiz em p, que volta então a ter a mesma altura que possuía antes da inserção de q. E como a árvore já era AVL, a nova árvore volta a ser balanceada.
Questão 10.
a) Sim. Como a operação de remoção preserva as relações de descendência dentro da árvore (perceba que a remoção de uma chave localizada em um nó com dois filhos deve ser encarada como a remoção nó que contém o sucessor), e já que as árvores resultantes das seqüência de remoção x, y e y, x contém as mesmas chaves, tais árvores são equivalentes. (Obs: esta argumentação apresenta os princípios que fazem com que a assertiva seja verdadeira, mas não vale como uma prova formal. Porque?)
b) Não. Basta considerar o resultado das seqüências de remoção 7, 12 e 12, 7 na árvore da figura 1, assumindo a substituição pelo sucessor.
Questão 11.
Não. Basta considerar o resultado das inserção e remoção da chave 12 na árvore da figura 1.
30
41
56
45
15
25
35
43
50
�figura � SEQ "figura" \*Arabic �1�
�figura � SEQ "figura" \*Arabic �2�