Definicin de tipos de datos complejos.En loslenguajes de programaciny en otros programas utilitarios tales como una planilla de clculos, untipo de datoes un atributo de una parte de los datos que indica al ordenador (y/o al programador) algo sobre la clase de datos sobre los que se va a procesar. Esto incluye imponer restricciones en los datos, como qu valores pueden tomar y qu operaciones se pueden realizar.

Tipos de datos comunes son: enteros, nmeros decoma flotante(decimales), cadenas alfanumricas, fechas, horas, colores, coches o cualquier cosa que se nos ocurra. Por ejemplo, enJava, el tipo "int" representa un conjunto de enteros de 32 bits cuyo rango va desde el -2.147.483.648 al 2.147.483.647, as como las operaciones que se pueden realizar con los enteros, como la suma, resta y multiplicacin.

Los colores, por otra parte, se representan como tres bytes denotando la cantidad de rojo, verde y azul, y una cadena de caracteres representando el nombre del color; las operaciones permitidas incluyen la adicin y sustraccin, pero no la multiplicacin.

ste es un concepto propio de lainformtica, ms especficamente de los lenguajes de programacin, aunque tambin se encuentra relacionado con nociones similares de lasmatemticasy lalgica.

Los tipos de datos definen un conjunto de valores y las operaciones sobre estos valores. Casi todos los lenguajes de programacin explcitamente incluyen la notacin del tipo de datos, aunque lenguajes diferentes pueden usar terminologa diferente.

La mayor parte de los lenguajes de programacin permiten al programador definir tipos de datos adicionales, normalmente combinando mltiples elementos de otros tipos y definiendo las operaciones del nuevo tipo de dato. Por ejemplo, un programador puede crear un nuevo tipo de dato llamado "Persona" que especifica que el dato interpretado como Persona incluir un nombre y una fecha de nacimiento.

Un tipo de dato puede ser tambin visto como una limitacin impuesta en la interpretacin de los datos en unsistema de tipificacin, describiendo la representacin, interpretacin y la estructura de losvaloresuobjetosalmacenados en la memoria del ordenador. El sistema de tipificacin usa informacin de los tipos de datos para comprobar laverificacinde los programas que acceden o manipulan los datos.

PilasSon elementos que pueden insertar o eliminar solo por sus extremos, conocidos como la estructura de LIFO(Last In, Firt Out) que significa que el ultimo en entrar es el primero en salir, estas son representados en memorias de arreglos y listas enlazadas. Son usados en el software del sistema, compiladores e intrpretes.

Unapila(stackeningls) es una lista ordinal oestructura de datosen la que el modo de acceso a sus elementos es de tipoLIFO(del inglsLast In First Out,ltimo enentrar, primero ensalir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el rea deinformticadebido a su simplicidad y ordenacin implcita de la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones bsicas:apilar(push), que coloca un objeto en la pila, y su operacin inversa,retirar(o desapilar,pop), que retira el ltimo elemento apilado.

En cada momento slo se tiene acceso a la parte superior de la pila, es decir, al ltimo objeto apilado (denominadoTOS,Top of Stacken ingls). La operacinretirarpermite la obtencin de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.Por analoga con objetos cotidianos, una operacinapilarequivaldra a colocar un plato sobre una pila de platos, y una operacinretirara retirarlo.Laspilassuelen emplearse en los siguientes contextos: Evaluacin de expresiones ennotacin postfija(notacin polaca inversa). Reconocedores sintcticos delenguajes independientes del contexto Implementacin derecursividad.

Historia:El mtodo de pila para la evaluacin de expresiones fue propuesto en 1955 y dos aos despus patentado por Fiedrich L.Bauer, quin recibi en 1988 el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.

Pila como tipo abstracto de datos: La pila es un contenedor de nodos y tiene dos operaciones bsicas:push(o apilar) ypop(o desapilar). 'Push' aade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior de la pila

OperacionesUna pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen aadir ms de uso habitual. Crear:se crea la pila vaca. Apilar:se aade 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) Vaca:devuelve cierto si la pila est vaca o falso en caso contrario.

ImplementacinUn requisito tpico de almacenamiento de una pila de n elementos es O(n). El requisito tpico de tiempo de O (1) las operaciones tambin son fciles de satisfacer con un array o con listas enlazadas simples.La biblioteca de plantillas de C++ estndar proporciona una "pila" clase templated que se limita a slo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especializacin de Vector. Esto podra ser considerado como un defecto, porque el diseo heredado get () de Vector mtodo LIFO ignora la limitacin de la Pila.

Arquitectura bsica de la pila.Una pila tpica es un rea de la memoria de los computadores con un origen fijo y un tamao variable. Al principio, el tamao de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la ms reciente localizacin en la pila; cuando la pila tiene un tamao de cero, el puntero de pila de puntos en el origen de la pila.

Las dos operaciones aplicables a todas las pilas son: Una operacin apilar, en el que un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la direccin en el puntero de pila se ajusta por el tamao de los datos de partida.

Una operacin desapilar: un elemento de datos en la ubicacin actual apuntada por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamao de los datos de partida.

Hay muchas variaciones en el principio bsico de las operaciones de pila. Cada pila tiene un lugar fijo en la memoria en la que comienza. Como los datos se aadirn a la pila, el puntero de pila es desplazado para indicar el estado actual de la pila, que se expande lejos del origen (ya sea hacia arriba o hacia abajo, dependiendo de la aplicacin concreta).

Por ejemplo, una pila puede comenzar en una posicin de la memoria de mil, y ampliar por debajo de las direcciones, en cuyo caso, los nuevos datos se almacenan en lugares que van por debajo de 1000, y el puntero de pila se decrementa cada vez que un nuevo elemento se agrega. Cuando un tema es eliminado de la pila, el puntero de pila se incrementa.

Los punteros de pila pueden apuntar al origen de una pila o de un nmero limitado de direcciones, ya sea por encima o por debajo del origen (dependiendo de la direccin en que crece la pila), sin embargo el puntero de pila no puede cruzar el origen de la pila. En otras palabras, si el origen de la pila est en la direccin 1000 y la pila crece hacia abajo (hacia las direcciones 999, 998, y as sucesivamente), el puntero de pila nunca debe ser incrementado ms all de 1000 (para 1001, 1002, etc.) Si un desapilar operacin en la pila hace que el puntero de pila se deje atrs el origen de la pila, una pila se produce desbordamiento. Si una operacin de apilar hace que el puntero de pila incremente o decremente ms all del mximo de la pila, en una pila se produce desbordamiento.

La pila es visualizada ya sea creciente de abajo hacia arriba (como pilas del mundo real), o, con el mximo elemento de la pila en una posicin fija, o creciente, de izquierda a derecha, por lo que el mximo elemento se convierte en el mximo a "la derecha". Esta visualizacin puede ser independiente de la estructura real de la pila en la memoria. Esto significa que rotar a la derecha es mover el primer elemento a la tercera posicin, la segunda a la primera y la tercera a la segunda.

ColasEstas no permiten un acceso concreto son lneas de informacin en la que accede de un modo determinado, que viene estructurado como FIFO (First In, First Out) que significa que el primero dato que entrar es el primero dato en salir, estas son representados en memorias que como arreglos y como listas ordenadas. Tambin son usados por las simulaciones, planificaciones y los procesos de entrada y salida con buffer.Unacolaes unaestructura de datos, caracterizada por ser una secuencia de elementos en la que la operacin de insercinpushse realiza por un extremo y la operacin de extraccinpoppor el otro. Tambin se le llama estructuraFIFO(del inglsFirst In First Out), debido a que el primer elemento en entrar ser tambin el primero en salir.

Las colas se utilizan en sistemasinformticos,transportesy operaciones deinvestigacin(entre otros), dnde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa enlenguajes orientados a objetosmediante clases, en forma de listas enlazadas.

Usos concretos de la cola

La particularidad de una estructura de datos de cola es el hecho de que slo podemos acceder al primer y al ltimo elemento de la estructura. As mismo, los elementos slo se pueden eliminar por el principio y slo se pueden aadir por el final de la cola.

Ejemplos de colas en la vida real seran: personas comprando en un supermercado, esperando para entrar a ver un partido de bisbol, esperando en el cine para ver una pelcula, una pequea peluquera, etc. La idea esencial es que son todas lneas de espera.

Operaciones bsicas: Crear: se crea la cola vaca. Encolar:(aadir, entrar, push): se aade un elemento a la cola. Se aade al final de esta. Desencolar:(sacar, salir, pop): se elimina el elemento frontal de la cola, es decir, el primer elemento que entr. Frente:(consultar, front): se devuelve el eleme

Tipos de colas:

Colas circulares (anillos): en las que el ltimo elemento y el primero estn unidos. Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atendern de modo convencional segn la posicin que ocupen. Hay 2 formas de implementacin:1. Aadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola. Bicolas: son colas en donde los nodos se pueden aadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes: Bicolas de entrada restringida: Son aquellas donde la insercin slo se hace por el final, aunque podemos eliminar alinicio alfinal. Bicolas de salida restringida: Son aquellas donde slo

Listas. Son elementos de coleccin que almacenar informacin, en lista de una estructura de datos lineales. Estas listas vienen enlazada o encadenada en una coleccin de nodos o elementos; un nodo siempre contiene la direccin de memoria del siguiente nodo de informacin y un apuntador es la direccin de memoria de un nodo.Es una de lasestructuras de datosfundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia denodos, en los que se guardancamposde datos arbitrarios y una o dosreferencias(punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a losarrayconvencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminacin de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto est previamente identificado o localizado), pero no permiten unacceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales comoLispySchemetiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales comoCoC++y Java, respectivamente, disponen de referencias para crear listas enlazadas.

Historia: Las listas enlazadas fueron desarrolladas en 1955-56 porCliff ShawyHerbert SimnenRAND Corporationcomo la principal estructura de datos para suLenguaje de Procesamiento de la Informacin(IPL).

IPL fue usado por los autores para desarrollar varios programas relacionados con lainteligencia artificial, incluida la Mquina de la Teora General, elSolucionador de Problemas Generales, y un programa informtico de ajedrez. Se public enIRE Transactions on Information Theoryen 1956, y en distintas conferencias entre 1957-1959, incluida Proceedings of the Western Joint Computer en 1957 y 1958, y en Information Processing (Procendents de la primera conferencia internacional del procesamiento de la informacin de laUnesco) en 1959. El diagrama clsico actual, que consiste en bloques que representan nodos de la lista con flechas apuntando a los sucesivos nodos de la lista, apareci en Programming the Logic Theory Machine, de Newell y Shaw. Newell y Simon fueron reconocidos por el ACM Turing Award en 1975 por hacer contribuciones bsicas a la inteligencia artificial, a la psicologa del conocimiento humano y al procesamiento de las listas.El problema de los traductores del procesamiento natural del lenguaje condujo aVctor Yngvedel Instituto Tecnolgico de Massachusetts(MIT)a usar listas enlazadas como estructura de datos en suCOMIT, lenguaje de programacin paracomputadoras, que investig en el campo de laLingstica computacional. Un informe de este lenguaje, titulado A programming language for mechanical translation apareci enMechanical Translationen 1958.

LISP, el principalprocesador de listas, fue creado en 1958. Una de las mayores estructuras de datos deLISPes la lista enlazada.

En torno a los 60, la utilidad de las listas enlazadas y los lenguajes que utilizaban estas estructuras como su principal representacin de datos estaba bien establecida. Bert Green delMITLincoln Laboratory, public un estudio tituladoComputer languages for symbol manipulationenIRE Transaction on Human Factors in Electronicsen marzo de 1961 que resuma las ventajas de las listas enlazadas. Un posterior artculo,A Comparison of list-processing computer languagesby Bobrow and Raphael, apareca enCommunications of the ACMen abril de 1964.

Muchos sistemas operativos desarrollados por Technical Systems Consultants (originalmente de West Lafayette Indiana y despus de Raleigh, Carolina del Norte) usaron listas enlazadas simples como estructuras de ficheros. Un directorio de entrada apuntaba al primer sector de un fichero y daba como resultado porciones de la localizacin del fichero mediante punteros. Los sistemas que utilizaban esta tcnica incluan Flex (para el Motorola 6800 CPU), mini-Flex (la misma CPU) y Flex9 (para el Motorola 6809 CPU). Una variante desarrollada por TSC se comercializ a Smoke Signal Broadcasting en California, usando listas doblemente enlazadas del mismo modo.El sistema operativo TSS, desarrollado por IBM para las mquinas System 360/370, usaba una lista doblemente enlazada para su catlogo de ficheros de sistema. La estructura del directorio era similar a Unix, donde un directorio poda contener ficheros u otros directorios que se podan extender a cualquier profundidad. Una utilidad fue creada para arreglar problemas del sistema despus de un fallo desde las porciones modificadas del catlogo de ficheros que estaban a veces en memoria cuando ocurra el fallo. Los problemas eran detectados por comparacin de los links posterior y anterior por consistencia. Si el siguiente link era corrupto y el anterior enlace del nodo infectado era encontrado, el posterior link era asignado al nodo con el link del anterior.

Tipos de Listas Enlazadas

Listas enlazadas lineales Listas simples enlazadas

La lista enlazada bsica es lalista enlazada simplela cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valorNULLo a la lista vaca, si es el ltimo nodo.

Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo Lista Doblemente Enlazada

Un tipo de lista enlazada ms sofisticado es lalista doblemente enlazadaolista enlazadas de dos vas. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valorNULLsi es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valorNULLsi es el ltimo nodo.

Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anteriorEn algn lenguaje de muy bajo nivel,XOR-Linkingofrece una va para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque el uso de esta tcnica no se suele utilizar.

Listas enlazadas circularesEn una lista enlazada circular, el primer y el ltimo nodo estn unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier direccin hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el ms usado para dirigir buffers para ingerir datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros Listas enlazadas circulares simplesCada nodo tiene un enlace, similar al de laslistas enlazadas simples, excepto que el siguiente nodo del ltimo apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados despus de uno que ya tengamos referenciado. Por esta razn, es usual quedarse con una referencia solamente al ltimo elemento en una lista enlazada circular simple, esto nos permite rpidas inserciones al principio, y tambin permite accesos al primer nodo desde el puntero del ltimo nodo. Lista Enlazada Doblemente CircularEn una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al ltimo y el enlace siguiente del ltimo nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algn nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que est en la cabeza o al nodo cola, y as mantener el orden tan bien como en una lista doblemente enlazada. Nodos CentinelasA veces las listas enlazadas tienen unnodo centinela(tambin llamadofalso nodoonodo ficticio) al principio o al final de la lista, el cual no es usado para guardar datos. Su propsito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un primer y ltimo nodo.

Ventajas:Como muchas opciones en programacin y desarrollo, no existe un nico mtodo correcto para resolver un problema. Una estructura de lista enlazada puede trabajar bien en un caso pero causar problemas en otros. He aqu una lista con algunas de las ventajas ms comunes que implican las estructuras de tipo lista. En general, teniendo una coleccin dinmica donde los elementos estn siendo aadidos y eliminados frecuentemente e importa la localizacin de los nuevos elementos introducidos se incrementa el beneficio de las listas enlazadas.

Listas Enlazadas vs. Vectores o MatricesArrayLista Enlazada

IndexadoO(1)O(n)

Insercin / Eliminacin al finalO(1)O(1) or O(n)2

Insercin / Eliminacin en la mitadO(n)O(1)

PersistenciaNoSimples s

LocalizacinBuenaMala

Las listas enlazadas poseen muchas ventajas sobre losarrays. Los elementos se pueden insertar en una lista indefinidamente mientras que un array tarde o temprano se llenar necesitar ser redimensionado, una costosa operacin que incluso puede no ser posible si la memoria se encuentra fragmentada.

En algunos casos se pueden lograr ahorros de memoria almacenando la misma cola de elementos entre dos o ms listas es decir, la lista acaba en la misma secuencia de elementos. De este modo, uno puede aadir nuevos elementos al frente de la lista manteniendo una referencia tanto al nuevo como a los viejos elementos - un ejemplo simple de una estructura de datospersistente.

Desventajas:

Por otra parte, losarrayspermitenacceso aleatoriomientras que laslistas enlazadasslo permiten acceso secuencial a los elementos. Las listas enlazadas simples, de hecho, solo pueden ser recorridas en una direccin. Esto hace que las listas sean inadecuadas para aquellos casos en los que es til buscar un elemento por su ndice rpidamente, como el heapsort. El acceso secuencial en los arrays tambin es ms rpido que en las listas enlazadas.

Otra desventaja de las listas enlazadas es el almacenamiento extra necesario para las referencias, que a menudos las hacen poco prcticas para listas de pequeos datos como caracteres o valores booleanos.

Tambin puede resultar lento y abusivo el asignar memoria para cada nuevo elemento. Existe una variedad de listas enlazadas que contemplan los problemas anteriores para resolver los mismos. Un buen ejemplo que muestra los pros y contras del uso de arrays sobre listas enlazadas es la implementacin de un programa que resuelva el problema de Josephus. Este problema consiste en un grupo de personas dispuestas en forma de crculo. Se empieza a partir de una persona predeterminada y se cuenta n veces, la persona n-sima se saca del crculo y se vuelve a cerrar el grupo. Este proceso se repite hasta que queda una sola persona, que es la que gana. Este ejemplo muestra las fuerzas y debilidades de las listas enlazadas frente a los arrays, ya que viendo a la gente como nodos conectados entre s en una lista circular se observa como es ms fcil suprimir estos nodos. Sin embargo, se ve como la lista perder utilidad cuando haya que encontrar a la siguiente persona a borrar. Por otro lado, en un array el suprimir los nodos ser costoso ya que no se puede quitar un elemento sin reorganizar el resto. Pero en la bsqueda de la n-sima persona tan slo basta con indicar el ndice n para acceder a l resultando mucho ms eficiente.

Arboles.Unrboles unaestructura de datosampliamente usada que imita la forma de un rbol (un conjunto de nodos conectados). Unnodoes la unidad sobre la que se construye el rbol y puede tener cero o ms nodos hijos conectados a l. Se dice que un nodoaespadrede un nodobsi existe un enlace desdeahastab(en ese caso, tambin decimos quebes hijo dea). Slo puede haber un nico nodo sin padres, que llamaremosraz. Un nodo que no tiene hijos se conoce comohoja. Los dems nodos (tienen padre y uno o varios hijos) se les conoce comorama.Es un conjunto de grafos formados por nodos y conectados por las aristas. Contienen la raz, caminos, padre, hijos, hojas y subrbol.

Definicin:Formalmente, podemos definir un rbol de la siguiente forma: Caso base: un rbol con slo un nodo (es a la vez raz del rbol y hoja). Un nuevo rbol a partir de un nodonrykrbolesde racesconelementos cada uno, puede construirse estableciendo una relacin padre-hijo entrenry cada una de las races de loskrboles. El rbol resultante denodos tiene como raz el nodonr, los nodosson los hijos denry el conjunto de nodos hoja est formado por la unin de loskconjuntos hojas iniciales. A cada uno de los rbolesAise les denota ahorasubrbolesde la raz. Una sucesin de nodos del rbol, de forma que entre cada dos nodos consecutivos de la sucesin haya una relacin de parentesco, decimos que es unrecorridorbol. Existen dos recorridos tpicos para listar los nodos de un rbol:primero en profundidadyprimero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y as sucesivamente. En el segundo, por su parte, antes de listar los nodos de niveln+ 1(a distancian+ 1aristas de la raz), se deben haber listado todos los de niveln. Otros recorridos tpicos del rbol sonpreorden,postordeneinorden:

El recorrido enpreorden, tambin llamadoorden previoconsiste en recorrer en primer lugar la raz y luego cada uno de los hijosen orden previo. El recorrido eninorden, tambin llamadoorden simtrico(aunque este nombre slo cobra significado en los rboles binarios) consiste en recorrer en primer lugarA1, luego la raz y luego cada uno de los hijosen orden simtrico. El recorrido enpostorden, tambin llamadoorden posteriorconsiste en recorrer en primer lugar cada uno de los hijosen orden posterior y por ltimo la raz.Finalmente, puede decirse que esta estructura es una representacin del concepto de rbol enteora de grafos. Un rbol es un grafoconexo yacclico(ver tambinteora de grafosyGlosario en teora de grafos).

Tipos de arboles

rboles Binarios rbol de bsqueda binario auto-balanceable rboles AVL rboles Rojo-Negro rbol AA rboles Multicamino rboles B(Arboles de bsqueda multicamino autobalanceados) rbol-B+ rbol-B*Usos de los rboles Representacin de datosjerrquicos. Como ayuda para realizar bsquedas en conjuntos de datos (ver tambin:algoritmos de bsqueda en rboles).

Grafos.Los grafos son conjunto de puntos en el espacio en donde se hacen llamar vertices, el cual estn conectados por un conjuntos de lneas denominadas aristas en donde tales aristas pueden ser adyacentes, paralelas, cclicas y cruce, en cuanto a los vertices estas pueden ser adyacentes, terminal y aislados.Representacin de un grafo:

Existen dos formas de mantener un grafo "G" enla memoriade unacomputadora, una se llamaRepresentacin secuencialdeG, la cual se basa en lamatrizde adyacenciaA; la otra forma, es la llamadaRepresentacin enlazadadeGy se basa en listas enlazadas de vecinos. Independientemente de la forma en que se mantenga un grafoGen lamemoriade una computadora, el grafoGnormalmente se introduce enla computadorapor su definicin formal: Un conjunto de nodos y un conjunto de aristas Representacin secuencial de un grafo:Considere el grafo siguiente "G":

Conceptos y definiciones:Grafo: Es el conjunto de elementos entre los que existen ligaduras orientadas.Suponemos un conjunto x = {A, B, C, D, E, F} y una relacin G = (x, T) de manera que:TA = {B, C, D}TB = {A}TC = {B, D, F}TD = {D, E}TE = {0}TF = {0}Lo representamos mediante un diagrama sagital.Para ver el grfico seleccione la opcin "Descargar" del men superiorCuadro de doble entrada.ABCDEF

A111

B1

C111

D11

E

F

Definiciones:Vrtice: Elemento de un conjunto que constituye un grafo.Arco: Par de elementos entre los que existe relacin teniendo en cuenta la orientacin, es decir que exista relacin orientada: (A, B); (A, C); (B, A);Camino: Es una sucesin de arcos adyacentes que nos permiten pasar de un vrtice a otro: (A, C, D, E).Circuito: Es un camino en el que el vrtice inicial y final coinciden: (A, C, B, A); (A, B, A).Bucle: Es un arco en el que el vrtice origen y final coinciden: (D)Arista: Relacin entre dos vrtices sin atender a la orientacin: (C, A); (A, C).Cadena: Sucesin de aristas adyacentes: (F, C, B, A).Longitud de un camino o circuito: Se mide por el nmero de arcos que constituyen el camino o circuito.Grafo conexo: Entre todo par de vrtices podemos establecer al menos una cadena.A Grafo no conexo ya que E no se relaciona con nadie y nadie se relaciona con l.Para ver el grfico seleccione la opcin "Descargar" del men superiorGrafo fuertemente conexo: Es aquel que entre cualquier par de vrtices podemos establecer al menos un camino.Grafo sincircuitos: Es aquel que no tiene circuitos.A nosotros nos interesan los grafos sin circuitos y conexos.