EdD - Clase BalancedTree (definitivamente lo más útil)
Página 1 de 1.
EdD - Clase BalancedTree (definitivamente lo más útil)
Primero el código de un nodo para árbol balanceado:
Aquí está todo lo necesario para un árbol balanceado AVL con grado de libertad 2.
Pueden deleitarse siguiendo el código de las rotaciones, obviamente no se puede aprender de memoria todo esto; sin embargo si se puede verificar que lo que hace lo hace bién, ESO ES LO QUE DEBE HACER UN DESARROLLADOR !!!
- Código:
using System;
namespace E05
{
/// <summary>
/// Clase para representar un nodo de un árbol binario
/// </summary>
/// <typeparam name="ELEMENT">Tipo de dato del elemento</typeparam>
public class NodeAVL<ELEMENT>
{
#region Estructura Interna y Propiedades
/// <summary>
/// Mantiene el elemento en el nodo
/// </summary>
private ELEMENT _Item;
/// <summary>
/// Facililta el acceso al elemento en el nodo
/// </summary>
public virtual ELEMENT Item
{
get { return this._Item; }
set { this._Item = value; }
}
/// <summary>
/// Mantiene el enlace al subárbol izquierdo
/// </summary>
private NodeAVL<ELEMENT> _Left;
/// <summary>
/// Facilita el acceso al enlace al subárbol izquierdo
/// </summary>
public virtual NodeAVL<ELEMENT> Left
{
get { return this._Left; }
set { this._Left = value; }
}
/// <summary>
/// Mantiene el elace al subárbol derecho
/// </summary>
private NodeAVL<ELEMENT> _Right;
/// <summary>
/// Facilita el acceso al enlace al subárbol derecho
/// </summary>
public virtual NodeAVL<ELEMENT> Right
{
get { return this._Right; }
set { this._Right = value; }
}
/// <summary>
/// Mantiene el factor de equilibrio del nodo
/// </summary>
private int _Balance;
/// <summary>
/// Facilita el acceso al factor de equilibrio del nodo
/// </summary>
public int Balance
{
get { return _Balance; }
set { _Balance = value; }
}
#endregion
#region Constructores
/// <summary>
/// Constructor por defecto, inicializa los campos de la estructura
/// interna en valores por defecto
/// </summary>
public NodeAVL()
{
this.Item = default(ELEMENT);
this.Left = null;
this.Right = null;
this.Balance = 0;
}
/// <summary>
/// Constructor especializado, permite fijar el elemento del nodo
/// </summary>
/// <param name="item">Elemento en el nodo</param>
public NodeAVL(ELEMENT item)
: this()
{
this.Item = item;
}
/// <summary>
/// Constructor especializado, permite fijar el elemento del nodo
/// y el valor de los enlaces a subárboles izquierdo y derecho
/// </summary>
/// <param name="item">Elemento en el nodo</param>
/// <param name="next">Enlace al subárbol izquierdo</param>
/// <param name="prev">Enlace al subárbol derecho</param>
public NodeAVL(ELEMENT item, NodeAVL<ELEMENT> left, NodeAVL<ELEMENT> right)
: this()
{
this.Item = item;
this.Left = left;
this.Right = right;
}
#endregion
/// <summary>
/// Metodo para probar las distintas formas en que
/// se puede recorrer un árbol
/// </summary>
public virtual void Visit()
{
Console.Write("{0} ", this.Item.ToString());
}
}
}
Aquí está todo lo necesario para un árbol balanceado AVL con grado de libertad 2.
- Código:
using System;
using System.Text;
namespace E05
{
/// <summary>
/// Implementación de árbol binario
/// </summary>
/// <typeparam name="ELEMENT">Tipo de dato de elementos que se introduce en el árbol</typeparam>
public class BalancedTree<ELEMENT> where ELEMENT : IComparable
{
#region Estructura Interna y Propiedades
/// <summary>
/// Mantiene la raíz del árbol
/// </summary>
private NodeAVL<ELEMENT> _Root;
/// <summary>
/// Facililta el acceso a la raíz del árbol
/// </summary>
protected virtual NodeAVL<ELEMENT> Root
{
get { return this._Root; }
set { this._Root = value; }
}
#endregion
#region Otras Propiedades
/// <summary>
/// Indica si el árbol está vacio
/// </summary>
public virtual Boolean IsEmpty
{
get { return this.Root == null; }
}
#endregion
#region Constructores
/// <summary>
/// Constructor por defecto
/// </summary>
public BalancedTree()
{
this.Root = null;
}
/// <summary>
/// Constructor especializado, permite asignar
/// el valor del item de la raíz del árbol
/// </summary>
/// <param name="root">referencia al item de la raíz del árbol, puede ser null</param>
public BalancedTree(ELEMENT item)
: this()
{
this.Root = new NodeAVL<ELEMENT>(item);
}
/// <summary>
/// Constructor especializado, permite asignar
/// el valor del item de la raíz del árbol y
/// los subárboles izquierdo y derecho
/// </summary>
/// <param name="root">referencia al item de la raíz del árbol, puede ser null</param>
/// <param name="left">referencia a un árbol que estará a la izquierda, puede ser null</param>
/// <param name="right">referencia a un árbol que estará a la derecha, puede ser null</param>
public BalancedTree(ELEMENT item, BalancedTree<ELEMENT> leftTree, BalancedTree<ELEMENT> rightTree)
: this()
{
this.Root = new NodeAVL<ELEMENT>(item);
if (leftTree != null)
{
this.Root.Left = leftTree.Root;
}
if (rightTree != null)
{
this.Root.Right = rightTree.Root;
}
}
#endregion
#region Comportamiento heredado de object
/// <summary>
/// Muestra la representación del árbol en forma de lista
/// </summary>
/// <returns>Cadena con la representación</returns>
public override string ToString()
{
return ToString(this.Root);
}
/// <summary>
/// Implementación recursiva para mostrar un árbol en forma de lista
/// </summary>
/// <param name="root">Nodo del árbol</param>
/// <returns>Cadena con la representación</returns>
protected virtual string ToString(NodeAVL<ELEMENT> root)
{
StringBuilder sb = new StringBuilder();
if (root != null)
{
sb.Append(root.Item.ToString());
if (root.Left != null)
{
sb.Append(" (" + ToString(root.Left));
if (root.Right != null)
{
sb.Append(", " + ToString(root.Right));
}
sb.Append(")");
}
else
{
if (root.Right != null)
{
sb.Append(" (, " + ToString(root.Right) + ")");
}
}
}
return sb.ToString(); ;
}
#endregion
#region Comportamiento para recorrer un árbol
/// <summary>
/// Implementación del recorrido Pre Orden
/// para la instancia
/// </summary>
public virtual void PreOrder()
{
PreOrder(this.Root);
}
/// <summary>
/// Implementación recursiva para recorrer un
/// árbol en Pre Orden
/// </summary>
/// <param name="root">Nodo a visitar</param>
protected virtual void PreOrder(NodeAVL<ELEMENT> root)
{
if (root != null)
{
root.Visit();
PreOrder(root.Left);
PreOrder(root.Right);
}
}
/// <summary>
/// Implementación del recorrido En Orden
/// para la instancia
/// </summary>
public virtual void InOrder()
{
InOrder(this.Root);
}
/// <summary>
/// Implementación recursiva para recorrer un
/// árbol en En Orden
/// </summary>
/// <param name="root">Nodo a visitar</param>
protected virtual void InOrder(NodeAVL<ELEMENT> root)
{
if (root != null)
{
InOrder(root.Left);
root.Visit();
InOrder(root.Right);
}
}
/// <summary>
/// Implementación del recorrido Post Orden
/// para la instancia
/// </summary>
public virtual void PostOrder()
{
PostOrder(this.Root);
}
/// <summary>
/// Implementación recursiva para recorrer un
/// árbol en PostOrden
/// </summary>
/// <param name="root">Nodo a visitar</param>
protected virtual void PostOrder(NodeAVL<ELEMENT> root)
{
if (root != null)
{
PostOrder(root.Left);
PostOrder(root.Right);
root.Visit();
}
}
#endregion
#region Búsqueda de un elemento
/// <summary>
/// Determina si un elemento está contenido en el árbol
/// </summary>
/// <param name="item">Elemento a controlar</param>
/// <returns>Verdadero si el elemento se encuentra contenido en el árbol</returns>
public virtual Boolean Contains(ELEMENT item)
{
return Contains(this.Root, item);
}
/// <summary>
/// Implementación recursivoa para determinar si un elemento
/// se encuentra contenido en el árbol
/// </summary>
/// <param name="root">Nodo raíz del subárbol a considerar</param>
/// <param name="item">Elemento a controlar</param>
/// <returns>Verdadero si el elemento se encuentra contenido en el árbol</returns>
protected virtual Boolean Contains(NodeAVL<ELEMENT> root, ELEMENT item)
{
if (root == null)
{
return false;
}
if (item.CompareTo(root.Item) < 0)
{
return Contains(root.Left, item);
}
else
{
if (item.CompareTo(root.Item) > 0)
{
return Contains(root.Right, item);
}
}
return true;
}
/// <summary>
/// Busca un elemento en el árbol
/// </summary>
/// <param name="item">Elemento a buscar</param>
/// <returns>Referencia al elemento o null si no está en el árbol</returns>
public virtual ELEMENT Find(ELEMENT item)
{
return Find(this.Root, item);
}
/// <summary>
/// Implementación recursiva para buscar un elemento en el árbol
/// </summary>
/// <param name="root">Nodo raíz del subárbol a considerar</param>
/// <param name="item">Elemento a buscar</param>
/// <returns>Referencia al elemento o null si no está en el árbol</returns>
protected virtual ELEMENT Find(NodeAVL<ELEMENT> root, ELEMENT item)
{
if (root == null)
{
return default(ELEMENT);
}
if (item.CompareTo(root.Item) < 0)
{
return Find(root.Left, item);
}
else
{
if (item.CompareTo(root.Item) > 0)
{
return Find(root.Right, item);
}
}
return root.Item;
}
#endregion
#region Agregar un elemento
/// <summary>
/// Agrega un elemento en el árbol equilibrado
/// </summary>
/// <param name="item">Elemento a agregar</param>
public virtual void Add(ELEMENT item)
{
bool flag = false;
this.Root = AddAVL(this.Root, item, ref flag);
}
/// <summary>
/// Implementación recursiva para agregar un elemento en un
/// árbol equilibrado utilizando los conceptos de A V L
/// </summary>
/// <param name="root">Nodo raiz del subárbol a considerar</param>
/// <param name="item">Elemento a agregar</param>
/// <param name="flag">Bandera que indica que cambió la altura</param>
/// <returns>Nodo raiz del subárbol considerado</returns>
protected virtual NodeAVL<ELEMENT> AddAVL(NodeAVL<ELEMENT> root, ELEMENT item, ref bool flag)
{
NodeAVL<ELEMENT> n1;
// Si el árbol está vacio, simplement se agrega
// y se indica que cambió la altura
if (root == null)
{
root = new NodeAVL<ELEMENT>(item);
flag = true;
}
else
{
if (item.CompareTo(root.Item) < 0)
{
// El valor del elemento a agregar es menor
// que el valor de la raíz del subárbol
// Se agrega recursivamente por la izquierda
root.Left = AddAVL(root.Left, item, ref flag);
if (flag) // cambió la altura ?
{
switch (root.Balance)
{
case 1:
// antes derecha > izquierda, después se equilibra
// y cambia la bandera
root.Balance = 0;
flag = false;
break;
case 0:
// anstes derecha = izquierda, después izquierda mas grande
// en algún nivel superior puede hacer falta un rebalanceo
// la bandera queda como estaba (true)
root.Balance = -1;
break;
case -1:
// antes derecha < izquierda, hay que rebalancear
n1 = root.Left;
if (n1.Balance == -1)
{
// la izquierda de la izquierda es mayor
// rotación simple izquierda-izquierda
root = LeftLeftRotation(root, n1);
}
else
{
// rotación doble izquierda-derecha
root = LeftRightRotation(root, n1);
}
// subárbol ajustado cambia la bandera
flag = false;
break;
}
}
}
else
{
if (item.CompareTo(root.Item) > 0)
{
// El valor del elemento a agregar es mayor
// que el valor de la raíz del subárbol
// Se agrega recursivamente por la derecha
root.Right = AddAVL(root.Right, item, ref flag);
if (flag) // cambió la altura ?
{
switch (root.Balance)
{
case 1:
// antes derecha > izquierda, hay que rebalancer
n1 = root.Right;
if (n1.Balance == 1)
{
// la derecha de la derecha es mayor
// rotación simple derecha-derecha
root = RightRightRotation(root, n1);
}
else
{
// rotación doble derecha-izquierda
root = RightLeftRoation(root, n1);
}
// subárbol ajustado cambia la bandera
flag = false;
break;
case 0:
// antes derecha = izquierda, después la derecha mas grande
// en algún nivel superior puede hacer falta un rebalanceo
// la bandera queda como estaba (true)
root.Balance = 1;
break;
case -1:
// antes derecha < izquierda, despues se equilibra
// y cambia la bandera
root.Balance = 0;
flag = false;
break;
}
}
}
else
{
// No se puede almacenar claves repetidas
throw new Exception("Claves repetidas");
}
}
}
return root;
}
#endregion
#region Extraer un elemento
/// <summary>
/// Extrae un elemento en el árbol equilibrado
/// </summary>
/// <param name="item">Elemento a extraer</param>
public virtual void Remove(ELEMENT item)
{
bool flag = false;
this.Root = RemoveAVL(this.Root, item, ref flag);
}
/// <summary>
/// Implementación recursiva para extraer un elemento en un
/// árbol equilibrado utilizando los conceptos de A V L
/// </summary>
/// <param name="root">Nodo raiz del subárbol a considerar</param>
/// <param name="item">Elemento a extraer</param>
/// <param name="flag">Bandera que indica que cambió la altura</param>
/// <returns>Nodo raiz del subárbol considerado</returns>
protected virtual NodeAVL<ELEMENT> RemoveAVL(NodeAVL<ELEMENT> root, ELEMENT item, ref bool flag)
{
// No se puede extraer nodos de un árbol vacío
if (root == null)
{
throw new Exception("No existe");
}
if (item.CompareTo(root.Item) < 0)
{
// El valor del elemento a extraer es menor
// que el valor de la raíz del subárbol
// Se procesa recursivamente por la izquierda
root.Left = RemoveAVL(root.Left, item, ref flag);
if (flag)
{
// Cambió la altura, analizar el balance
root = LeftBalance(root, ref flag);
}
}
else
{
if (item.CompareTo(root.Item) > 0)
{
// El valor del elemento a extraer es mayor
// que el valor de la raíz del subárbol
// Se procesa recursivamente por la derecha
root.Right = RemoveAVL(root.Right, item, ref flag);
if (flag)
{
// Cambió la altura, analizar el balance
root = RightBalance(root, ref flag);
}
}
else
{ // encontrado
NodeAVL<ELEMENT> q;
q = root;
if (q.Left == null)
{
// Un único descendiente, cambia la altura
root = q.Right;
flag = true;
}
else
{
if (q.Right == null)
{
// Un único descendiente, cambia la altura
root = q.Left;
flag = true;
}
else
{ // tiene dos subárboles !!!
root.Left = Repleace(root, root.Left, ref flag);
if (flag)
{
// Cambió la altura, analizar el balance
root = LeftBalance(root, ref flag);
}
q = null;
}
}
}
}
return root;
}
#endregion
#region Utilitarios para extraer un elemento
/// <summary>
/// Aplica mayor de los menores controlando el cambio de altura
/// La técnica aplicada es eliminación por copia con búsqueda recursiva
/// </summary>
/// <param name="n">Nodo que debe extraerse</param>
/// <param name="act">Nodo que corresponde al mayor de los menores</param>
/// <param name="flag">Bandera que indica que cambió la altura</param>
/// <returns></returns>
protected virtual NodeAVL<ELEMENT> Repleace(NodeAVL<ELEMENT> n, NodeAVL<ELEMENT> act, ref bool flag)
{
if (act.Right != null)
{
// hay algo a la derecha, es mayor que el actual
act.Right = Repleace(n, act.Right, ref flag);
if (flag)
{
// Cambió la altura, analizar el balance
act = RightBalance(act, ref flag);
}
}
else
{
// act es el mayor de los menores
// copiar el elemento y anular la referencia
// cambia la altura
n.Item = act.Item;
n = act;
act = act.Left;
n = null;
flag = true;
}
return act;
}
/// <summary>
/// Analiza las posibles rotaciones cuando se extrajo un nodo de la izquierda
/// </summary>
/// <param name="n">Nodo a considerar</param>
/// <param name="flag">Bandera que indica que cambió la altura</param>
/// <returns>Nodo considerado</returns>
protected virtual NodeAVL<ELEMENT> LeftBalance(NodeAVL<ELEMENT> n, ref bool flag)
{
NodeAVL<ELEMENT> n1;
switch (n.Balance)
{
case -1:
// antes izquierda > derecha, después se equilibra
n.Balance = 0;
break;
case 0:
// antes izquierda = derecha, despues se ajusta
// y cambia la altura
n.Balance = 1;
flag = false;
break;
case 1:
// antes izquierda < derecha, hay que rebalancer
// situaciones especiales para el cambio de altura
n1 = n.Right;
if (n1.Balance >= 0)
{
flag = false;
n = RightRightRotation(n, n1);
}
else
{
n = RightLeftRoation(n, n1);
}
break;
}
return n;
}
/// <summary>
/// Analiza las posibles rotaciones cuando se extrajo un nodo de la derecha
/// </summary>
/// <param name="n">Nodo a considerar</param>
/// <param name="flag">Bandera que indica que cambió la altura</param>
/// <returns>Nodo considerado</returns>
protected virtual NodeAVL<ELEMENT> RightBalance(NodeAVL<ELEMENT> n, ref bool flag)
{
NodeAVL<ELEMENT> n1;
switch (n.Balance)
{
case -1:
// antes izquierda > derecha, hay que rebalancer
// situaciones especiales para el cambio de altura
n1 = n.Left;
if (n1.Balance <= 0)
{
if (n1.Balance == 0)
{
flag = false;
}
n = LeftLeftRotation(n, n1);
}
else
{
n = LeftRightRotation(n, n1);
}
break;
case 0:
// antes izquierda = derecha, después se ajusta
// y cambia la altura
n.Balance = -1;
flag = false;
break;
case 1:
// antes izquierda < derecha, después se equilibra
n.Balance = 0;
break;
}
return n;
}
#endregion
#region Rotaciones
/// <summary>
/// Rotacion simple Izquierda - Izquierda
/// </summary>
/// <param name="n">Nodo raíz a considerar</param>
/// <param name="n1">Nodo a la izquierda del raíz a considerar</param>
/// <returns>Nuevo nodo raíz</returns>
protected virtual NodeAVL<ELEMENT> LeftLeftRotation(NodeAVL<ELEMENT> n, NodeAVL<ELEMENT> n1)
{
n.Left = n1.Right;
n1.Right = n;
if (n1.Balance == -1)
{
n.Balance = 0;
n1.Balance = 0;
}
else
{
n.Balance = -1;
n1.Balance = 1;
}
return n1;
}
/// <summary>
/// Rotacion doble Izquierda - Derecha
/// </summary>
/// <param name="n">Nodo raíz a considerar</param>
/// <param name="n1">Nodo a la izquierda del raíz a considerar</param>
/// <returns>Nuevo nodo raíz</returns>
protected virtual NodeAVL<ELEMENT> LeftRightRotation(NodeAVL<ELEMENT> n, NodeAVL<ELEMENT> n1)
{
// Nodo a la derecha del nodo que está a la izquierda del nodo raíz a considerar
NodeAVL<ELEMENT> n2;
n2 = n1.Right;
n.Left = n2.Right;
n2.Right = n;
n1.Right = n2.Left;
n2.Left = n1;
n1.Balance = (n2.Balance == 1) ? -1 : 0;
n.Balance = (n2.Balance == -1) ? 1 : 0;
n2.Balance = 0;
return n2;
}
/// <summary>
/// Rotacion simple Derecha - Derecha
/// </summary>
/// <param name="n">Nodo raíz a considerar</param>
/// <param name="n1">Nodo a la derecha del raíz a considerar</param>
/// <returns>Nuevo nodo raíz</returns>
protected virtual NodeAVL<ELEMENT> RightRightRotation(NodeAVL<ELEMENT> n, NodeAVL<ELEMENT> n1)
{
n.Right = n1.Left;
n1.Left = n;
if (n1.Balance == 1)
{
n.Balance = 0;
n1.Balance = 0;
}
else
{
n.Balance = 1;
n1.Balance = -1;
}
return n1;
}
/// <summary>
/// Rotacion doble Derecha - Izquierda
/// </summary>
/// <param name="n">Nodo raíz a considerar</param>
/// <param name="n1">Nodo a la derecha del raíz a considerar</param>
/// <returns>Nuevo nodo raíz</returns>
protected virtual NodeAVL<ELEMENT> RightLeftRoation(NodeAVL<ELEMENT> n, NodeAVL<ELEMENT> n1)
{
// Nodo a la izquierda del nodo que está a la derecha del nodo raíz a considerar
NodeAVL<ELEMENT> n2;
n2 = n1.Left;
n.Right = n2.Left;
n2.Left = n;
n1.Left = n2.Right;
n2.Right = n1;
n.Balance = (n2.Balance == 1) ? -1 : 0;
n1.Balance = (n2.Balance == -1) ? 1 : 0;
n2.Balance = 0;
return n2;
}
#endregion
}
}
Pueden deleitarse siguiendo el código de las rotaciones, obviamente no se puede aprender de memoria todo esto; sin embargo si se puede verificar que lo que hace lo hace bién, ESO ES LO QUE DEBE HACER UN DESARROLLADOR !!!
Temas similares
» EdD - Clase BinarySearchTree (esto es mucho más útil)
» EdD - Clase Stack (alternativa a la clase desarrollada en teoría)
» EdD - Clase BinaryTree (lo más simple)
» EdD - Clase Stack (desarrollada en teoría)
» EdD - Clase Queue (desarrollada en teoría)
» EdD - Clase Stack (alternativa a la clase desarrollada en teoría)
» EdD - Clase BinaryTree (lo más simple)
» EdD - Clase Stack (desarrollada en teoría)
» EdD - Clase Queue (desarrollada en teoría)
Página 1 de 1.
Permisos de este foro:
No puedes responder a temas en este foro.
|
|