01 - Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos. Uma árvore binária de busca é uma árvore binária onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raíz. Para construirmos uma árvore balanceada ou AVL primeiramente precisamos utilizar o conceito de ABB. Portanto explique o conceito de árvore balanceada ou AVL?
R: A árvore AVL é balanceada quando a diferença da sub-árvores (direita e esquerda) for = < 1, e se seus filhos e netos tiverem diferenças maiores que 1 essa arvore não esta balanceada.
R: A árvore AVL é balanceada quando a diferença da sub-árvores (direita e esquerda) for = < 1, e se seus filhos e netos tiverem diferenças maiores que 1 essa arvore não esta balanceada.
2 - Sabendo que podemos inserir elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de inserção na árvore AVL e do seu algoritmo.
R: Seja c uma nova chave a inserir numa árvore AVL A. Primeiro, c é inserido como folha de A, seguindo o algoritmo do caso geral das ABBs. Se depois da inserção a árvore permanece AVL, então nada mais temos a fazer. Caso contrário, é necessário remanejar a árvore.
3 - Sabendo-se que os conceitos de rotação simples a direita/esquerda e de rotação dupla a direita/esquerda são essenciais na inserção de elementos na árvore avl. Explique os conceitos de rotação simples e rotação dupla.
R: Rotação simples é utilizada quando a apenas filhos alinhados Ex: 3 > 7 > 9 o valor 9 é a raiz principal, o 7 é filho do 9 e pai do 3, agora vamos balanceá-la, o 7 se torna a raiz principal, o 3 é filho esquerdo de 7 e o 9 é filho direito de 7.
4 - Sabendo que podemos retirar elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de remoção na árvore AVL e do seu algoritmo.
R: A remoção deve ser feita por uma rotação em torno do nó a ser removido e torná-lo folha para que então possa ser retirado. Em alguns casos, após ser retirado são necessárias rotações para ajustar o fator de balanceamento.
5 - Através dos conceitos discutidos, dê dois exemplos de inserção em árvores AVL e dois exemplos de remoção em árvores AVL.
R:
Nenhum comentário:
Postar um comentário