Unidad 5: Arboles en Monton
Definición:
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:
- Inserción
- Búsqueda
- Eliminación
- Recorrido (Ordenado)
Inserción
Definición:
El Concepto de Inserción ya es familiar para nosotros y sabemos que para realizar el mismo no resulta complejo el procedimiento.
Pero en los Árboles en Montón es uno de los Métodos más largos para efectuarlo.
Detalle:
Básicamente lo que hace estos Algoritmos es la Inserción Ordenada. Primero comparan si es posible insertar algún Elemento al Arreglo, si es posible hacerlo Ingresa el Elemento a la Ultima posición.
Después básicamente acomoda el Arreglo con el Método de la Burbuja llamando a otra serie de Métodos.
Algoritmos:
Insertar(Arbol, N, Elemento) Si N<25 Arbol[N] -> a N -> N + 1 OrdMon(Arbol, N) Salir //Fin de la condición// Imprimir "Árbol Lleno..." 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 condición// Fin de la condición Si Arbol[v] ≥ Arbol[w] Salir //Fin de la condición// 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:
Búsqueda
Definición:
El Concepto de Búsqueda es sencillo, simplemente es un método de búsqueda lineal. Existen 3 posible resultados:
- Que el Árbol este Vació y no se puede realizar la búsqueda.
- Que el Elemento sea encuentre en el Árbol
- Que el Elemento no este dentro del Árbol
Detalle:
Se manda al Método Búsqueda el Dato que se desea buscar, se acomoda el Árbol en Orden en caso que no estuviera Ordenado y después 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 //Fin de la condición// i -> i + 1 //Fin del ciclo// Imprimir "El Elemento no esta en el Árbol..." Salir //Fin de la condición// Imprimir "Árbol Vació..." Salir
Diagrama:
Corrida:
Eliminación
Definición:
El Concepto de Eliminación consiste en la búsqueda de un Elemento y sacarlo del Arreglo. Existen 3 casos Diferentes;
- Que el Árbol este Vació y no se puede realizar la eliminación
- Que el Elemento sea encuentre en el Árbol y sea eliminado
- Que el Elemento no este dentro del Árbol por lo tanto no se elimina
Detalle:
Vemos si el Árbol tiene Elementos insertados en el, de otra forma será imposible realizar la Eliminación ya que esta Vació. Después si el Árbol tiene Elementos lo ordenamos y hacemos un búsqueda lineal para encontrar el dato. Después usamos el método de la Burbuja para dejar el Elemento Eliminado hasta el final y le Restamos a N un Elemento.
Algoritmo:
Eliminar(Arbol, N, Elemento) Si N ≠ 0 OrdMon(Arbol, N) i -> Mientras I < N Si Arbol[i] = Elemento j -> i + 1 Mientras j < N t -> Arbol[i] Arbol[i] -> Arbol[j] Arbol[j] -> t j -> j + 1 //Fin del ciclo// N -> n - 1 Imprimir "Elemento Eliminado..." Salir //Fin de la condición// i -> i + 1 //Fin del ciclo// Fin de la condición Imprimir "Arbol Vacio... Imposible Eliminar..." Salir
Diagrama:
Corrida:
Recorrido (Ordenado)
Definición:
El Recorrido simplemente ira desplegando cada uno de los Elementos del Árbol. Solo existen 2 posibles casos:
- Que el Árbol este Vació y no se pueda recorrer
- El Árbol tenga Elementos para desplegar
Detalle:
Comparamos para comprobar que el Árbol tiene Elementos dentro de el, de ser así Desplegamos cada uno 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 //Fin de la condición// Imprimir "Arbol Vacio..." Salir
Corrida:
