mikiman Blog
(>_<)
El verdadero amigo es aquel que está a tu lado cuando preferiria estar en otra parte.

America TV señal Online [Solo IP´s Peruanas]

Posted By Mikiman on marzo 20th, 2011

http://mikiman.notengointer.net/america-tv-senal-online-solo-ip%c2%b4s-peruanas.html
 

Posts Tagged ‘Programacion’

Arbol AVL [C Sharp]

por: Mikiman on julio 5th, 2011

http://mikiman.notengointer.net/arbol-avl-c-sharp.html

Listas Enlazadas Dobles
Árbol AVL es un tipo especial 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ó.

Arbol binario No-AVL

Arbol Binario AVL

Para mas info sobre arboles AVL ve a la Wikipedia - Arboles AVL

1.- Primero Creamos un Nuevo Proyecto al que llamaremos "arbol-AVL".
2.- Creamos una clase que nos servira de Nodo "Nodo.sc".
Estructura de la Clase Nodo.sc

Clic para ver Texto Plano
C#:
  1. class Nodo
  2.     {
  3.         private double dato;
  4.         private Nodo nodoIzquierdo;
  5.         private Nodo nodoDerecho;
  6.         private Nodo padre;
  7.         private int fEq;
  8.  
  9.         private Arbol tree;
  10.  
  11.         public Nodo(double dato)
  12.         {
  13.             this.dato = dato;
  14.             this.fEq = 0;
  15.             this.nodoIzquierdo = this.nodoDerecho = this.padre = null;
  16.         }
  17.  
  18.         public double Dato
  19.         {
  20.             get { return dato; }
  21.             set { dato = value; }
  22.         }
  23.  
  24.         public int FactEq
  25.         {
  26.             get { return fEq; }
  27.             set { fEq = value; }
  28.         }
  29.  
  30.         public Nodo NodoIzquierdo
  31.         {
  32.             get { return nodoIzquierdo; }
  33.             set { nodoIzquierdo = value; }
  34.         }
  35.  
  36.         public Nodo NodoDerecho
  37.         {
  38.             get { return nodoDerecho; }
  39.             set { nodoDerecho = value; }
  40.         }
  41.  
  42.         public Nodo Padre
  43.         {
  44.             get { return padre; }
  45.             set { padre = value; }
  46.         }
  47.  
  48.         public Arbol Tree
  49.         {
  50.             get { return tree; }
  51.             set { tree = value; }
  52.         }
  53.     }

3.- Creamos una clase "Arbol.sc" para poder enlazar nodo a nodo
Estructura de la Clase Arbol.sc.

Clic para ver Texto Plano
C#:
  1. class Arbol
  2.     {
  3.         private Nodo root;
  4.  
  5.         private int size;
  6.  
  7.         public void limpiar()
  8.         {
  9.             this.root = null;
  10.         }
  11.  
  12.         public Arbol()
  13.         {
  14.             this.root = null;
  15.         }
  16.  
  17.         public Nodo Root
  18.         {
  19.             get { return root; }
  20.             set { root = value; }
  21.         }
  22.  
  23.         public void aInsertarNodos()
  24.         {
  25.             Console.Write("Ingresar Dato : ");
  26.             double dato = double.Parse(Console.ReadLine());
  27.             Add(dato);
  28.         }
  29.  
  30.         public void aInsertarVariosNodos(string nodos)
  31.         {
  32.             string[] noditos = nodos.Trim().Split(' ');
  33.             double x;
  34.             for (int z = 0; z <noditos.Length; z++)
  35.             {
  36.                 if (double.TryParse(noditos[z], out x))
  37.                 {
  38.                     Add(x);
  39.                 }
  40.                 else
  41.                 {
  42.                     Console.WriteLine("Error de Parsing");
  43.                 }
  44.             }
  45.         }
  46.  
  47.         private void Add(double valor)
  48.         {
  49.             Nodo nuevo = new Nodo(valor);
  50.             Add(nuevo);
  51.  
  52.             Nodo nodoPadre = nuevo.Padre;
  53.  
  54.             while (nodoPadre != null)
  55.             {
  56.                 int balance = getBalance(nodoPadre);
  57.                 if (Math.Abs(balance) == 2) //-2 o 2 = Desvalanceado
  58.                 {
  59.                     //Rebalancear arbol
  60.                     balancear(nodoPadre, balance);
  61.                 }
  62.                 nodoPadre = nodoPadre.Padre;
  63.             }
  64.             Console.ReadKey();
  65.         }
  66.  
  67.         private void Add(Nodo nuevo)
  68.         {
  69.             if (root == null)
  70.             {
  71.                 this.root = nuevo;
  72.                 nuevo.Tree = this; //asignar a este nodo de árbol binario
  73.                 Console.WriteLine("\n\tInsertando -->> {0}", nuevo.Dato);
  74.                 size++;
  75.             }
  76.             else
  77.             {
  78.                 if (nuevo.Padre == null)
  79.                     nuevo.Padre = root;
  80.  
  81.                 if (nuevo.Dato <nuevo.Padre.Dato)
  82.                 {
  83.                     if (nuevo.Padre.NodoIzquierdo == null)
  84.                     {
  85.                         nuevo.Padre.NodoIzquierdo = nuevo;
  86.                         Console.WriteLine("\tInsertando a la Izquierda -->> {0}", nuevo.Dato);
  87.                         //Console.WriteLine("factor de equilibrio -->> {0}", getBalance(node));
  88.                         size++;
  89.                         nuevo.Tree = this;//asignar a este nodo de árbol binario
  90.                     }
  91.                     else
  92.                     {
  93.                         nuevo.Padre = nuevo.Padre.NodoIzquierdo;
  94.                         Add(nuevo);
  95.                     }
  96.                 }
  97.                 else
  98.                 {
  99.                     if (nuevo.Dato> nuevo.Padre.Dato)
  100.                     {
  101.                         if (nuevo.Padre.NodoDerecho == null)
  102.                         {
  103.                             nuevo.Padre.NodoDerecho = nuevo;
  104.                             Console.WriteLine("\tInsertando a la Derecha -->> {0}", nuevo.Dato);
  105.                             //Console.WriteLine("factor de equilibrio -->> {0}", getBalance(node));
  106.                             size++;
  107.                             nuevo.Tree = this; //asignar a este nodo de árbol binario
  108.                         }
  109.                         else
  110.                         {
  111.                             nuevo.Padre = nuevo.Padre.NodoDerecho;
  112.                             Add(nuevo);
  113.                         }
  114.                     }
  115.                     else
  116.                     {
  117.                         Console.WriteLine("\tNo se pudo insertar -->> {0}", nuevo.Dato);
  118.                     }
  119.                 }
  120.             }
  121.         }
  122.  
  123.         private void balancear(Nodo nodito, int balance)
  124.         {
  125.             if (balance == 2)
  126.             {
  127.                 int balanceDerecho = getBalance(nodito.NodoDerecho);
  128.  
  129.                 if (balanceDerecho == 1 || balanceDerecho == 0)
  130.                 {
  131.                     Console.WriteLine("\t -->> Rotando a la Izquierda Nodo [{0}] Balance -> {1}", nodito.Dato, getBalance(nodito));
  132.                     rotarIzquierda(nodito);
  133.                 }
  134.                 else if (balanceDerecho == -1)
  135.                 {
  136.                     Console.WriteLine("\t -->> Rotando a la Derecha Nodo [{0}] Balance -> {1}", nodito.NodoDerecho.Dato, getBalance(nodito.NodoIzquierdo));
  137.                     rotarDerecha(nodito.NodoDerecho);
  138.  
  139.                     Console.WriteLine("\t -->> Rotando a la Izquierda Nodo [{0}] Balance -> {1}", nodito.Dato, getBalance(nodito));
  140.                     rotarIzquierda(nodito);
  141.                 }
  142.             }
  143.             else if (balance == -2)
  144.             {
  145.                 int leftBalance = getBalance(nodito.NodoIzquierdo);
  146.                 if (leftBalance == 1)
  147.                 {
  148.                     Console.WriteLine("\t -->> Rotando a la Izquierda Nodo [{0}] Balance -> {1}", nodito.NodoIzquierdo.Dato, getBalance(nodito.NodoIzquierdo));
  149.                     rotarIzquierda(nodito.NodoIzquierdo);
  150.  
  151.                     Console.WriteLine("\t -->> Rotando a la Derecha Nodo [{0}] Balance -> {1}", nodito.Dato, getBalance(nodito));
  152.                     rotarDerecha(nodito);
  153.                 }
  154.                 else if (leftBalance == -1 || leftBalance == 0)
  155.                 {
  156.                     Console.WriteLine("\t -->> Rotando a la Derecha Nodo [{0}] Balance -> {1}", nodito.Dato, getBalance(nodito));
  157.                     rotarDerecha(nodito);
  158.                 }
  159.             }
  160.         }
  161.  
  162.         private void rotarIzquierda(Nodo root)
  163.         {
  164.             if (root == null)
  165.                 return;
  166.  
  167.             Nodo pivote = root.NodoDerecho;
  168.  
  169.             if (pivote == null)
  170.                 return;
  171.             else
  172.             {
  173.                 Nodo padreRoot = root.Padre;
  174.                 bool esNodoIzquierdo = (padreRoot != null) && padreRoot.NodoIzquierdo == root;
  175.                 bool xd = root.Tree.Root == root;
  176.  
  177.                 //Rotando
  178.                 root.NodoDerecho = pivote.NodoIzquierdo;
  179.                 pivote.NodoIzquierdo = root;
  180.  
  181.                 //Actualizando padre
  182.                 root.Padre = pivote;
  183.                 pivote.Padre = padreRoot;
  184.  
  185.                 if (root.NodoDerecho != null)
  186.                     root.NodoDerecho.Padre = root;
  187.  
  188.                 if (xd)
  189.                     pivote.Tree.Root = pivote;
  190.  
  191.                 if (esNodoIzquierdo)
  192.                     padreRoot.NodoIzquierdo = pivote;
  193.                 else
  194.                     if (padreRoot != null)
  195.                         padreRoot.NodoDerecho = pivote;
  196.             }
  197.         }
  198.  
  199.         private void rotarDerecha(Nodo root)
  200.         {
  201.             if (root == null)
  202.                 return;
  203.  
  204.             Nodo pivote = root.NodoIzquierdo;
  205.  
  206.             if (pivote == null)
  207.                 return;
  208.             else
  209.             {
  210.                 Nodo padreRoot = root.Padre;
  211.                 bool esNodoIzquierdo = (padreRoot != null) && padreRoot.NodoIzquierdo == root;
  212.                 bool xd = root.Tree.Root == root;
  213.  
  214.                 //Rotando
  215.                 root.NodoIzquierdo = pivote.NodoDerecho;
  216.                 pivote.NodoDerecho = root;
  217.  
  218.                 //Actualizando padre
  219.                 root.Padre = pivote;
  220.                 pivote.Padre = padreRoot;
  221.  
  222.                 if (root.NodoIzquierdo != null)
  223.                     root.NodoIzquierdo.Padre = root;
  224.  
  225.                 if (xd)
  226.                     pivote.Tree.Root = pivote;
  227.  
  228.                 if (esNodoIzquierdo)
  229.                     padreRoot.NodoIzquierdo = pivote;
  230.                 else
  231.                     if (padreRoot != null)
  232.                         padreRoot.NodoDerecho = pivote;
  233.             }
  234.         }
  235.  
  236.         private int getAltura(Nodo nodoActual)
  237.         {
  238.             if (nodoActual == null)
  239.                 return 0;
  240.             else
  241.                 return 1 + Math.Max(getAltura(nodoActual.NodoIzquierdo), getAltura(nodoActual.NodoDerecho));
  242.         }
  243.  
  244.         private int getBalance(Nodo root)
  245.         {
  246.             return this.getAltura(root.NodoDerecho) - this.getAltura(root.NodoIzquierdo);
  247.         }
  248.  
  249.         public void aMostrarEstructura(int index)
  250.         {
  251.             if (root == null)
  252.             {
  253.                 Console.WriteLine("NO se puede visualizar la estructura...");
  254.                 return;
  255.             }
  256.  
  257.             Console.WriteLine("\tNodo Raiz      -->> {0}", this.root.Dato);
  258.             Console.WriteLine();
  259.             mostrarPreInPostOrden(this.root, index);
  260.             return;
  261.         }
  262.  
  263.         private void mostrarNodoInfo(Nodo nodito)
  264.         {
  265.             if (nodito == null)
  266.             {
  267.                 Console.WriteLine("No existe el nodo en la estructura!");
  268.                 return;
  269.             }
  270.             Console.WriteLine("\tNODO ACTUAL---->>> {0}", nodito.Dato);
  271.             Console.WriteLine("\tFact. Equilibrio-> {0}", getBalance(nodito));
  272.             Console.WriteLine("\tAltura del Nodo--> {0}", getAltura(nodito));
  273.             Console.Write("\tPunteros:\t\t");
  274.             if (nodito.NodoIzquierdo == null)
  275.             {
  276.                 Console.Write("[X]\t<---");
  277.             }
  278.             else
  279.             {
  280.                 Console.Write("{0}\t<---", nodito.NodoIzquierdo.Dato);
  281.             }
  282.  
  283.             Console.Write("\t[{0}]\t", nodito.Dato);
  284.             if (nodito.NodoDerecho == null)
  285.             {
  286.                 Console.WriteLine("--->\t[X]");
  287.             }
  288.             else
  289.             {
  290.                 Console.WriteLine("--->\t{0}", nodito.NodoDerecho.Dato);
  291.             }
  292.             Console.WriteLine();
  293.         }
  294.  
  295.         private void mostrarPreInPostOrden(Nodo nActual, int index)
  296.         {
  297.             if (nActual == null) return;
  298.             switch (index)
  299.             {
  300.                 case 0: //preOrden();
  301.                     mostrarNodoInfo(nActual);
  302.                     mostrarPreInPostOrden(nActual.NodoIzquierdo, index);
  303.                     mostrarPreInPostOrden(nActual.NodoDerecho, index);
  304.                     break;
  305.                 case 1: //inOrden;
  306.                     mostrarPreInPostOrden(nActual.NodoIzquierdo, index);
  307.                     mostrarNodoInfo(nActual);
  308.                     mostrarPreInPostOrden(nActual.NodoDerecho, index);
  309.                     break;
  310.                 case 2: //postOrden;
  311.                     mostrarPreInPostOrden(nActual.NodoIzquierdo, index);
  312.                     mostrarPreInPostOrden(nActual.NodoDerecho, index);
  313.                     mostrarNodoInfo(nActual);
  314.                     break;
  315.             }
  316.             return;
  317.         }
  318.  
  319.     }

4.- Y por ultimo la clase "Program.sc".

Clic para ver Texto Plano
C#:
  1. static void Main(string[] args)
  2.         {
  3.             Arbol avl = new Arbol();
  4.             Console.Title = "Arbol AVL : Mikiman";
  5.             int op;
  6.             do
  7.             {
  8.                 try
  9.                 {
  10.                     Console.Clear();
  11.                     Console.WriteLine("==============================");
  12.                     Console.WriteLine("           Arbol AVL          ");
  13.                     Console.WriteLine("------------------------------");
  14.                     Console.WriteLine("[1] - Ingresar Varios Nodos (Parsing de Numeros)");
  15.                     Console.WriteLine("[2] - Insertar Nodo (Uno por Uno)");
  16.                     Console.WriteLine("[3] - Recorrido preOrden");
  17.                     Console.WriteLine("[4] - Recorrido inOrden");
  18.                     Console.WriteLine("[5] - Recorrido postOrden");
  19.                     if (avl.Root != null)
  20.                         Console.WriteLine("[6] - Limpiar Arbol");
  21.                     Console.WriteLine("[0] - Salir");
  22.                     Console.WriteLine("------------------------------");
  23.                     Console.Write("opcion : ");
  24.                     op = int.Parse(Console.ReadLine());
  25.                     Console.WriteLine("------------------------------");
  26.                     switch (op)
  27.                     {
  28.                         case 1:
  29.                             Console.Write("Ingrese Numeros Separados por Espacios: ");
  30.                             avl.aInsertarVariosNodos(Console.ReadLine());
  31.                             Console.WriteLine("\nNodos Insertados...");
  32.                             Console.ReadLine();
  33.                             break;
  34.                         case 2:
  35.                             avl.aInsertarNodos();
  36.                             break;
  37.                         case 3:
  38.                             avl.aMostrarEstructura(0);
  39.                             Console.ReadLine();
  40.                             break;
  41.                         case 4:
  42.                             avl.aMostrarEstructura(1);
  43.                             Console.ReadLine();
  44.                             break;
  45.                         case 5:
  46.                             avl.aMostrarEstructura(2);
  47.                             Console.ReadLine();
  48.                             break;
  49.                         case 6:
  50.                             avl.limpiar();
  51.                             Console.WriteLine("Arbol Limpiado");
  52.                             Console.ReadLine();
  53.                             break;
  54.                         case 0:
  55.                             string chao = "\n\tMikiman  -  Con Estilo y Elegancia  ..........";
  56.                             Console.Write("\t\t");
  57.                             for (int x = 0; x <chao.Length; x++)
  58.                             {
  59.                                 Console.Write(chao.Substring(x, 1));
  60.                                 Console.Beep(1760, 60);
  61.                             }
  62.                             Console.WriteLine();
  63.                             break;
  64.                     }
  65.                 }
  66.                 catch (Exception ex)
  67.                 {
  68.                     Console.WriteLine(ex.Message);
  69.                     Console.ReadLine();
  70.                     op = 10;
  71.                 }
  72.             } while (op != 0);
  73.         }

Cualquier duda, queja o sugerencia puedes comentarla y yo tratare de responder lo mas pronto posible.

en: Programacion
Comentarios (4)