Google+ Seguidores

martes, 14 de agosto de 2018

Implementación de un Árbol AVL - Estructuras de Datos con Python

Introducción:

Hola amigos de Internet, les doy la bienvenida a Mi Diario Python, el mejor blog para Aprender Python.

En este articulo, nos enfocaremos en conocer los principios básicos de los árboles AVL, un tipo especial de árbol binario. Al final, realizaremos una implementación utilizando el lenguaje de programación Python.

¿Que es un árbol AVL?

Los árboles AVL son un tipo especial de árbol binario. Inventado por los matemáticos rusos Adelson-Velskii y Landis, de allí el nombre AVL. 

El árbol AVL tiene la peculiaridad de ser el primer árbol binario auto-balanceable. 

Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa.

La siguiente imagen es una representación de su equilibrio:

Imagen relacionada

Para conseguir esta propiedad de equilibrio, la inserción y borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado de rompe la condición de equilibrio, hay que realizar una serie de rotaciones de nodos.

Representación de una construcción de un árbol AVL y sus rotaciones


Operaciones:

Otro punto a tener en cuenta son las operaciones que se pueden realizar en un árbol AVL. Esto nos servira para saber que métodos agregar al momento de la implementación.

Rotaciones:

El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.

Podemos realizar 4 tipos de rotaciones:

Rotación simple a la derecha:

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).

rotación simple a la derecha inicio


Rotación simple a la izquierda:

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) de r y el hijo izquierdo será el hijo izquierdo del árbol (i).


Precondición : Tiene que tener hijo derecho no vacío.

Rotación doble a la derecha:


La Rotación doble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación simple derecha.

rotación a la izquierda inicio
rotación a la izquierda final


Rotación doble a la izquierda

La Rotación doble a la Izquierda son dos rotaciones simples, primero rotación simple derecha y luego rotación simple izquierda.

rotación a la izquierda iniciorotación a la izquierda final


Inserción:

La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibrado y después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción.

Proceso de inserción:

  1. Buscar hasta encontrar la posición de inserción o modificación (proceso idéntico a inserción en árbol binario de búsqueda).
  2. Insertar el nuevo nodo con factor de equilibrio “equilibrado”.
  3. Desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario.
Insercion1.jpg Insercion2.jpg Insercion3-1.jpg Insercion3-2.jpg Insercion4-1.jpg Insercion4-2.jpg

Referencias: 


Implementación:

Ahora sí es el momento de escribir código. 

"""
Árbol AVL - Implementación en Python
"""

from __future__ import print_function

"""
Declaramos la clase "Node", con cada una de sus propiedades.
"""
class Node:
    def __init__(self, label):
        self.label = label
        self._parent = None
        self._left = None
        self._right = None
        self.height = 0

    @property
    def right(self):
        return self._right

    @right.setter
    def right(self, node):
        if node is not None:
            node._parent = self
            self._right = node

    @property
    def left(self):
        return self._left

    @left.setter
    def left(self, node):
        if node is not None:
            node._parent = self
            self._left = node

    @property
    def parent(self):
        return self._parent

    @parent.setter
    def parent(self, node):
        if node is not None:
            self._parent = node
            self.height = self.parent.height + 1
        else:
            self.height = 0

# Declaramos la clase AVL
class AVL:

    def __init__(self):
        self.root = None
        self.size = 0

        """
        Operación de inserción para agregar nuevos nodos
        al árbol.
        """
    def insert(self, value):
        node = Node(value)

        if self.root is None:
            self.root = node
            self.root.height = 0
            self.size = 1
        else:
            dad_node = None
            curr_node = self.root

            while True:
                if curr_node is not None:

                    dad_node = curr_node

                    if node.label < curr_node.label:
                        curr_node = curr_node.left
                    else:
                        curr_node = curr_node.right
                else:
                    node.height = dad_node.height
                    dad_node.height += 1
                    if node.label < dad_node.label:
                        dad_node.left = node
                    else:
                        dad_node.right = node
                    self.rebalance(node)
                    self.size += 1
                    break

        # Operación de rotación
    def rebalance(self, node):
        n = node

        while n is not None:
            height_right = n.height
            height_left = n.height

            if n.right is not None:
                height_right = n.right.height

            if n.left is not None:
                height_left = n.left.height

            if abs(height_left - height_right) > 1:
                if height_left > height_right:
                    left_child = n.left
                    if left_child is not None:
                        h_right = (left_child.right.height
                                    if (left_child.right is not None) else 0)
                        h_left = (left_child.left.height
                                    if (left_child.left is not None) else 0)
                    if (h_left > h_right):
                        self.rotate_left(n)
                        break
                    else:
                        self.double_rotate_right(n)
                        break
                else:
                    right_child = n.right
                    if right_child is not None:
                        h_right = (right_child.right.height
                            if (right_child.right is not None) else 0)
                        h_left = (right_child.left.height
                            if (right_child.left is not None) else 0)
                    if (h_left > h_right):
                        self.double_rotate_left(n)
                        break
                    else:
                        self.rotate_right(n)
                        break
            n = n.parent

    def rotate_left(self, node):
        aux = node.parent.label
        node.parent.label = node.label
        node.parent.right = Node(aux)
        node.parent.right.height = node.parent.height + 1
        node.parent.left = node.right


    def rotate_right(self, node):
        aux = node.parent.label
        node.parent.label = node.label
        node.parent.left = Node(aux)
        node.parent.left.height = node.parent.height + 1
        node.parent.right = node.right

    def double_rotate_left(self, node):
        self.rotate_right(node.getRight().getRight())
        self.rotate_left(node)

    def double_rotate_right(self, node):
        self.rotate_left(node.getLeft().getLeft())
        self.rotate_right(node)

    def empty(self):
        if self.root is None:
            return True
        return False

    def preShow(self, curr_node):
        if curr_node is not None:
            self.preShow(curr_node.left)
            print(curr_node.label, end=" ")
            self.preShow(curr_node.right)

    def preorder(self, curr_node):
        if curr_node is not None:
            self.preShow(curr_node.left)
            self.preShow(curr_node.right)
            print(curr_node.label, end=" ")

    def getRoot(self):
        return self.root

if __name__ == '__main__':
    t = AVL()
    t.insert(5)
    t.insert(9)
    t.insert(13)
    t.insert(10)
    t.insert(17)
    t.preShow(t.root)

5 9 10 13 17 

El método preShow nos mostrara nos nodos del árbol. Todo de manera equilibrada.

¿Alguna duda? No dudes en dejar tu comentario.

Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.

1 comentario :
Write comentarios
  1. Se podrá aplicar éste programa para gramática para el esquema arbóreo.

    ResponderEliminar

Tu comentario es importante y nos motiva a seguir escribiendo...

Powered by Blogger .