Leccion 5.2 Arboles AVL

8/8/2019 Leccion 5.2 Arboles AVL

1/14

Leccion 5.2 ARBOLES AVL

El Arbol en Monton consisten en el ordenamiento de un conjunto de Elemento en un solo arreglo.

Trabajaremos sobre la siguientes Operaciones en este Tema:

1. Insercin2. Bsqueda3. Eliminacin4. Recorrido (Ordenado)

Insercin

Definicin:

El Concepto de Insercin ya es familiar para nosotros y sabemos que para realizar el mismo no resultacomplejo el procedimiento.

Pero en los rboles en Montn es uno de los Mtodos ms largos para efectuarlo.

Detalle:

Bsicamente lo que hace estos Algoritmos es la Insercin Ordenada. Primero comparan si es posibleinsertar algn Elemento al Arreglo, si es posible hacerlo Ingresa el Elemento a la Ultima posicin.

Despus bsicamente acomoda el Arreglo con el Mtodo de la Burbuja llamando a otra serie deMtodos.

Algoritmos:

Insertar(Arbol, N, Elemento)

Si N a

N -> N + 1OrdMon(Arbol, N)

Salir

//Fin de la condicin//

Imprimir "rbol Lleno..."

ESTRUCTURAS DE DATOS LECCION 5.2 ARBOLES AVL Pgina 1


2/14

Salir

OrdMon(Arbol, Total)

ConstMon(Arbol, Total)

Mientras Total > 1

Total -> Total - 1

Burbuja(0, Total)

RecMon(Total, 0)

//Fin del ciclo//

Salir

ConstMon(Arbol, Total)

v -> (Total/2) - 1

Mientras v 0

RecMon(Arbol, Total, v)

v -> v - 1

//Fin del ciclo//

Salir

----

RecMon(Arbol, Total, v)

w -> 2*v+1

Mientras w < Total

Si (w+1) < Total

Si Arbol[w+1] > Arbol[w]

w++


Fin de la condicin

Si Arbol[v] Arbol[w]

Salir




3/14

Burbuja(Arbol, v, w)

v -> w

w -> 2*v+1

//Fin del ciclo//

Salir

----

Burbuja(Arbol, v, w)

t -> Arbol[v]

Arbol[v] -> Arbol[w]

Arbol[w] -> t

Salir

Diagrama:

Corrida:

http://www.programacionfacil.com/_detail/estructura_de_datos/image597.jpg?id=estructura_de_datos%3Aarbol_monton


4/14

Bsqueda

Definicin:

El Concepto de Bsqueda es sencillo, simplemente es un mtodo de bsqueda lineal. Existen 3 posibleresultados:

1. Que el rbol este Vaci y no se puede realizar la bsqueda.2. Que el Elemento sea encuentre en el rbol3. Que el Elemento no este dentro del rbol

Detalle:

Se manda al Mtodo Bsqueda el Dato que se desea buscar, se acomoda el rbol en Orden en caso que

no estuviera Ordenado y despus compara con cada uno de los datos.

Algoritmos:

**Busqueda(Arbol, N, Elemento)**

Si N 0

OrdMon(Arbol, N)

i ->

Mientras i < N;i++)

Si Arbol[i] = Elemento

Imprimir "Elemento Encontrado..."

Salir




5/14

i -> i + 1

//Fin del ciclo//

Imprimir "El Elemento no esta en el rbol..."

Salir


Imprimir "rbol Vaci..."

Salir

Diagrama:

Corrida:



6/14


7/14

t -> Arbol[i]

Arbol[i] -> Arbol[j]

Arbol[j] -> t

j -> j + 1

//Fin del ciclo//

N -> n - 1

Imprimir "Elemento Eliminado..."

Salir


i -> i + 1

//Fin del ciclo//

Fin de la condicin

Imprimir "Arbol Vacio... Imposible Eliminar..."

Salir

Diagrama:

Corrida:



8/14

Recorrido (Ordenado)

Definicin:

El Recorrido simplemente ira desplegando cada uno de los Elementos del rbol. Solo existen 2 posiblescasos:

1. Que el rbol este Vaci y no se pueda recorrer2. El rbol tenga Elementos para desplegar

Detalle:

Comparamos para comprobar que el rbol tiene Elementos dentro de el, de ser as Desplegamos cadauno de ellos. De otra manera Desplegamos rbol Vaci.

Algoritmo:

Recorrido(Arbol, N)

Si N 0

i ->

Mientras i < N

Imprimir Arbol[i]

i -> i + 1

//Fin del ciclo//

Salir


Imprimir "Arbol Vacio..."



9/14

Salir

Corrida:

Programa Click Here:

#include

#include

class Arbol_Monton

{

private:

int Arbol[25];

int N;

public:

Arbol_Monton()

{

for(int i=0;i


10/14

if(N


11/14

}

}

cout


12/14

}

}

void ConstMon(int n)

{

for(int v=n/2-1;v>=0;v--)

RecMon(n,v);

}

void RecMon(int n,int v)

{

int w=2*v+1;

while(w=Arbol[w])

return;

Burbuja(v,w);

v=w;

w=2*v+1;

}

}

void Burbuja(int i,int j)

{

int t=Arbol[i];

Arbol[i]=Arbol[j];

Arbol[j]=t;

}

void Recorrido()



13/14

{

if(N!=0)

{

for(int i=0;i


14/14

cin>>res;

tec.Busqueda(res);

break;

case 3:

cout

Documents

Leccion 5.2 Arboles AVL