lunes, 12 de noviembre de 2012

Arbol AVL

Descargar Solución de la galería de códigos de msdn aquí

De la wikipedia: http://es.wikipedia.org/wiki/%C3%81rbol_AVL
El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Adelson-Velskii y Landis.  Lo dieron a conocer en la publicación de un artículo en 1962: "An algorithm for the organization of information" ("Un algoritmo para la organización de la información").
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. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.
Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.
Los árboles AVL más profundos son los árboles de Fibonacci.

using System; using System.Collections.Generic; using System.Text;
namespace ProbandoAVL {
   
class AVL<Tkey, Tvalue> where Tkey : IComparable
   
{
       
#region ( Instance of Variables )

       
protected Tkey key;
       
protected Tvalue value;
       
protected int son, height, balanceFactor;
       
protected AVL<Tkey, Tvalue> sonLeft;
       
protected AVL<Tkey, Tvalue> father;
       
protected AVL<Tkey, Tvalue> sonRight;

       
#endregion
       
#region ( Properties )

       
public Tkey Key
       
{
           
get { return this.key; }
           
set { this.key = value; }
       
}
       
public Tvalue Value
       
{
           
get { return this.value; }
           
set { this.value = value; }
       
}
       
public AVL<Tkey, Tvalue> SonLeft
       
{
           
get { return sonLeft; }
       
}
       
public AVL<Tkey, Tvalue> Father
       
{
           
get { return father; }
       
}
       
public AVL<Tkey, Tvalue> SonRight
       
{
           
get { return sonRight; }
       
}

       
#endregion
       
#region ( Builder )

       
public AVL()
       
{
           sonLeft
= null;
           key
= default(Tkey);
           value
= default(Tvalue);
           son
= balanceFactor = 0;
           height
= -1;
           father
= null;
           sonRight
= null;
       
}

       
#endregion
       
#region ( Public Methods )

       
public void Add(Tkey key, Tvalue value)
       
{
           
if (IsEmpty())
           
{
               
RefreshAdd(this, key, value); return;
           
}
           AVL
<Tkey, Tvalue> aux = Search(this, key);
           
if (!aux.IsEmpty()) return;
           
else
           
{
               
RefreshAdd(aux, key, value);
               
if (aux.father != null) BalanceAdd(aux.father); return;
           
}
       
}
       
public void Extract(Tkey key)
       
{
           AVL
<Tkey, Tvalue> aux = Search(this, key);
           
if (aux.Isleaf())
           
{
               
if (aux.father == null)
               
{ aux.Key = default(Tkey); aux.Value = default(Tvalue); return; }
               
if (aux.son == -1)
               
{ aux.father.sonLeft = aux.sonLeft; aux.father.sonLeft.father = aux.father; }
               
else { aux.father.sonRight = aux.sonRight; aux.father.sonRight.father = aux.father; }
               
RefreshExtract(aux.father); return;
           
}
           AVL
<Tkey, Tvalue> aux2 = SearchQuantityOfSon(aux);
           
if (aux2 != null)
           
{
               
if (aux.father == null)
               
{
                   
Swap(aux, aux2);
                   aux
.sonLeft = aux2.sonLeft; aux.sonLeft.father = aux;
                   aux
.sonRight = aux2.sonRight; aux.sonRight.father = aux;
                   
RefreshExtract(aux); return;
               
}
               
if (aux.son == -1) { aux.father.sonLeft = aux2; aux.father.sonLeft.son = -1; }
               
else { aux.father.sonRight = aux2; aux.father.sonRight.son = 1; }
               aux2
.father = aux.father; RefreshExtract(aux.father); return;
           
}
           AVL
<Tkey, Tvalue> aux3 = SearchLessOfBiggest(aux.sonRight);
           
Swap(aux, aux3);
           
if (aux3.Isleaf())
           
{
               
if (aux3.son == -1)
               
{ aux3.father.sonLeft = aux3.sonLeft; aux3.father.sonLeft.father = aux3.father; }
               
else { aux3.father.sonRight = aux3.sonRight; aux3.father.sonRight.father = aux3.father; }
               
RefreshExtract(aux3.father); return;
           
}
           
if (aux3.son == -1)
           
{ aux3.father.sonLeft = aux3.sonRight; aux3.father.sonLeft.son = -1; aux3.sonRight.father = aux3.father; }
           
else
           
{ aux3.father.sonRight = aux3.sonRight; aux3.sonRight.father = aux3.father; }
           
RefreshExtract(aux3.father); return;
       
}
       
public AVL<Tkey, Tvalue> ContainsKey(Tkey key)
       
{
           
return Search(this, key);
       
}

       
public static void Clear(AVL<Tkey, Tvalue> avl)
       
{
           avl
= new AVL<Tkey, Tvalue>();
       
}

       
#endregion
       
#region ( Protected Methods )

       
protected bool IsEmpty()
       
{
           
return key == null || key.Equals(default(Tkey));
       
}
       
protected bool Isleaf()
       
{
           
return height == 0;
       
}
       
protected void Swap(AVL<Tkey, Tvalue> aux, AVL<Tkey, Tvalue> aux3)
       
{
           aux
.key = aux3.key;
           aux
.Value = aux3.Value;
       
}
       
protected void RefreshHeightAndBF()
       
{
           
if (IsEmpty())
           
{ height = -1; balanceFactor = 0; }
           
else
           
{
               height
= 1 + Math.Max(sonLeft.height, sonRight.height);
               balanceFactor
= sonRight.height - sonLeft.height;
           
}
       
}
       
protected void RefreshAdd(AVL<Tkey, Tvalue> avl, Tkey key, Tvalue value)
       
{
           avl
.Key = key;
           avl
.Value = value;
           avl
.sonLeft = new AVL<Tkey, Tvalue>();
           avl
.sonLeft.father = avl;
           avl
.sonLeft.son = -1;
           avl
.sonRight = new AVL<Tkey, Tvalue>();
           avl
.sonRight.father = avl;
           avl
.sonRight.son = 1;
           avl
.RefreshHeightAndBF();
       
}
       
protected void BalanceAdd(AVL<Tkey, Tvalue> avl)
       
{
           avl
.RefreshHeightAndBF();
           
if (avl.balanceFactor == 0) return;
           
else if (avl.balanceFactor == -1 || avl.balanceFactor == 1)
           
{ if (avl.father != null) BalanceAdd(avl.father); }
           
else if (avl.balanceFactor == 2 && avl.sonRight.balanceFactor == 1)
           
{
               
RotationLeft(avl);/*Refresh:*/
               avl
.sonLeft.RefreshHeightAndBF(); avl.RefreshHeightAndBF(); return;
           
}
           
else if (avl.balanceFactor == 2 && avl.sonRight.balanceFactor == -1)
           
{
               
RotationRight(avl.sonRight);/*Refresh:*/
               avl
.sonRight.sonRight.RefreshHeightAndBF(); avl.sonRight.RefreshHeightAndBF();
               
RotationLeft(avl);/*Refresh:*/
               avl
.sonLeft.RefreshHeightAndBF(); avl.RefreshHeightAndBF(); return;
           
}
           
else if (avl.balanceFactor == -2 && avl.sonLeft.balanceFactor == -1)
           
{
               
RotationRight(avl);/*Refresh:*/
               avl
.sonRight.RefreshHeightAndBF(); avl.RefreshHeightAndBF(); return;
           
}
           
else if (avl.balanceFactor == -2 && avl.sonLeft.balanceFactor == 1)
           
{
               
RotationLeft(avl.sonLeft);/*Refresh:*/
               avl
.sonLeft.sonLeft.RefreshHeightAndBF(); avl.sonLeft.RefreshHeightAndBF();
               
RotationRight(avl);/*Refresh:*/
               avl
.sonRight.RefreshHeightAndBF(); avl.RefreshHeightAndBF(); return;
           
}
       
}
       
protected void RefreshExtract(AVL<Tkey, Tvalue> avl)
       
{
           avl
.RefreshHeightAndBF();
           
if (avl.balanceFactor == -1 || avl.balanceFactor == 1) return;
           
else if (avl.balanceFactor == 0)
           
{ if (avl.father != null) RefreshExtract(avl.father); }
           
else if (avl.balanceFactor == -2 && avl.sonLeft.balanceFactor == 0)
           
{
               
RotationRight(avl);/*Refresh:*/
               avl
.sonRight.RefreshHeightAndBF(); avl.RefreshHeightAndBF(); return;
           
}
           
else if (avl.balanceFactor == -2 && avl.sonLeft.balanceFactor == -1)
           
{
               
RotationRight(avl);/*Refresh:*/
               avl
.sonRight.RefreshHeightAndBF(); avl.RefreshHeightAndBF();
               
if (avl.father != null) RefreshExtract(avl.father);
           
}
           
else if (avl.balanceFactor == -2 && avl.sonLeft.balanceFactor == 1)
           
{
               
RotationLeft(avl.sonLeft);/*Refresh:*/
               avl
.sonLeft.sonLeft.RefreshHeightAndBF(); avl.sonLeft.RefreshHeightAndBF();
               
RotationRight(avl);/*Refresh:*/
               avl
.sonRight.RefreshHeightAndBF(); avl.RefreshHeightAndBF();
               
if (avl.father != null) RefreshExtract(avl.father);
           
}
           
else if (avl.balanceFactor == 2 && avl.sonRight.balanceFactor == 0)
           
{
               
RotationLeft(avl);/*Refresh:*/
               avl
.sonLeft.RefreshHeightAndBF(); avl.RefreshHeightAndBF(); return;
           
}
           
else if (avl.balanceFactor == 2 && avl.sonRight.balanceFactor == 1)
           
{
               
RotationLeft(avl);/*Refresh:*/
               avl
.sonLeft.RefreshHeightAndBF(); avl.RefreshHeightAndBF();
               
if (avl.father != null) RefreshExtract(avl.father);
           
}
           
else if (avl.balanceFactor == 2 && avl.sonRight.balanceFactor == -1)
           
{
               
RotationRight(avl.sonRight);/*Refresh:*/
               avl
.sonRight.sonRight.RefreshHeightAndBF(); avl.sonRight.RefreshHeightAndBF();
               
RotationLeft(avl);/*Refresh:*/
               avl
.sonLeft.RefreshHeightAndBF(); avl.RefreshHeightAndBF();
               
if (avl.father != null) RefreshExtract(avl.father);
           
}
       
}
       
protected void RotationRight(AVL<Tkey, Tvalue> avl)
       
{
           AVL
<Tkey, Tvalue> primary = new AVL<Tkey, Tvalue>();
           primary
.Key = avl.Key;
           primary
.Value = avl.Value;
           avl
.key = avl.sonLeft.key;
           avl
.Value = avl.sonLeft.Value;
           primary
.sonRight = avl.sonRight;
           avl
.sonRight.father = primary;
           avl
.sonRight = primary;
           primary
.son = 1;
           avl
.sonRight.father = avl;
           primary
.sonLeft = avl.sonLeft.sonRight;
           primary
.sonLeft.son = -1;
           avl
.sonLeft.sonRight.father = primary;
           avl
.sonLeft = avl.sonLeft.sonLeft;
           avl
.sonLeft.father = avl;
       
}
       
protected void RotationLeft(AVL<Tkey, Tvalue> avl)
       
{
           AVL
<Tkey, Tvalue> primary = new AVL<Tkey, Tvalue>();
           primary
.Key = avl.Key;
           primary
.Value = avl.Value;
           avl
.key = avl.sonRight.key;
           avl
.Value = avl.sonRight.Value;
           primary
.sonLeft = avl.sonLeft;
           avl
.sonLeft.father = primary;
           avl
.sonLeft = primary;
           primary
.son = -1;
           avl
.sonLeft.father = avl;
           primary
.sonRight = avl.sonRight.sonLeft;
           primary
.sonRight.son = 1;
           avl
.sonRight.sonLeft.father = primary;
           avl
.sonRight = avl.sonRight.sonRight;
           avl
.sonRight.father = avl;
       
}
       
protected AVL<Tkey, Tvalue> Search(AVL<Tkey, Tvalue> avl, Tkey key)
       
{
           
if (avl.IsEmpty()) return avl;
           
if (key.CompareTo(avl.Key) < 0)
           
{
               avl
= avl.sonLeft;
               
return Search(avl, key);
           
}
           
if (key.CompareTo(avl.Key) > 0)
           
{
               avl
= avl.sonRight;
               
return Search(avl, key);
           
}
           
return avl;
       
}
       
protected AVL<Tkey, Tvalue> SearchQuantityOfSon(AVL<Tkey, Tvalue> aux)
       
{
           
if (!aux.sonLeft.IsEmpty() && !aux.sonRight.IsEmpty()) return null;
           
else if (aux.sonLeft.IsEmpty() && !aux.sonRight.IsEmpty()) return aux.sonRight;
           
else return aux.sonLeft;
       
}
       
protected AVL<Tkey, Tvalue> SearchLessOfBiggest(AVL<Tkey, Tvalue> aux)
       
{
           
if (aux.sonLeft.IsEmpty()) return aux;
           aux
= aux.sonLeft;
           
return SearchLessOfBiggest(aux);
       
}

       
#endregion
   
} }