El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Arbres AVL

Següent ►
►

Introducció als Arbres AVL

Els arbres AVL són un tipus especial d'arbre binari de cerca (BST) que es mantenen equilibrats automàticament. El nom AVL prové dels seus inventors, Adelson-Velsky i Landis, que els van introduir el 1962. La característica clau dels arbres AVL és que per a qualsevol node de l'arbre, la diferència de profunditat entre els seus subarbres esquerre i dret (anomenada factor d'equilibri) és com a màxim 1. Això garanteix que les operacions de cerca, inserció i eliminació es puguin realitzar en temps logarítmic.

Característiques dels Arbres AVL

  1. Equilibri: La diferència de profunditat entre els subarbres esquerre i dret de qualsevol node és com a màxim 1.
  2. Temps d'operació: Les operacions de cerca, inserció i eliminació es realitzen en O(log n) en el pitjor dels casos.
  3. Rotacions: Per mantenir l'equilibri, els arbres AVL utilitzen rotacions simples i dobles.

Rotacions en Arbres AVL

Quan es realitza una inserció o eliminació que desequilibra l'arbre, es necessiten rotacions per restaurar l'equilibri. Hi ha quatre tipus de rotacions:

  1. Rotació Simple a l'Esquerra (LL): Quan un node es desequilibra a l'esquerra a causa d'una inserció en el subarbre esquerre del seu fill esquerre.
  2. Rotació Simple a la Dreta (RR): Quan un node es desequilibra a la dreta a causa d'una inserció en el subarbre dret del seu fill dret.
  3. Rotació Doble a l'Esquerra-Dreta (LR): Quan un node es desequilibra a l'esquerra a causa d'una inserció en el subarbre dret del seu fill esquerre.
  4. Rotació Doble a la Dreta-Esquerra (RL): Quan un node es desequilibra a la dreta a causa d'una inserció en el subarbre esquerre del seu fill dret.

Exemple de Rotació Simple a la Dreta (RR)

Considerem un arbre AVL desequilibrat després d'una inserció:

    3
     \
      4
       \
        5

Després d'una rotació simple a la dreta, l'arbre es converteix en:

    4
   / \
  3   5

Exemple de Rotació Doble a l'Esquerra-Dreta (LR)

Considerem un arbre AVL desequilibrat després d'una inserció:

    3
   /
  1
   \
    2

Després d'una rotació doble a l'esquerra-dreta, l'arbre es converteix en:

    2
   / \
  1   3

Implementació d'un Arbre AVL en Python

A continuació es mostra una implementació bàsica d'un arbre AVL en Python:

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 < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        balance = self.get_balance(root)

        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)

        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)

        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def left_rotate(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

    def right_rotate(self, z):
        y = z.left
        T3 = y.right

        y.right = z
        z.left = T3

        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

    def get_height(self, root):
        if not root:
            return 0
        return root.height

    def get_balance(self, root):
        if not root:
            return 0
        return self.get_height(root.left) - self.get_height(root.right)

    def pre_order(self, root):
        if not root:
            return
        print("{0} ".format(root.key), end="")
        self.pre_order(root.left)
        self.pre_order(root.right)

# Exemple d'ús
avl = AVLTree()
root = None

keys = [10, 20, 30, 40, 50, 25]

for key in keys:
    root = avl.insert(root, key)

print("Preordre de l'arbre AVL:")
avl.pre_order(root)

Explicació del Codi

  1. Node: La classe Node defineix un node de l'arbre AVL amb una clau, referències als fills esquerre i dret, i la seva alçada.
  2. AVLTree: La classe AVLTree conté mètodes per inserir nodes, realitzar rotacions, obtenir l'alçada i el factor d'equilibri dels nodes, i imprimir l'arbre en preordre.
  3. Inserció: El mètode insert insereix un nou node a l'arbre i ajusta les alçades i els equilibris mitjançant rotacions si és necessari.
  4. Rotacions: Els mètodes left_rotate i right_rotate realitzen les rotacions necessàries per mantenir l'arbre equilibrat.
  5. Preordre: El mètode pre_order imprimeix l'arbre en preordre per verificar la seva estructura.

Exercici Pràctic

Exercici

Implementa una funció per eliminar un node d'un arbre AVL i mantenir l'equilibri de l'arbre.

Solució

class AVLTree:
    # ... (altres mètodes)

    def delete(self, root, key):
        if not root:
            return root

        if key < root.key:
            root.left = self.delete(root.left, key)
        elif key > 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.get_min_value_node(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.get_height(root.left), self.get_height(root.right))

        balance = self.get_balance(root)

        if balance > 1 and self.get_balance(root.left) >= 0:
            return self.right_rotate(root)

        if balance > 1 and self.get_balance(root.left) < 0:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        if balance < -1 and self.get_balance(root.right) <= 0:
            return self.left_rotate(root)

        if balance < -1 and self.get_balance(root.right) > 0:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def get_min_value_node(self, root):
        if root is None or root.left is None:
            return root
        return self.get_min_value_node(root.left)

# Exemple d'ús
avl = AVLTree()
root = None

keys = [10, 20, 30, 40, 50, 25]

for key in keys:
    root = avl.insert(root, key)

print("Preordre de l'arbre AVL abans de l'eliminació:")
avl.pre_order(root)

root = avl.delete(root, 40)

print("\nPreordre de l'arbre AVL després de l'eliminació:")
avl.pre_order(root)

Explicació del Codi

  1. Eliminació: El mètode delete elimina un node de l'arbre AVL i ajusta les alçades i els equilibris mitjançant rotacions si és necessari.
  2. Node amb Valor Mínim: El mètode get_min_value_node troba el node amb el valor mínim en un subarbre, utilitzat per substituir el node eliminat.

Conclusió

Els arbres AVL són una estructura de dades poderosa que garanteix operacions eficients en temps logarítmic mantenint l'equilibri de l'arbre. Comprendre les rotacions i la implementació d'arbres AVL és essencial per a qualsevol programador que treballi amb estructures de dades avançades.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats