Algoritmos y Estructura de Datos II

Mehr dazu

LOS SISTEMAS DE ARBOLES Y SU CLASIFICACION

von Rodolfo Melchor Rubio

Fundamento de números

von Gisell Báez

numeros racionales

von Daniela Cristancho

Pérez Buendía(En ro

von Rogelio Pérez-Buendía

Se dice que un arbol se convierte en grafo, si uno de los nodos hijos llegase a tener dos padres

Dentro de los grafos podemos encontrar diversos tipos; sin embargo, de forma básica son interesantes los siguientes (los demás se estudiarán más a fondo luego de comprender los mencionados) :

Esta estructura se caracteriza por que existe una relación entre los nodos que la componen, mediante "aristas", estos grafos son estudiados en la TEORÍA DE GRAFOS (donde se estudia su implementación mediante un lenguaje de programación). Sus aplicaciones son diversas en las ciencias computacionales y matemáticas debido, justamente, a la teoría de datos. Los grafos son escenciales para las resoluciones de algoritmos complejos.

Grafos no dirigidos

Grafos ponderados, etiquetados, con costos o pesados

Grafos dirigidos

Los árboles tienen muchas utilidades en el ámbito informático tales como : En árboles de busqueda,hash trees, treap(que tiene que ver con redes inalámbricas y asignación en memoria), huffman coding tree ( que tienen que ver con los archivos de formato .jpeg y .mp3), etc

Un grafo

Árbol binario de búsqueda Sea A un árbol binario de raíz R e hijos izquierdo y derecho (posiblemente nulos) HI y HD , respectivamente. Decimos que A es un árbol binario de búsqueda (ABB) si y solo si se satisfacen las dos condiciones al mismo tiempo: "HI es vacío" o ("R es mayor que todo elemento de HI" y "HI es un ABB"). "HD es vacío" o ("R es menor que todo elemento de HD" y "HD es un ABB").

Dentro de los árboles encontramos a los famosos árboles binarios: cuya característica principal es que cada nodo posee un hijo izquierdo y uno derecho, no excediendo mas de dos hijos por nodo. Además de los árboles binarios de búsqueda: los cuales son arboles binarios que satisfacen la siguiente condición:

Raíz: El nodo superior de un árbol. Hijo: Un nodo conectado directamente con otro cuando se aleja de la raíz. Padre: La noción inversa de hijo. Hermanos: Un conjunto de nodos con el mismo padre Descendiente: Un nodo accesible por descenso repetido de padre a hijo. Ancestro: Un nodo accesible por ascenso repetido de hijo a padre. Hoja: Un nodo sin hijos. Nodo interno: Un nodo con al menos un hijo Grado: Número de subárboles de un nodo Brazo: La conexión entre un nodo y otro Camino: Una secuencia de nodos y brazos conectados con un nodo descendiente. Nivel: El nivel de un nodo se define por 1 + (el número de brazos entre el nodo y la raíz) Altura de un nodo: La altura de un nodo es el número de brazos en el camino más largo entre ese nodo y una hoja Altura de un árbol: La altura de un árbol es la altura de su nodo raíz Profundidad: La profundidad de un nodo es el número de brazos desde la raíz del árbol hasta un nodo Bosque: Un bosque es un conjunto de árboles n ≥ 0 disjuntos Rama: Una ruta del nodo raíz a cualquier otro nodo.

Los TDA o ADT (en inglés), son un tipo de dato definido por el usuario, cuyas operaciones especifican como un usario (que sería el cliente) puede manipular datos, definiendo así una interfaz entre usuario y dato; por otro lado, un TDA se representa por medio de clases

Ambos son TDAs (TIPOS DE DATOS ABSTRACTOS

Sirve para estructurar

Esta estructura se caracteriza por la forma que posee al ser representada, ya que hace referencia a la forma jerárquica de un árbol (aunque facilmente se parece a una raíz).En java se usan TreeMap para representar un BST(Binary Search Tree). Debido a esto, a continuación se muestra una terminología usada para estos árboles

CIRCULAR DOBLEMENTE ENLAZADA

CIRCULARMENTE ENLAZADA

DOBLEMENTE ENLAZADA

SIMPLEMENTE ENLAZADA

Las listas enlazadas se clasifican en : simplemente enlazadas, doblemente enlazadas, circularmente enlazadas y circular doblemente enlazada

Debido a que se compone de nodos, los cuales son auto-referenciables, esos enlaces también se pueden conocer como "referencias"

Esta estructura de datos es una de las fundamentales y se la puede usar para implementar otras estructuras de datos(como las pilas y las colas). Es una secuencia de datos dispuestos uno detrás de otro (un nodo destrás de otro) y se relacionan a través de un "enlace"

Podemos encontrar colas lineales o prioridad, circulares(donde el primer elemento y el último están unidos) y bicolas(los nodos se pueden añadir y quitar por ambos extremos, llamados DEQUE)

Posee operaciones básicas como : encolar , agregar un elemento al final de la cola; y desencolar, que quita el primer elemento al principio de la cola. Además de la operación frente, que devuelve el último elemento agregado

Esta estructura de datos se carecteriza por lo siguiente: Su modo de acceso es del tipo FIFO ( first in, first out) el primero en entrar es el primero en salir; al contrario de una pila, los elementos se insertan por un extremo y salen por el otro.

En java se puede emplear la clase Stack para realizar la tarea de una pila

Posee dos operaciones básicas tales como : push (apilar) y pop (desapilar); con esto se puede entender que hay acceso siempre al último elemento y , para acceder al resto, debemos empezar por retirar este último (top of stack) y así consecutivamente hasta llegar al deseado

Esta estructura de datos se carecteriza por lo siguiente: Su modo de acceso es del tipo FILO ( last in, first out) el último en entrar es el primero en salir; además de ser muy sencillo y posee una buena respuesta a los procesos

Además de la diferencia de la manipulación del tamaño en la ejecución, existe algo por recalcar, el acceso varia dependiendo el tipo de dato estructurado. Si bien el estático favorece el acceso de una manera directa o aleatoria ( debido al índice ), cosa que no se cuenta en una estructura dinámica debido a que esta es secuencial y carece de índice; hay una desventaja en ciertos métodos tales como insertar y eliminar, cosa que en las dinámicas es mucho más facil que en las estáticas.

TipoArreglo nombreDelArreglo[][][]= new Tipo de arreglo[f][c][m] ; donde f son las filas, c las columnas, m las capas, TipoArreglo puede ser int, char, double, clasePersona, etc. (Sin embargo, un arregllo multidimensional puede aludir a una matriz que tiene por elementos arreglos)

Poseen dos a más índices de accesibilidad a la información, cuando hacemos referencia a multidimensión facilmente podemos hablar de arreglo de arreglos. De la misma forma podemos pensar en un arreglo más próximo al tema de multidimensionalidad como: un arreglo con un índice más con respecto a una matriz; dandonos una idea de "un cubo"

TipoArreglo nombreDelArreglo[][]= new Tipo de arreglo[f][c] ; donde f son las filas y c las columnas, TipoArreglo puede ser int, char, double, clasePersona, etc.(En java)

Poseen dos índices de accesibilidad a la información, el tamaño depende dos datos (número de filas y número de columnas)

{

int dato; NODO sgt;

public class NODO {

la estructura básica del nodo es la siguiente:

La estructura básica de este tipo de estructuras son los llamados NODOS, los cuales se componen por dos cosas importantes, la primera: donde se encuentran los datos, y la segunda: la que referencia a un objeto tipo nodo; por lo que podemos decir que es auto-referenciable,

TipoArreglo nombreDelArreglo[]= new Tipo de arreglo[n] ; donde n es el tamaño del arreglo, TipoArreglo puede ser int, char, double, clasePersona, etc. (En java)

Poseen un solo índice de accesibilidad a la información, el tamaño depende de un solo dato

Almacenan datos del mismo tipo o clase, se puede acceder a la información guardada mediante índices, además se puede trabajar arreglo de arreglos y arreglos escalonados

Tamaño definido antes de la ejecución del programa, no varían durante la ejecución.

Combinan tipos de datos primitivos en estructuras complejas y permiten representar la estructura de la información que el programa debe procesar, además se pueden implementar objetos

Su tamaño puede variar durante la ejecución del programa. Su acceso es secuencial

Arrays o Arreglos

Pilas

Listas enlazadas

Colas

Árboles

Grafos

Poliedros o Arreglos multidimensionales

Matrices o Arreglos bidimensionales

short nombreDato = 12;

Intervalo :[±3,4·10^(-38) .. ±3,4·10^38]

Intervalo : [±1,7·10^(-308) .. ±1,7·10^308]

Vectores o Arreglos unidimensionales

nombreDato = false;

nombreDato = true;

boolean nombreDato;

double nombreDato = 0,13345;

float nombreDato = 12,5 ;

byte nombreDato = 1;

char nombreDato = ' - ';

long nombreDato = 12123;

Intervalo : [-32,768 ... 32,767]

Tamaño en disco: 8 byte

Intervalo : [-2^63 ... (2^63)-1]

String nombreDato = " cadena ";

Conjunto de caracteres, se puede implementar de la siguiente forma (java):

Tamaño en disco: 2 byte

Intervalo : ['\u0000' .. '\uffff'] o [0 .. 65.535]

Tamaño en disco: 8 bits

Intervalo : [-128 ... 127]

int nombreDato = 11;

Tamaño en disco: 4 byte

Intervalo : [-2^31 ... (2^31)-1]

Indican verdad o falsedad (true o false)

long

short

byte

int

double

float

Lógico

Booleanos

Caracter

String

char

Numéricos

Enteros

Decimales

Estructura de datos: organización de datos en un conjunto con relaciones bien definidas. Pueden ser anidadas. Estos datos pueden ser: