bachiller

Árbol AVL

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Este aviso fue puesto el 24 de noviembre de 2013.
Puedes añadirlas o avisar al autor principal del artículo en su página de discusión pegando: {{subst:Aviso referencias|Árbol AVL}} ~~~~


Esteartículo o sección necesita una revisión de ortografía y gramática.
Puedes colaborar editándolo (lee aquí sugerencias para mejorar tu ortografía). Cuando esté corregido, borra este aviso, por favor.
Puedes ayudarte del corrector ortográfico, activándolo en: Mis preferencias → Accesorios → Navegación →  El corrector ortográfico resalta errores ortográficos con un fondo rojo.
Un árbol AVL es un tipoespecial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.
Índice
  [ocultar] 
1 árbol de navidad en java
2 Descripción
3 Definición formal
3.1 Definición de la altura de un árbol
3.2 Definición de árbol AVL
4 Factor de equilibrio
5 Operaciones
5.1 Rotaciones
5.2 Inserción
5.3 Extracción5.4 Búsqueda
6 Véase también
7 Enlaces externos
árbol de navidad en java[editar]
import javax.swing.JOptionPane;
public class ArbolNavidad {
/**
* @param args
*/
public static void main(String[] args) {
int pisos=Integer.parseInt(JOptionPane.showInputDialog("Dame un número de pisos: "));
pisos=pisos*2-1;

for(int i=0; i el nodo está equilibradoy su subárbol izquierdo es un nivel más alto.
Si el factor de equilibrio  es necesario reequilibrar.
Operaciones[editar]
Las operaciones básicas de un árbol AVL implican generalmente el realizar los mismos algoritmos que serían realizados en un árbol binario de búsqueda desequilibrado, pero precedido o seguido por una o más de las llamadas "rotaciones AVL".
Rotaciones[editar]


Lasrotaciones internas en árboles binarios son operaciones internas comunes utilizadas para mantener el balance perfecto (o casi perfecto del árbol binario. Un árbol balanceado permite operaciones en tiempo logarítmico
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 casospueden ser hacia la derecha o hacia la izquierda.
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 dei (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).

op rotDer: AVL{X} -> [AVL{X}] .
eq rotDer(arbolBin(R1, arbolBin(R2, I2, D2), D1)) ==
arbolBin(R2, I2, arbolBin(R1, D2, D)) .
Rotación 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 derechocolocamos 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’) y el hijo izquierdo será el hijo izquierdo del árbol (i).
Precondición : Tiene que tener hijo derecho no vacío.

op rotIzq: AVL{X} -> [AVL{X}] .
eq rotIzq(arbolBin(R1, I, arbolBin(R2, I2, D2))) ==
arbolBin(R2,arbolBin(R1, I, I2), D2) .
Si la inserción se produce en el hijo derecho del hijo izquierdo del nodo desequilibrado (o viceversa) hay que realizar una doble rotación.
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 doble a la izquierda
La Rotación doble a la Izquierda son...