ARBOL EN PROGRAMACION
Estructura que organiza sus elementos formando jerarquías: PADRES E HIJOS
Los elementos de un árbol se llaman nodos
Camino: Secuencia de nodos conectados dentro de un árbol
Longitud del camino: es el numero de nodos menos 1 en un camino
Altura del árbol: es el nivel mas alto del árbol
Un árbol con un solo nodo tiene altura 1
Nivel(profundidad) de un nodo: es el numero de nodos entre el nodo y la raíz.
Nivel de un árbol
Es el numero de nodos entre la raíz y el nodo mas profundo del árbol, la
altura del un árbol entonces
ARBOL BINARIO
Grado(aridad) de un nodo: es numero de hijos del nodo
Grado(aridad) de un árbol: máxima aridad de sus nodos
Tipo especial de árbol
Cada nodo no puede tener más de dos hijos
Un árbol puede ser un conjunto
Vacío, no tiene ningún nodo
O constar de tres partes:
Un nodo raíz y
Dos subárboles binarios: izquierdo y derecho
La definición de un árbol binario es recursiva
La definición global depende de si misma
Un árbol equilibrado es cuando
La diferencia de altura entre los subárboles de cualquier nodo es máximo 1
Un árbol binario equilibrado totalmente
Los subárboles izquierdo y derecho de cada nodo tienen las misma altura:
es un árbol lleno
Un árbol completo es equilibrado
Un árbol lleno es totalmente equilibrado
RECORRIDO DE UN ARBOL BINARIO
Recorrer es
Visitar todos los elementos de una estructura
Como recorrer un árbol
Hay tantos caminos, cual escoger?
Existe tres recorridos típicos
Nombrados de acuerdo a la posición de la raíz
Preorden: raíz - subarbol izq. - subarbol der.
Enorden : subarbol izq. - raíz - subarbol der.
Postorden : subarbol izq. - subarbol der. -raíz
EVALUACION DE EXPRESIONES
Ya sabemos lo de las expresiones, cierto?
InFija, operador en medio
PreFija, operador antes de dos operandos
PosFija, operador luego de dos operandos
Para evaluar una expresion dada, podriamos
Pasarla a posfija y usar solo pilas
Pasarla a posfija y usar pilas y un arbol de expresion
Los elementos en un arbol
Hasta ahora no han guardado un orden
No sirven para buscar elementos
Los arboles de busqueda
Permiten ejecutar en ellos busqueda binaria
Dado un nodo:
Todos los nodos del sub. Izq. Tienen una
clave menor que la clave de la raiz
Todos los nodos del sub. Der.
Tienen una clave mayor que la clave de la raiz
ELIMINACIÓN DE UN NODO
La operación de borrado en árboles balanceados consiste en quitar un nodo del árbol sin violar los
principios que definen a un árbol balanceado.
Para este tipo de operación se deben de tomar en cuenta los siguientes casos:
CASO 1: Si el elemento a borrar es hoja, simplemente se suprime.
CASO 2: Si el elemento a borrar tiene sólo un hijo, entonces tiene que sustituirse por él.
CASO 3: Si el elemento a borrar tiene los dos hijos, entonces tiene que sustituirse por el nodo
que se encuentra más a la izquierda en el SAD o por el nodo que se encuentra más a la derecha
en el SAI.
MEMORIA ESTATICA
La memoria estática es la que se reserva al momento de compilación antes de comenzar a ejecutarse el
programa. Los objetos son creados en ese momento y destruidos al final del programa. Mantiene la
misma de localización en memoria durante todo el transcurso del programa.
Los objetos administrados de este modo son:
Variables Static.
Variables Globales.
Miembros Static de la Clase.
Literales de cualquier tipo.
Ejemplo 1:
(Programa 13)
class CSimple
{
static void Main(string[]args)
{
int[]Numeros=new int[] {1,2,3,4,5};
for (int i=0; i<5;>
{
Console.WriteLine("{0}, ",Numeros[i]);
}
}
}
MEMORIA DINAMICA
La memoria dinámica se refiere a aquella memoria que no puede ser definida ya que no se conoce o no
se tiene idea del número de la variable a considerarse, la solución a este problema es la memoria
dinámica que permite solicitar memoria en tiempo de ejecución, por lo que cuanta más memoria se
necesite, más se solicita al sistema operativo. El sistema operativo maneja la memoria gracias al uso de
punteros, por la misma naturaleza del proceso nos impide conocer el tamaño de la memoria necesaria
en el momento de compilar.
Un dato importante es que como tal este tipo de datos se crean y se destruyen mientras se ejecuta el
programa y por lo tanto la estructura de datos se va dimensionando de forma precisa a los
requerimientos del programa, evitándonos así perder datos o desperdiciar memoria si hubiéramos
tratado de definir la cantidad de memoria a utilizar en el momento de compilar el programa.
1. ¿Considera que la memoria dinámica es más eficiente que la memoria estática?
Explique su respuesta.
Dependiendo de la cantidad de datos, si se trata de una pequeña cantidad no se notarán
grandes diferencias en cuanto a la eficiencia, pero al trabajar grandes cantidades de
datos la memoria dinámica sobresale, ya que al realizar consultas no debe de recorrer
cada uno de los datos como en la estática, solamente una sección de ellos. La memoria
estática puede ser utilizada para grandes cantidades de registros, pero al estar definida y
no utilizarla en su totalidad se estaría desaprovechando espacio en memoria; por otra
parte, una de las ventajas de la memoria dinámica es el poder liberar espacio sin uso.
2. Que diferencias puede mencionar de la memoria dinámica y la estática.
Memoria Estática Memoria Dinámica
- Se debe conocer con anticipación - El espacio en memoria se modifica
el tamaño que se requiere para su dependiendo del usuario.
utilización.
- La lógica de la memoria estática es - La memoria dinámica es difícil de
simple. implementar.
- El espacio en memoria es fijo y no - El espacio en memoria sin llenar
puede ser liberado. puede ser liberado.
- Al estar definido el espacio, se - La memoria dinámica puede alterar
tiene un control de rendimiento del el rendimiento del equipo.
equipo.
