Embed Size (px)
Citation preview
UNIVERSIDAD TÉCNICA DE MANABÍ
Ext. En El Carmen
INTEGRANTES:
Mite SandraFerrìn Jenny
TUTORA:ING. Roció Mendoza
MATERIA Estructura de Datos
4to. Semestre de Ingeniería en Sistema
TEMAS
*Arboles Binarios*listas Abiertas y Cerradas
- Inserción- Recorrido- Eliminación
*Pilas - Concepto- Inserción- Recorrido- Eliminación
* Colas- Inserción- Recorrido- Eliminación
*Manejo de Memoria Estática* Manejo de Memoria Dinámica* Arboles Definicial * tipos de Recorrido
-Orden - In-Orden- Post-Orden
* Que son Arboles AVL* Arboles Equilibrados AVL
Árboles binarios
Un árbol binario en un árbol en
el cual cada nodo puede tener
como máximo dos hijos.
Recursivamente un árbol
binario puede definirse como:
un árbol vacío, o un nodo raíz
con un subárbol izquierdo y un
subárbol derecho.
Raíz
Sub árbol Izquierdo
Sub árbol Derecho
Un árbol es una estructura de datos formada por nodos los cuales están conectados por aristas.
Es una estructura de datos jerárquica
La relación entre los elementos es de uno a muchos.
A
B C D
E FG H I
nodos
Aristas
•Un árbol puede estar vacío; es decir no contener ningún nodo.
• Raíz: es el nodo que está al tope del árbol. Un árbol
solo tiene una raíz.
A
B C D
E FG H I
raíz
Conceptos Básicos
Un conjunto de nodos y aristas se define como un árbol y solo si existe un único camino desde la raíz hasta cada uno de sus nodos.
A
B C D
E FG H I
•Padre: En un árbol toda rama va de un nodo n1 a unnodo n2, se dice que n1 es padre de n2.
Ejemplo: C es padre de E y de F, D es padre de G, de Hy de I.
• Hijo: todo nodo puede tener mas de una arista que lolleva a otro nodo por debajo de él. Estos nodos que seencuentran por debajo de un nodo dado se llamanhijos. Ejemplo: E es hijo de C, B es hijo de A, H es hijode D
A
B C D
E FG H I
padres
hijos
•Hojas: son aquellos nodos que no tienen hijos. En unarbol solo puede haber una raíz pero pueden habermuchas hojas. Ejemplo: B,E,F,G,H,I son hojas.
• Subárbol: Cualquier nodo se puede considerar comola raíz de un subárbol.
•Nivel: el nivel de un nodo es el numero degeneraciones que hay desde la raíz hasta él.
El nivel de la raíz es cero.
• Profundidad o altura: es la longitud del camino maslargo desde la raíz hasta una hoja.
La profundidad de este árbol es 2. La raíz tieneprofundidad 0.
A
B C D
E FG H I
Nivel 0
Nivel 1
Nivel 2
LISTAS ABIERTAS
La forma más simple de estructura dinámica es lalista abierta. En esta forma los nodos se organizande modo que cada uno apunta al siguiente, y elúltimo no apunta a nada, es decir, el puntero delnodo siguiente vale NULL.
INSERCION
Este es, evidentemente, el caso más sencillo.Partiremos de que ya tenemos el nodo a insertary, por supuesto un puntero que apunte a él, ademásel puntero a la lista valdrá NULL:
INSERCION UN ELEMENTO EN LA ÚLTIMA POSICIÓN DE UNA LISTA
EJEMPLO:
LISTAS CIRCULARES
Una lista circular es una lineal, en la que el ultimo elemento enlaza con el
primero. Entonces es posible acceder a cualquier elemento de la lista
desde cualquier punto dado. Las operaciones sobre una lista circular
resultan mas sencillas, ya que se evitan casos especiales.
Cuando recorremos una lista circular, diremos que hemos llegado al final
de la misma, cuando nos encontramos de nuevo en el punto de partida;
suponiendo, desde luego, que el punto de partida se guarda de alguna
manera en la lista, por ejemplo
Con un puntero fijo al mismo.
+2
+ 3 1 0 + 1 3 0
+++4+
+ 0 4 0 - 0 0 1
00+4 -1 0
Listas CircularComo ejemplo de utilización de listas circulares, realizaremos la suma de ecuaciones algebraicas o polinómicas de las variables x, y, z.. Por ejemplo:
2x³y + 4xy³- y⁴ más 2xy³-xy
Cada polinomio será representado como una lista en la que cada elemento
representa un término nulo, como se indica a continuación:
± A B C SIGUIENTE
COEFICIENTE
FUNCIONES
1. Leer PolinomioLeer_ polinomio(&polP);
Leer_ polinomio(&polQ);
2. InicializarInicializar(&polP);
Inicializar(&polQ);
3. CompararComparar(&polP ,&polQ);
4. Eliminar TérminosEliminar_Término(PolQ);
5. Escribir Polinomios Escribir_polinomio(polQ);
PILASCREAR: Se crea la pila vacía
APILAR: Se añade un elemento
a la pila (push)
DESAPILAR: Se elimina el
elemento frontal de la pila(pop)
CIMA: Devuelve el elemento
que esta en la cima de la pila(top
o peek)
VACIA: Devuelve cierto si la
pila esta vacía o falso en caso
contrario
La particularidad de unaestructura de datos de cola esel hecho de que sólopodemos acceder al primer yal último elemento de laestructura. Así mismo, loselementos sólo se puedeneliminar por el principio ysólo se pueden añadir por elfinal de la cola.
Ejemplos de colas en la vidareal serían: personascomprando en unsupermercado, esperandopara entrar a ver un partidode béisbol, esperando en elcine para ver unapelícula, una pequeñapeluquería, etc. La ideaesencial es que son todoslíneas de espera.
15 20 9 18 19
15 20 9 18 19 13
20 9 18 19 13
1.- Ejemplo de la cola
2.-vamos a insertar el 13 en la cola
3.-Sacamos al frente de la cola
COLAS
MEMORIA ESTATICA
La forma más fácil de almacenar el contenido de una variable enmemoria en tiempo de ejecución es en memoria estática opermanente a lo largo de toda la ejecución del programa.
La asignación de memoria puede hacerse en tiempo de compilacióny los objetos están vigentes desde que comienza la ejecución delprograma hasta que termina.
EJEMPLO:
liberación de Memoria Estática
4
8
14
20
4
8
6
8
20
4
20
4
8
14
20
8
6
8
MANEJO DE UNA MEMORIA ESTÀTICA
VENTAJAS DESVENTAJAS
En algunos casos se pueden desperdiciar
memoria
Es una memoria fija
Fácil de almacenar datos
Desperdicia espacio liberado
En otros casos pueden que ser que los datos sea
grande el espacio asignado.
Es secuencial
Es una sola casilla
Desperdicia espacio liberado
MEMORIA DINAMICALa memoria dinámica es un espacio de almacenamiento que sesolicita en tiempo de ejecución. De esa manera, a medida que elproceso va necesitando espacio para más líneas, va solicitando másmemoria al sistema operativo para guardarlas.
Mejor ajuste: Busca asignar el espacio más pequeño de los espacioscon capacidad suficiente.
Peor ajuste: Asigna el hueco más grande. Una vez más, se debe debuscar en toda la tabla de huecos a menos que esté organizada portamaño
EJEMPLO
Liberación De Memoria Estática
6
8
14
20
4
20
4
8
14
20
2
8
14
46
MANEJO DE UNA MEMORIA ESTÀTICA
VENTAJAS DESVENTAJAS
En algunos casos se pueden desperdiciar
memoria
No es secuencial
Utiliza un puntero
Desperdicia espacio liberado
En otros casos pueden que ser que los datos sea
grande el espacio asignado.
Debe ser refrescada
Para ubicación de un registro
Desperdicia espacio liberado
Una función que asigna a Malloc
TIPOS DE RRECORRIDO
Pre-order: Procesar nodoProcesar árbol izquierdoProcesar árbol derecho
In-order:Procesar árbol izquierdoProcesar nodoProcesar árbol derecho
Post-order:Procesar árbol izquierdoProcesar árbol derechoProcesar nodo
A
B C
F GD E
Pre-orden: A, B, D, E, C, F, GIn-orden: D, B, E, A, F, C, G
Post-orden: D, E, B, F, G, C, A
ÁRBOLES EQUILIBRADOS AVL.
Un árbol AVL (llamado así por las iníciales de susinventores: Adelson-Velskii y Landis) es un árbolbinario de búsqueda en el que para cada nodo, lasalturas de sus subárboles izquierdo y derecho nodifieren en más de 1.
Los AVL son también ABB, de modo que mantienentodas las operaciones que poseen éstos. Las nuevasoperaciones son las de equilibrar el árbol, pero eso sehace como parte de las operaciones de insertado yborrado.
Ejemplos de arboles equilibrados
ESTE ES UN ARBOL AVL
NO ES ÀRBOL AVL
Inserción externa por la derecha.
Si se inserta nodo F, en la rama externa más larga delsubárbol derecho: La relación de orden del árbol binarioes: A<B<C<D<E<F
Inserción interna por la derecha.
Si se inserta nodo D, en la rama interna más largadel subárbol derecho.
Con orden: A<B<C<D<E<F
Veamos ahora la forma en que puede afectar una inserción en unárbol AVL y la forma en que deberíamos reorganizar los nodos demanera que siga equilibrado. Consideremos el esquema general de lasiguiente figura, supongamos que la inserción ha provocado que elsubárbol que cuelga de Ai pasa a tener una altura 2 unidades mayorque el subárbol que cuelga de Ad .
¿Qué operaciones son necesarias para que el nodo r tenga 2subárboles que cumplan la propiedad de árboles AVL?.
La inserción se ha realizado en el árbol A. La operación a realizar esla de una rotación simple a la derecha sobre el nodo r resultando el
árbol mostrado en la siguiente figura.
La inserción se ha realizado en el árbol B. (supongamos tiene raízb, subárbol izquierdo B1 y subárbol derecho B2). La operación arealizar es la rotación doble izquierda-derecha la cual es equivalente arealizar una rotación simple a la izquierda sobre el nodo Ai ydespués una rotación simple a la derecha sobre el nodo r (portanto, el árbol B queda dividido). El resultado se muestra en la figurasiguiente.
