arboles avl con codigo en java

El contenido de esta exposicion es de mi autoría, y/o, es un recopilación de distintas fuentes.

1. Árbol AVL Diego Márquez De La Hoz Ingeniería de Sistemas

2. Descripción " Un algoritmo para la organización de la información “.( Adelson-Velskii y Landis) Están siempre equilibrados. Es decir, 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 complejidad de una búsqueda se mantiene siempre en orden de complejidad O(log n). Para conseguir la propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si no se preserva esta propiedad, hay que realizar una serie de rotaciones de los nodos.

3. Factor de equilibrio Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los árboles binarios de búsqueda (ABB), y además el dato que controla el factor de equilibrio. El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo: FE = altura subárbol derecho - altura subárbol izquierdo

4. Operaciones

5. Rotación simple a la derecha De un árbol de raíz (r) y de hijos izq. (i) y der.(d), se formara un nuevo árbol cuya raíz sea la raíz del hijo izq., como hijo izq. colocamos el hijo izq. de i (i’) y como hijo der. construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo der. de i (d’) será el hijo izq. y el hijo der. será el hijo derecho del árbol (d).

6. Rotación simple a la izquierda De un árbol de raíz (r) y de hijos izq. (i) y der. (d), se formara un nuevo árbol cuya raíz sea la raíz del hijo der., como hijo der. colocamos el hijo der. de d (d ’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izq. de d será el hijo derecho (i’) y el hijo izq. será el hijo izq. del árbol (i).

7. Inserción 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 2. insertar el nuevo nodo con factor de equilibrio 3. repasar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario

8. Extracción Una extracción trae consigo una disminución de la altura de la rama donde se extrajo y tendrá como efecto un cambio en el factor de equilibrio del nodo padre de la rama en cuestión, pudiendo necesitarse una rotación .

9. Borrar A, y la nueva raíz será M . Borrado A, la nueva raíz es M. Aplicamos la rotación a la derecha. El árbol resultante ha perdido altura .

10. Código en java

11. Class AvlNode /** * * @ author Diego */ public class AVLNode { public Comparable dato; // el dato del nodo public AVLNode izquierdo; // hijo izquierdo public AVLNode derecho; // hijo derecho public int height ; // altura // Constructors public AVLNode (Comparable dato) { this (dato, null , null ); } public AVLNode (Comparable dato , AVLNode izq , AVLNode der) { this.dato = dato; this.izquierdo = izq ; this.derecho = der; height = 0; // altura predeterminada } }

12. Class AvlTree public class AVLTree { private AVLNode root ; public void insert (Comparable x) { root = insertar(x, root ); } /* * x es una instancia de una clase que implementa Comparable */ private AVLNode insertar(Comparable x, AVLNode t) { if (t == null ) { t = new AVLNode (x, null , null ); } else if ( x.compareTo ( t.dato ) < 0) { t.izquierdo = insertar(x, t.izquierdo ); if ( height ( t.izquierdo ) - height ( t.derecho ) == 2) { if ( x.compareTo ( t.izquierdo.dato ) < 0) { t = rotacionHijoIzquierdo (t); /* Caso 1 */ } else { t = rotacionDobleHijoIzquierda (t); /* Caso 2 */ } } } else if ( x.compareTo ( t.dato ) > 0) { t.derecho = insertar(x, t.derecho ); if ( height ( t.derecho ) - height ( t.izquierdo ) == 2) { if ( x.compareTo ( t.derecho.dato ) > 0) { t = rotacionHijoDerecho (t); /* Caso 4 */ } else { t = rotacionDobleHijoDerecho (t); /* Caso 3 */ } } } else ; // Duplicado; no hago nada t.height = max ( height ( t.izquierdo ), height ( t.derecho )) + 1; return t; } private static int max( int izquierdaHeight , int derechaHeight ) { return izquierdaHeight > derechaHeight ? izquierdaHeight : derechaHeight ; } private static AVLNode rotacionHijoIzquierdo ( AVLNode t) { AVLNode aux2 = t.izquierdo ; t.izquierdo = aux2.derecho; aux2.derecho = t; t.height = max ( height ( t.izquierdo ), height ( t.derecho )) + 1; aux2.height = max ( height (aux2.izquierdo), t.height ) + 1; return aux2; } private static AVLNode rotacionHijoDerecho ( AVLNode t) { AVLNode aux2 = t.derecho ; t.derecho = aux2.izquierdo; aux2.izquierdo = t; t.height = max ( height ( t.izquierdo ), height ( t.derecho )) + 1; aux2.height = max ( height (aux2.derecho), t.height ) + 1; return aux2; }

13. private static AVLNode rotacionDobleHijoIzquierda ( AVLNode aux ) { aux.izquierdo = rotacionHijoDerecho ( aux.izquierdo ); return rotacionHijoIzquierdo ( aux ); } private static AVLNode rotacionDobleHijoDerecho ( AVLNode aux ) { aux.derecho = rotacionHijoIzquierdo ( aux.derecho ); return rotacionHijoDerecho ( aux ); } private static int height( AVLNode t) { return t == null ? -1 : t.height ; } /* * Imprime el arbol con el recorrido InOrden */ public void imprimir() { imprimir( root ); } private void imprimir( AVLNode nodo) { if (nodo != null ) { imprimir( nodo.derecho ); System.out.println ("[" + nodo.dato + "]"); imprimir( nodo.izquierdo ); } } public void imprimirPorAltura () { imprimirPorltura ( root ); } /* * Imprime cada nodo linea por linea . Recorriendo el arbol desde * el Nodo más a la derecha hasta el nodo más a la izquierda, * y dejando una identacion de varios espacios en blanco segun su * altura en el arbol */ private void imprimirPorltura ( AVLNode nodo) { if (nodo != null ) { imprimirPorltura ( nodo.derecho ); System.out.println ( replicate (" ", height ( root ) - height (nodo)) + "[" + nodo.dato + "]"); imprimirPorltura ( nodo.izquierdo ); } }

14. /* * Metodo estatico auxiliar que dada una cadena a y un enterto cnt * replica o concatena esa cadena a, cnt veces */ private static String replicate ( String a, int cnt ) { String x = new String (""); for (int i = 0; i < cnt; i++) { x = x + a; } return x; } /* * Obtiene la altura del arbol AVL */ public int calcularAltura () { return calcularAltura ( root ); } private int calcularAltura ( AVLNode actual) { if (actual == null ) { return -1; } else { return 1 + Math.max ( calcularAltura ( actual.izquierdo ), calcularAltura ( actual.derecho )); } } // Imprime el arbol por niveles. Comienza por la raiz . public void imprimirPorNiveles () { imprimirPorNiveles ( root ); } // Imprime el arbol por niveles. private void imprimirPorNiveles ( AVLNode nodo) { // Mediante la altura calcula el total de nodos posibles del árbol // Y crea una array cola con ese tamaño int max = 0; int nivel = calcularAltura (); for (; nivel >= 0; nivel--) { max += Math.pow (2, nivel); } max ++; // Suma 1 para no utilizar la posicion 0 del array AVLNode cola[] = new AVLNode [ max ]; // Carga en la pos 1 el nodo raiz cola[1] = nodo; int x = 1;

15. // Carga los demas elementos del arbol , // Carga null en izq y der si el nodo es null // i aumenta de a 2 por q carga en izq y der los hijos // x aumenta 1, que son los nodos raiz - padre for (int i = 2; i < max; i += 2, x++) { if (cola[x] == null ) { cola[i] = null ; cola[i + 1] = null ; } else { cola[i] = cola[x].izquierdo; cola[i + 1] = cola[x].derecho; } } nivel = 0; int cont = 0; // contador para cada nivel int cantidad = 1; // cantidad de nodos por nivel int ultimaPosicion = 1; // ultimaPosicion del nodo en la cola de cada nivel // Cuando i es = a 2^nivel hay cambio de nivel // 2 ^ 0 = 1 que es el nodo raiz for (int i = 1; i < max; i++) { if (i == Math.pow (2, nivel)) { // Nodo raiz tiene nivel 1, por eso (nivel + 1) System.out.print ("\n Nivel " + (nivel) + ": "); nivel++; } if (cola[i] != null ) { System.out.print ("[" + cola[i].dato + "]"); cont ++; } if ( ultimaPosicion == i && cantidad == Math.pow (2, --nivel)) { if (cantidad == 1) { System.out.print (" Cantidad de nodos: " + cont + " ( raiz )"); } else { System.out.print (" Cantidad de nodos: " + cont ); } cont = 0; cantidad *= 2; ultimaPosicion += ( int ) Math.pow (2, ++nivel); } } } }

16. Class EjecutableAvlTree /** * * @ author Diego */ public class EjecutableAVLTree { /** * @ param args the command line arguments */ public static void main(String[] args ) { // TODO code application logic here AVLTree arbolAVL = new AVLTree (); Integer elemento1 = new Integer ("1"); Integer elemento2 = new Integer ("2"); Integer elemento3 = new Integer ("3"); Integer elemento4 = new Integer ("4"); Integer elemento5 = new Integer ("5"); Integer elemento6 = new Integer ("6"); Integer elemento7 = new Integer ("7"); Integer elemento8 = new Integer ("15"); Integer elemento9 = new Integer ("14"); Integer elemento10 = new Integer ("13"); arbolAVL.insert (elemento1); arbolAVL.insert (elemento2); arbolAVL.insert (elemento3); arbolAVL.insert (elemento4); arbolAVL.insert (elemento5); arbolAVL.insert (elemento6); arbolAVL.insert (elemento7); arbolAVL.insert (elemento8); arbolAVL.insert (elemento9); arbolAVL.insert (elemento10); arbolAVL.imprimirPorNiveles (); int altura = arbolAVL.calcularAltura () + 1; System.out.println ("\n"); System.out.println (altura + " altura del arbol "); System.out.println ("\n"); arbolAVL.imprimirPorAltura (); } }