EdD - Clase BalancedTree (definitivamente lo más útil)

Ir abajo

EdD - Clase BalancedTree (definitivamente lo más útil)

Mensaje  Admin el Jue Nov 03, 2011 6:21 pm

Primero el código de un nodo para árbol balanceado:
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 !!!
avatar
Admin
Admin

Cantidad de envíos : 94
Fecha de inscripción : 28/08/2009

http://www.jtentor.com.ar

Volver arriba Ir abajo

Volver arriba

- Temas similares

 
Permisos de este foro:
No puedes responder a temas en este foro.