REBECA - AEDA

Prévia do material em texto

15
UNOPAR
CIÊNCIAS DA COMPUTAÇÃO
ATIVIDADE PRÁTICA:
Algoritmo e Estrutura de Dados Avançado
Buíque
2024
ATIVIDADE PRÁTICA:
Algoritmo e Estrutura de Dados Avançado
Trabalho textual apresentado como requisito parcial para a obtenção de média semestral.
Orientadora: Prof. Anderson Inacio Salata de Abreu 
Buíque
2024
SUMÁRIO
1	INTRODUÇÃO	3
2	DESENVOLVIMENTO	4
2.1	RESULTADO	8
3	CONCLUSÃO	10
REFERÊNCIAS	11
INTRODUÇÃO
Ao iniciar esta atividade prática, meu objetivo principal era desenvolver uma compreensão aprofundada sobre árvores AVL, focando nas operações de inserção e remoção de elementos e como essas operações afetam o balanceamento da árvore. Árvores AVL são um tipo específico de árvore binária de busca que se auto-balanceia, garantindo que as operações de busca, inserção e remoção sejam realizadas de forma eficiente. A importância desta atividade reside na aplicação prática de conceitos teóricos de estruturas de dados avançadas, permitindo-me visualizar e entender melhor o comportamento dinâmico das árvores AVL. Além disso, a atividade proporciona uma oportunidade de praticar a identificação e aplicação das rotações necessárias para manter o balanceamento da árvore, visualizando o resultado gráfico dessas operações.
As árvores AVL são fundamentais no estudo de estruturas de dados devido à sua capacidade de manter a altura balanceada, o que é crucial para garantir a eficiência das operações. Compreender e aplicar esses conceitos é essencial para qualquer desenvolvedor que deseja criar algoritmos eficientes e escaláveis. Através desta atividade, pude explorar as operações de inserção e remoção em árvores AVL, bem como as rotações simples e duplas necessárias para manter o balanceamento.
DESENVOLVIMENTO
Inserção de Elementos
A primeira parte da atividade envolveu a inserção de uma lista de elementos em uma árvore AVL, um por vez, garantindo que a árvore permanecesse balanceada após cada inserção. A lista de elementos fornecida foi: 20, 4, 26, 3, 9, 15, 30, 2, 7. Para cada inserção, desenhei a árvore resultante e identifiquei as rotações necessárias para manter o balanceamento.
Passos Seguidos:
1. Inserir o elemento 20: Como a árvore estava vazia, 20 se tornou a raiz.
2. Inserir o elemento 4: 4 foi inserido à esquerda de 20, sem necessidade de rotação.
3. Inserir o elemento 26: 26 foi inserido à direita de 20, sem necessidade de rotação.
4. Inserir o elemento 3: 3 foi inserido à esquerda de 4, sem necessidade de rotação.
5. Inserir o elemento 9: 9 foi inserido à direita de 4, sem necessidade de rotação.
6. Inserir o elemento 15: 15 foi inserido à direita de 9, necessitando uma rotação simples à esquerda para balancear a subárvore.
7. Inserir o elemento 30: 30 foi inserido à direita de 26, sem necessidade de rotação.
8. Inserir o elemento 2: 2 foi inserido à esquerda de 3, necessitando uma rotação simples à direita para balancear a subárvore.
9. Inserir o elemento 7: 7 foi inserido à esquerda de 9, necessitando uma rotação dupla à direita para balancear a subárvore.
Remoção de Elementos
A segunda parte da atividade envolveu a remoção de alguns elementos da árvore AVL, ajustando novamente a árvore para garantir o balanceamento. Os elementos a serem removidos foram: 26, 4, 9. Para cada remoção, desenhei a árvore resultante e identifiquei as rotações necessárias para manter o balanceamento.
Passos Seguidos:
1. Remover o elemento 26: Após a remoção, a árvore foi ajustada sem necessidade de rotação.
2. Remover o elemento 4: Após a remoção, a árvore foi ajustada com uma rotação simples à direita para balancear a subárvore.
3. Remover o elemento 9: Após a remoção, a árvore foi ajustada com uma rotação dupla à esquerda para balancear a subárvore.
Altura dos Nós
Após todas as inserções e remoções, calculei a altura de cada nó na árvore resultante. A altura de um nó em uma árvore AVL é definida como a distância máxima da raiz até uma folha, garantindo que a árvore permaneça balanceada.
Implementação do Código
Implementei o algoritmo para inserção e remoção de elementos em uma árvore AVL, seguindo os passos descritos. Aqui está um exemplo de código em Python para ilustrar o processo:
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1
class AVLTree:
    def insert(self, root, key):
        if not root:
            return Node(key)
        elif key 1 and key root.right.key:
            return self.leftRotate(root)
        if balance > 1 and key > root.left.key:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
        if balance root.key:
            root.right = self.delete(root.right, key)
        else:
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp
            temp = self.getMinValueNode(root.right)
            root.key = temp.key
            root.right = self.delete(root.right, temp.key)
        if root is None:
            return root
        root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
        balance = self.getBalance(root)
        if balance > 1 and self.getBalance(root.left) >= 0:
            return self.rightRotate(root)
        if balance > 1 and self.getBalance(root.left) 0:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)
        return root
    def leftRotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        return y
    def rightRotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        return y
    def getHeight(self, root):
        if not root:
            return 0
        return root.height
    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)
    def getMinValueNode(self, root):
        if root is None or root.left is None:
            return root
        return self.getMinValueNode(root.left)
    def preOrder(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.preOrder(root.left)
        self.preOrder(root.right)
# Exemplo de uso
tree = AVLTree()
root = None
elements_to_insert = [20, 4, 26, 3, 9, 15, 30, 2, 7]
for element in elements_to_insert:
    root = tree.insert(root,element)
print("Árvore AVL após inserções:")
tree.preOrder(root)
print()
elements_to_delete = [26, 4, 9]
for element in elements_to_delete:
    root = tree.delete(root, element)
print("Árvore AVL após remoções:")
tree.preOrder(root)
print()
resultado
Ao final da atividade, consegui desenvolver uma árvore AVL funcional que realiza as operações de inserção e remoção de elementos, mantendo a árvore balanceada. Este resultado foi extremamente satisfatório, pois confirmou que os conceitos teóricos que aprendi estavam bem assimilados e que eu era capaz de aplicá-los na prática. Além disso, a experiência de escrever um relatório detalhado sobre a atividade me ajudou a refletir sobre o processo de desenvolvimento, as dificuldades encontradas e as soluções aplicadas.
Durante o processo de inserção, cada elemento foi adicionado à árvore AVL um por vez, e a árvore foi desenhada após cada inserção. Sempre que uma rotação foi necessária para manter o balanceamento, identifiquei e apliquei a rotação correta, seja ela simples à esquerda, simples à direita, dupla à esquerda ou dupla à direita. Isso me permitiu visualizar como as rotações afetam a estrutura da árvore e garantem que ela permaneça balanceada.
Na etapa de remoção, os elementos 26, 4 e 9 foram removidos da árvore, e a árvore foi ajustada após cada remoção para garantir que permanecesse balanceada. Novamente, desenhei a árvore após cada remoção e apliquei as rotações necessárias. Este processo reforçou minha compreensão de como as operações de remoção podem desbalancear a árvore e como as rotações ajudam a restaurar o balanceamento.
Finalmente, calculei a altura de cada nó na árvore resultante após todas as inserções e remoções. A altura de um nó em uma árvore AVL é crucial para garantir que a árvore permaneça balanceada, e este cálculo me ajudou a entender melhor a estrutura da árvore e a importância do balanceamento na eficiência das operações.
Código rodando no VS code:
CONCLUSÃO
Esta atividade prática foi uma excelente oportunidade para aplicar os conceitos de estruturas de dados avançadas em um ambiente de desenvolvimento real. Através desta prática, consegui consolidar meus conhecimentos teóricos sobre árvores AVL e desenvolver habilidades práticas essenciais para a implementação e manutenção dessas estruturas de dados.
As dificuldades encontradas durante o processo, como a identificação e aplicação das rotações corretas para manter o balanceamento da árvore, foram superadas com a aplicação de soluções adequadas e a prática contínua. O resultado foi um algoritmo funcional e eficiente que realiza as operações de inserção e remoção de elementos em uma árvore AVL, mantendo a árvore balanceada.
Além disso, esta experiência destacou a importância de compreender a estrutura e o comportamento das árvores AVL, especialmente em termos de balanceamento e eficiência das operações. A experiência adquirida com esta prática será valiosa para futuros projetos e desafios na área de algoritmos e estruturas de dados avançadas.
REFERÊNCIAS
Colaborar – Cursos. Portal Digital do Aluno. Disponível em: Acesso em: 22 de out. de 2024.
VS Code. Disponível em: .
Acesso em: 22 de out. de 2024.
image9.png
image10.png
image11.png
image12.png
image13.png
image1.png
image2.png
image3.png
image4.png
image5.png
image6.png
image7.png
image8.png