Arboles AVL

Arboles AVL

Los árboles AVL son una estructura de datos de árbol binario de búsqueda que se caracteriza por estar equilibrada, es decir, la altura de sus dos subárboles hijos difiere en no más de 1. Esto se consigue manteniendo una condición específica de equilibrio durante la inserción y eliminación de nodos, lo que garantiza una complejidad de tiempo de búsqueda, inserción y eliminación de O(log n) en el peor de los casos.


Los árboles AVL se denominan así por los apellidos de los inventores: Adelson-Velskii y Landis. Fueron propuestos por primera vez en 1962 por G.M. Adelson-Velskii y E.M. Landis como una forma de acelerar las operaciones de búsqueda en un árbol binario de búsqueda.


En donde podemos ver el uso de los arboles AVL?

Los árboles AVL son una estructura de datos muy útil en informática y se utilizan en muchas aplicaciones en la vida real. Aquí hay algunos ejemplos:


Bases de datos: los árboles AVL se utilizan para indexar y buscar información en bases de datos. Debido a su naturaleza equilibrada, los árboles AVL permiten realizar búsquedas eficientes y rápidas, lo que los convierte en una opción popular para bases de datos grandes y complejas.


Redes de telecomunicaciones: los árboles AVL se utilizan para enrutar las llamadas telefónicas y los mensajes de texto a través de las redes de telecomunicaciones. Los árboles AVL se utilizan para mantener un registro de las rutas más eficientes entre los dispositivos de red, lo que ayuda a reducir la congestión de la red y mejorar el rendimiento.


Sistemas operativos: los árboles AVL se utilizan para administrar la memoria en los sistemas operativos. Los árboles AVL se utilizan para almacenar y recuperar rápidamente datos en la memoria, lo que ayuda a mejorar el rendimiento general del sistema operativo.


Compiladores: los árboles AVL se utilizan en la construcción de compiladores de lenguaje de programación. Los árboles AVL se utilizan para almacenar y organizar la información de la sintaxis del programa, lo que ayuda al compilador a generar código ejecutable más rápido y eficiente.


Sistemas de archivos: los árboles AVL se utilizan para administrar los archivos y directorios en los sistemas de archivos. Los árboles AVL se utilizan para organizar y buscar archivos y directorios de manera eficiente, lo que ayuda a mejorar el rendimiento del sistema de archivos en general.


En resumen, los árboles AVL son una estructura de datos importante en la informática y se utilizan en una variedad de aplicaciones en la vida real. Su equilibrio y eficiencia los hacen ideales para procesar grandes cantidades de datos y mejorar el rendimiento de los sistemas informáticos.


Sus caracteristicas

Los árboles AVL son similares a los árboles de búsqueda binarios normales, excepto por el hecho de que se mantienen equilibrados automáticamente mediante una serie de rotaciones. Estas rotaciones mantienen la altura del árbol en equilibrio, lo que a su vez mantiene la complejidad de las operaciones de búsqueda, inserción y eliminación en su nivel óptimo.


Para mantener el equilibrio en el árbol AVL, se debe garantizar que la diferencia de altura entre los subárboles izquierdo y derecho de cualquier nodo no sea mayor que 1. Si esta diferencia es mayor que 1, entonces el árbol no está balanceado y se deben aplicar rotaciones en el árbol para equilibrarlo.


Existen dos tipos de rotaciones que se utilizan en un árbol AVL: rotación izquierda y rotación derecha. Estas rotaciones se aplican en función del factor de balance de los nodos del árbol.


Cuando se inserta o elimina un nodo de un árbol AVL, se debe actualizar el factor de balance de todos los nodos afectados y se deben aplicar rotaciones si el árbol está desequilibrado. De esta forma, se mantiene la propiedad de balance del árbol AVL y se asegura que la altura del árbol no crezca demasiado, lo que permite realizar búsquedas, inserciones y eliminaciones en tiempo logarítmico.


Característica básica de un árbol AVL (AVL Equilibrio/ Balance):

Para todos cada uno de los Nodos v, la diferencia entre la altura de su subarbol a su izquierda y la altura en su subarbol en la derecha debe ser menor o igual a 1


En otras palabras, el factor de balance (balance factor) de un nodo en un árbol AVL se define como la diferencia entre la altura del subárbol derecho y la altura del subárbol izquierdo. Si el factor de balance es 0, el árbol está perfectamente equilibrado, si es negativo, el subárbol izquierdo es más alto y si es positivo, el subárbol derecho es más alto.


La altura de un árbol de búsqueda determina la complejidad de búsqueda en el hablando de tiempo de ejecución.


Los árboles AVL nos ofrecen un tiempo de ejecución constante para la búsqueda de un elemento en el mejor de los casos y logarítmica en el peor de los casos, en el caso promedio o en caso de una búsqueda sin éxito:


Lo interesante es que si observamos el tiempo de ejecución para las operaciones de Insertar y Eliminar, el cual es mayor comparado con el valor de este para la operación de búsqueda, veremos que este tiempo de ejecución se reduce hasta ser igual al mismo valor que en búsqueda, cuando logramos que la característica de balanceo propia de los árboles AVL, se restaure usando tiempo constante.


Idea de conservación de la característica AVL en arboles:


  • Guardar la altura de cada uno de los subárboles en sus nodos.

  • Actualización de cada altura de cada subárbol después de implementar operaciones de insertar o eliminar.

  • Comprobación de la característica AVL en todos y cada uno de los nodos a lo largo de una ruta afectada al aplicar operaciones de insertar o eliminar, hasta llegar a la raíz del árbol (nodo más alto).

  • Restauración de la característica AVL por medio de rotaciones

Rotaciones

Los diferentes tipos de rotaciones que se pueden realizar en un árbol AVL son los siguientes:


Cuando el subárbol a la izquierda es muy alto, rotación a la Derecha:


  • Rotación simple, cuando allí, el subárbol izquierdo (externo) es muy alto

  • Rotación doble, cuando allí, el subárbol derecho (interno) es muy alto

Cuando el subárbol a la derecha es muy alto, rotación a la izquierda:


  • Rotación simple, cuando allí, el subárbol derecho (externo) es muy alto

  • Rotación doble, cuando allí, el subárbol izquierdo (interno) es muy alto

Ejemplo:

Supongamos que tenemos el siguiente árbol, insertaremos el valor 25, lo que nos obligara a reestablecer la característica AVL con una rotación simple a la izquierda sobre el nodo 15. A continuación insertaremos el valor 30, lo que nos obligara a hacer la misma rotación esta vez sobre el nodo 20


El árbol AVL resultante lo tenemos en la parte de abajo. En la siguiente tabla vemos las características del primer árbol al insertar el valor 25.


Nodo n Altura h(n) Factor de balance b(n) ¿Balanceado? 
10 h(10) = 3 h(8) - h(15) = -2 NO
8 h(8) = 0 h()-h()= (-1)–(-1)= 0 si
15 h(15) = 2 h(12)-h(20) = -1 si
12 h(12) = 0 h()-h()= (-1)–(-1)= 0 si
20 h(20) = 1 h()-h(25) = -1-0 = -1 si
25 h(25) = 0 h() - h() = 0 si

Implementación de un árbol

A continuación veremos una implementación de un Arbol AVL en C++


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>

using namespace std;
typedef int object;
class avlElem { 
    public: 
        int height; object val;
        avlElem *left, *right; 
};        
class avlTree {
    private: 
        avlElem *root;
        int max(int a,int b);
        int getHeight(avlElem *elem);
        void updateHeight(avlElem *elem);
        void insert(avlElem * &elem,object o);
        void deleteTree(avlElem *root);
        void checkRotationRight(avlElem* &elem);
        void checkRotationLeft(avlElem* &elem);
        void print(avlElem *curr, int depth);
        void rotateLeft(avlElem* &a);
        void doubleRotationLeft(avlElem* &a);
        void rotateRight(avlElem* &a);
        void doubleRotationRight(avlElem* &a);
        void remove(avlElem* &elem, object o);
    public: 
        avlTree(); 
        ~avlTree();
        void insert(object o);       
        void print_out();
        void remove_out(object o);
};

Te invito ver la implementación entera en el libro "El Manual de los algoritmos y las estructuras de datos"


El Manual de los algoritmos y las estructuras de datos.

Este capítulo ha sido solo uno de 9 capítulos en total del libro.


Descarga el manual directamente desde este enlace:

https://leanpub.com/elmanualdelosalgoritmosylasestructurasdedatos


¿Te ha gustado?, quisieras acceder a más contenido?

Dejame saber tu opinion en los comentarios!


Sanchez

Profesional en informatica medica con enfasis en algoritmos y analizis de imagen en C++. Programador con experiencia en C/C++ y Python.

Reactions

4

2

0

0

Access hereTo be able to comment

TheWhiteCode.com is not the creator or owner of the images shown, references are: