Scribd
Cargar
7 vistas8 páginas

Implementación de Árbol AVL en C#

Este documento define la clase cArbolAVL que representa un árbol AVL. La clase hereda de cArbolBB y agrega un factor de equilibrio para cada nodo. Incluye métodos para rotaciones simples y dobles para mantener el árbol balanceado durante inserciones, y métodos para recorrer el árbol y verificar si contiene un elemento.

Cargado por

ramiromunoz9876
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
7 vistas8 páginas

Implementación de Árbol AVL en C#

Este documento define la clase cArbolAVL que representa un árbol AVL. La clase hereda de cArbolBB y agrega un factor de equilibrio para cada nodo. Incluye métodos para rotaciones simples y dobles para mantener el árbol balanceado durante inserciones, y métodos para recorrer el árbol y verificar si contiene un elemento.

Cargado por

ramiromunoz9876
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

using System;

using [Link];
using [Link];
using [Link];
using [Link];

namespace AppArbolesAVL01
{
public class cArbolAVL : cArbolBB
{
#region *********************** Atributos *************************
private int aFE; // -- Factor de equilibrio, necesario para determinar si un nodo está o no balanceado
#endregion Atributos

#region ====================== Constructores =======================


/* -------------------------------------------------------------- */
public cArbolAVL() : base()
{
aFE = 0;
}

/* -------------------------------------------------------------- */
public cArbolAVL(Object pRaiz) : base(pRaiz)
{
aFE = 0;
}

/* -------------------------------------------------------------- */
public cArbolAVL(cArbolAVL pSubArbolIzq, Object pRaiz, cArbolAVL pSubArbolDer)
: base(pSubArbolIzq, pRaiz, pSubArbolDer)
{
aFE = 0;
}

/* -------------------------------------------------------------- */
public static cArbolAVL CrearAVL()
{
return new cArbolAVL();
}

/* -------------------------------------------------------------- */
public static cArbolAVL CrearAVL(Object pRaiz)
{
return new cArbolAVL(pRaiz);
}

/* -------------------------------------------------------------- */
public static cArbolAVL CrearAVL(cArbolAVL pSubArbolIzq, Object pRaiz, cArbolAVL pSubArbolDer)
{
return new cArbolAVL(pSubArbolIzq, pRaiz, pSubArbolDer);
}
#endregion Constructores

#region ********************* Propiedades ***********************


/* ---------------------------------------------------------- */
public int FE
{
get
{
return aFE;
}
set
{
aFE = value;
}
}

#endregion ********************* Propiedades ***********************

#region ==================== Metodos ======================

/* -------------------------------------------------------------- */
/*
private bool EstaBalanceado()
{
int Altura1 = (SubArbolIzq==null ? 0 :1+[Link]());
int Altura2 = (SubArbolDer==null ? 0 :1+[Link]());
return ([Link](Altura1-Altura2)<2);
}
*/

/* -------------------------------------------------------------- */
protected void RotacionSimpleIzq(bool FlagFE = true)
{
// La rotación se efectuara primero creando un nuevo arbol y reordenando los enlaces de los arboles
SubArbolDer = [Link]([Link] as cArbolAVL, Raiz, SubArbolDer as cArbolAVL);
Raiz = [Link];
SubArbolIzq = [Link];
// -- Actualizar FE
if (FlagFE)
{
FE = 0; // -- El nodo donde se realizaó la rotación, está balanceado
(SubArbolDer as cArbolAVL).FE = 0; // -- El nodo rotado también está balanceado
}
}

/* -------------------------------------------------------------- */
protected void RotacionDobleIzq(Object Elemento)
{
// -- Determinar condicones para actualizar FE
bool FlagHoja = [Link]();
bool FlagIzqDerIzq = false;
if (!FlagHoja)
FlagIzqDerIzq = ([Link]().CompareTo([Link]()) < 0);
// -- Efectuar rotaciones
((cArbolAVL)SubArbolIzq).RotacionSimpleDer(false);
RotacionSimpleIzq(false);
// -- Actualizar factor de equilibrio
FE = 0; // -- El nodo donde se efectúa la rotación está balanceado
if (FlagHoja)
(SubArbolDer as cArbolAVL).FE = 0;
else if (FlagIzqDerIzq)
{
(SubArbolIzq as cArbolAVL).FE = 0;
(SubArbolDer as cArbolAVL).FE = 1;
}
else
{
(SubArbolIzq as cArbolAVL).FE = -1;
(SubArbolDer as cArbolAVL).FE = 0;
}
}

/* -------------------------------------------------------------- */
protected void RotacionSimpleDer(bool FlagFE = true)
{
// La rotación se efectuara primero creando un nuevo arbol y reordenando los enlaces de los arboles
SubArbolIzq = [Link](SubArbolIzq as cArbolAVL, Raiz, [Link] as cArbolAVL);
Raiz = [Link];
aFE = 0;
SubArbolDer = [Link];
// -- Actualizar FE
if (FlagFE)
{
FE = 0; // -- El nodo donde se realizaó la rotación, está balanceado
(SubArbolIzq as cArbolAVL).FE = 0; // -- El nodo rotado también está balanceado
}
}

/* -------------------------------------------------------------- */
protected void RotacionDobleDer(Object Elemento)
{
// -- Determinar condicones para actualizar FE
bool FlagHoja = [Link]();
bool FlagDerIzqDer = false;
if (!FlagHoja)
FlagDerIzqDer = ([Link]().CompareTo([Link]()) > 0);
// -- Efectuar rotaciones
((cArbolAVL)SubArbolDer).RotacionSimpleIzq(false);
RotacionSimpleDer(false);
// -- Actualizar factor de equilibrio
FE = 0; // -- El nodo donde se efectúa la rotación está balanceado
if (FlagHoja)
(SubArbolIzq as cArbolAVL).FE = 0;
else if (FlagDerIzqDer)
{
(SubArbolIzq as cArbolAVL).FE = -1;
(SubArbolDer as cArbolAVL).FE = 0;
}
else
{
(SubArbolIzq as cArbolAVL).FE = 0;
(SubArbolDer as cArbolAVL).FE = 1;
}
}

/* -------------------------------------------------------------- */
public int Agregar(object Elemento)
{
int Ind = 0;
if (Raiz == null)
Raiz = Elemento;
else
if ([Link]().CompareTo([Link]()) < 0)
{ // Agregar el nuevo elemento como hijo Izq
if (SubArbolIzq == null)
{
SubArbolIzq = [Link](null, Elemento, null);
aFE--;
Ind = 1;
}
else
{
Ind = (SubArbolIzq as cArbolAVL).Agregar(Elemento);
if (Ind != 0)
{
aFE -= Ind;
// Balancear arbol si esta desbalanceado
if (aFE == -2) // Si el Factor de equilibrio es -2 entonces hay desbalance
{
if ([Link]().CompareTo([Link]()) < 0)
RotacionSimpleIzq();
else
RotacionDobleIzq(Elemento);
Ind = 0;
}
}
}
}
else
{ // Agregar el nuevo elemento como hijo Der
if (SubArbolDer == null)
{
SubArbolDer = [Link](null, Elemento, null);
aFE++;
Ind = 1;
}
else
{
Ind = (SubArbolDer as cArbolAVL).Agregar(Elemento);
if (Ind != 0)
{
aFE++;
// Balancear arbol si esta desbalanceado
if (aFE == 2)
{
if ([Link]().CompareTo([Link]()) > 0)
RotacionSimpleDer();
else
RotacionDobleDer(Elemento);
Ind = 0;
}
}
}
}
return Ind;
}

/* -------------------------------------------------------------- */
public void PreOrdenFE()
{
if (Raiz != null)
{
// ----- Procesar la raiz
[Link]([Link]() + "- " + [Link]());
// ----- Procesar hijo Izq
if (SubArbolIzq != null)
(SubArbolIzq as cArbolAVL).PreOrdenFE();
// ----- Procesar hijo Der
if (SubArbolDer != null)
(SubArbolDer as cArbolAVL).PreOrdenFE();
}
}

//contiene

//metodo inorden
public void InOrdenFE()
{
if (Raiz != null)
{
// ----- Procesar hijo Izq
if (SubArbolIzq != null)
(SubArbolIzq as cArbolAVL).InOrdenFE();
// ----- Procesar la raiz
[Link]([Link]() + "- " + [Link]());
// ----- Procesar hijo Der
if (SubArbolDer != null)
(SubArbolDer as cArbolAVL).InOrdenFE();
}
}
//metodo posorden
public void PosOrdenFE()
{
if (Raiz != null)
{
// ----- Procesar hijo Izq
if (SubArbolIzq != null)
(SubArbolIzq as cArbolAVL).PosOrdenFE();
// ----- Procesar hijo Der
if (SubArbolDer != null)
(SubArbolDer as cArbolAVL).PosOrdenFE();
// ----- Procesar la raiz
[Link]([Link]() + "- " + [Link]());
}
}
#endregion Metodos
//metodo para mostrar el arbol en consola con su grafico en forma de grafo
public new void VistaArbol(string prefijo = "", bool esIzquierdo = false)
{
if (Raiz != null)
{
string valor = [Link]();
[Link](prefijo + (esIzquierdo ? "└── " : "├── ") + valor);

if (SubArbolIzq != null || SubArbolDer != null)


{
var nuevoPrefijo = prefijo + (esIzquierdo ? " " : "│ ");
(SubArbolIzq as cArbolAVL)?.VistaArbol(nuevoPrefijo, true);
(SubArbolDer as cArbolAVL)?.VistaArbol(nuevoPrefijo, false);
}
}
}

//contiene
public bool Contiene(object elemento)
{
// Verificar si el elemento coincide con la raíz
if (Raiz != null && [Link](elemento))
{
return true;
}

// Verificar en el subárbol izquierdo si es un cArbolAVL


if (SubArbolIzq is cArbolAVL && ((cArbolAVL)SubArbolIzq).Contiene(elemento))
{
return true;
}

// Verificar en el subárbol derecho si es un cArbolAVL


if (SubArbolDer is cArbolAVL && ((cArbolAVL)SubArbolDer).Contiene(elemento))
{
return true;
}

// El elemento no se encuentra en este subárbol


return false;
}

//fusionar 2 arboles avl


public static cArbolAVL FusionarArbolesAVL(cArbolAVL arbol1, cArbolAVL arbol2)
{
cArbolAVL arbolFusionado = new cArbolAVL();

// Función auxiliar para recorrer el árbol AVL y agregar nodos únicos al árbol fusionado
void FusionarAVLAuxiliar(cArbolAVL arbol, cArbolAVL arbolFusionado)
{
if (arbol != null)
{
// Agregar el nodo de la raíz al árbol fusionado si no existe
if (![Link]([Link]))
{
[Link]([Link]);
}

// Fusionar los subárboles AVL


FusionarAVLAuxiliar([Link] as cArbolAVL, arbolFusionado);
FusionarAVLAuxiliar([Link] as cArbolAVL, arbolFusionado);

}
}

// Fusionar los árboles AVL


FusionarAVLAuxiliar(arbol1, arbolFusionado);
FusionarAVLAuxiliar(arbol2, arbolFusionado);

return arbolFusionado;
}
}
}

using System;
using [Link];
using [Link];
using [Link];
using [Link];
using [Link];

using System;

namespace AppArbolesAVL01
{
class Program
{
static void Main(string[] args)
{
// Crear los árboles AVL
cArbolAVL arbol1 = new cArbolAVL();
[Link](5);
[Link](3);
[Link](7);

cArbolAVL arbol2 = new cArbolAVL();


[Link](5);
[Link](6);
[Link](8);

// Fusionar los árboles AVL


cArbolAVL arbolFusionado = [Link](arbol1, arbol2);

// Mostrar el árbol fusionado


[Link]("Árbol fusionado:");
[Link]();
}
}
}

También podría gustarte