SUBSECRETARÍA DE EDUCACIÓN SUPERIORDIRECCIÓN GENERAL DE EDUCACIÓN SUPERIOR TECNOLÓGICA

UNIVERSIDAD TECNOLOGICA SANTA CATARINAPROGRAMA EDUCATIVO DE:

TECNOLOGIAS DE LA INFORMACION Y COMUNICACION

MANUAL DE ASIGNATURA DE:

ESTRUCTURA DE DATOS

Universidad Tecnológica Santa CatarinaCarretera Saltillo-Monterrey Km. 61.5

Santa Catarina C.p. 66359Tel. 81248400

www.utsc.edu.mx

Unidades TemáticasI. Conceptos básicos

II. Arreglos III. Listas IV. Pilas V. Colas VI. Árboles

I. Conceptos básicosObjetivo General: El alumno elaborará programas que integren el uso de recursividady definir estructuras de datos para generar alternativas de programación.

Tipo de dato abstractoUn tipo de dato abstracto (TDA) o Tipo abstracto de datos (TAD) es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo.

1 Introducción2 Historia3 Definición4 Separación de la interfaz e implementación5 Caracterización6 La abstracción7 Ejemplos de utilización de TDAs IntroducciónEn el mundo de la programación existen diversos lenguajes que se han ido creando con el paso del tiempo y que se han perfeccionado debido a las necesidades de los programadores de la época a la que pertenecen. Los primeros lenguajes de programación eran de tipo lineal, ya que un programa se recorría desde un punto marcado como Inicio hasta llegar a un punto Fin. Con el tiempo se fueron creando nuevos lenguajes y en nuestros días los más utilizados son los llamados “Orientados a Objetos”.

Los Lenguajes Orientados a Objetos (LOO) tienen la característica de que no son lenguajes lineales, sino que se forman de diversas funciones, las cuales son llamadas en el orden en que el programa mismo las pide o el usuario determina. Para entender mejor cómo funcionan los Lenguajes Orientados a Objetos, vamos a introducir un concepto fundamental en las Estructuras de Datos denominado Abstracción de Datos y que es parte importante de estos Lenguajes y de la manera en que funciona la mayoría del software comercial de nuestros días.

HistoriaEl concepto de tipo de dato abstracto (TDA, Abstract Data Type), fue propuesto por primera vez hacia 1974 por John Guttag y otros, pero no fue hasta 1975 que por primera vez Liskov lo propuso para el lenguaje CLU.

El lenguaje Turbo Pascal fue determinante para la común aceptación de los TDAs con la introducción de las Units, si bien estas no cumplen con las características básicas de un Tipo de dato Abstracto como por ejemplo la encapsulación de los datos. El lenguaje Ada pudo implementar exitosamente los TDAs con sus Packages. Vale recordar que estos dos últimos lenguajes soportan formalmente la Programación modular.

[editar] DefiniciónCon mucha frecuencia se utilizan los términos TDA y Abstracción de Datos de manera equivalente, y esto es debido a la similitud e interdependencia de ambos. Sin embargo, es importante definir por separado los dos conceptos.

Como ya se mencionó, los Lenguajes de Programación Orientados a Objetos son lenguajes formados por diferentes métodos o funciones y que son llamados en el orden en que el programa lo requiere, o el usuario lo desea. La abstracción de datos consiste en ocultar las características de un objeto y obviarlas, de manera que solamente utilizamos el nombre del objeto en nuestro programa. Esto es similar a una situación de la vida cotidiana. Cuando yo digo la palabra “perro”, usted no necesita que yo le diga lo que hace el perro. Usted ya sabe la forma que tiene un perro y también sabe que los perros ladran. De manera que yo abstraigo todas las características de todos los perros en un solo término, al cual llamo “perro”. A esto se le llama ‘Abstracción’ y es un concepto muy útil en la programación, ya que un usuario no necesita mencionar todas las características y funciones de un objeto cada vez que éste se utiliza, sino que son declaradas por separado en el programa y simplemente se utiliza el término abstracto (“perro”) para mencionarlo.

En el ejemplo anterior, “perro” es un Tipo de Dato Abstracto y todo el proceso de definirlo, implementarlo y mencionarlo es a lo que llamamos Abstracción de Datos.

Vamos a poner un ejemplo real de la programación. Supongamos que en algún Lenguaje de Programación Orientado a Objetos un pequeño programa saca el área de un rectángulo de las dimensiones que un usuario decida. Pensemos también que el usuario probablemente quiera saber el área de varios rectángulos. Sería muy tedioso para el programador definir la multiplicación de ‘base’ por ‘altura’ varias veces en el programa, además que limitaría al usuario a sacar un número determinado de áreas. Por ello, el programador puede crear una función denominada ‘Área’, la cual va a ser llamada el número de veces que sean necesitadas por el usuario y así el programador se evita mucho trabajo, el programa resulta más rápido, más eficiente y de menor longitud. Para lograr esto, se crea el método Área de una manera separada de la interfaz gráfica presentada al usuario y se estipula ahí la operación a realizar, devolviendo el valor de la multiplicación. En el método principal solamente se llama a la función Área y el programa hace el resto.

Al hecho de guardar todas las características y habilidades de un objeto por separado se le llama Encapsulamiento y es también un concepto importante para entender la estructuración de datos. Es frecuente que el Encapsulamiento sea usado como un sinónimo del Ocultación de información, aunque algunos creen que no es así [1].

Separación de la interfaz e implementaciónCuando se usa en un programa de computación, un TDA es representado por su interfaz, la cual sirve como cubierta a la correspondiente implementación. Los usuarios de un TDA tienen que preocuparse por la interfaz, pero no con la implementación, ya que esta puede cambiar en el tiempo y afectar a los programas que usan el TDA. Esto se basa en el concepto de Ocultación de información, una protección para el programa de decisiones de diseño que son objeto de cambio.

La solidez de un TDA reposa en la idea de que la implementación está escondida al usuario. Solo la interfaz es pública. Esto significa que el TDA puede ser implementado de diferentes formas, pero mientras se mantenga consistente con la interfaz, los programas que lo usan no se ven afectados.

Hay una diferencia, aunque a veces sutil, entre el Tipo de Dato Abstracto y la Estructura de Dato usada en su implementación. Por ejemplo, un TDA de una lista puede ser implementado mediante un Arreglo o una Lista Enlazada o hasta un Árbol binario de búsqueda. Una lista es un Tipo de Dato Abstracto con operaciones bien definidas (agregar elemento, agregar al final, agregar al principio, recuperar, eliminar, etc) mientras una lista enlazada es una estructura de datos basada en punteros o referencias (dependiendo del lenguaje) que puede ser usada para crear una representación de una Lista. La Lista Enlazada es comúnmente usada para representar una TDA Lista, y a veces, hasta confundida. Un ejemplo es la clase Linked List de Java, la cual ofrece una gran cantidad de métodos que no corresponden a una Lista Enlazada "pura", sino a un fuerte TDA.

De forma similar, un TDA Árbol binario de búsqueda puede ser representado de muchas maneras: Árbol binario, Árbol AVL, Árbol rojo-negro, Arreglo, etc. A pesar de la implementación un Árbol binario siempre tiene las mismas operaciones (insertar, eliminar, encontrar, etc.)

Separar la interfaz de la implementación no siempre significa que el usuario ignora totalmente la implementación de la rutina, pero lo suficiente para no depender de ningún aspecto de la implementación. Por ejemplo, un TDA puede ser creado usando un script o cualquiera que pueda ser decompilado (como C).

En la terminología de Lenguaje Orientado a Objeto, un TDA es una clase; un instancia de un TDA o clase, es un objeto.

CaracterizaciónUn TDA está caracterizado por un conjunto de operaciones (funciones) al cual le denominaron usualmente como su interfaz pública y representan el comportamiento del TDA; mientras que la implementación como la parte privada del TDA está oculta al programa cliente que lo usa. Todos los lenguajes de alto nivel tienen predefinidos TDA; que son los tipos denominados simples y las estructuras predefinidas, y estos tienen sus interfaces públicas que incluyen las operaciones como la +, -, *, etc. no se necesita conocer como actúan tales

operadores sobre la representación interna de los tipos definidos, que además, suele ser una implementación bastante dependiente de la máquina sobre la que trabaje el compilador. Lo interesante es que los lenguajes actuales nos van a permitir ampliar los TDA predefinidos con otros que serán definidos por el propio programador para adecuar así los tipos de datos a las necesidades de los programas.

Los TDA que nos van a interesar de ahora en adelante son aquellos que reflejen cierto comportamiento organizando cierta variedad de datos estructuradamente. A esta forma estructurada de almacenar los datos será a la que nos refiramos para caracterizar cada TDA.

Los TDA que tienen informaciones simples pero dependientes de un comportamiento estructural serán llamados polilíticos y aquellos TDA simples, como son los tipos predefinidos donde la información no es relacionada mediante ninguna estructura y no admiten más que un valor en cada momento serán denominados TDA monolíticos.

Nótese que cuando hablemos de un TDA no haremos ninguna alusión al tipo de los elementos sino tan sólo a la forma en que están dispuestos estos elementos. Sólo nos interesa la estructura que soporta la información y sus operaciones. Para determinar el comportamiento estructural basta con observar la conducta que seguirán los datos.

Caractericemos entonces los TDA. Un TDA tendrá una parte que será invisible al usuario la cual hay que proteger y que se puede decir que es irrelevante para el uso del usuario y está constituida tanto por la maquinaria algorítmica que implemente la semántica de las operaciones como por los datos que sirvan de enlace entre los elementos del TDA, es decir, información interna necesaria para la implementación que se esté haciendo para ese comportamiento del TDA. Resumiendo podemos decir, que tanto la implementación de las operaciones como los elementos internos del TDA serán privados al acceso externo y ocultos a cualquier otro nivel.

Un TDA representa una abstracción:

Se destacan los detalles (normalmente pocos) de la especificación (el qué).Se ocultan los detalles (casi siempre numerosos) de la implementación (el cómo).[editar] La abstracciónLa abstracción, una de las herramientas que más nos ayuda a la hora de solucionar un problema, es un mecanismo fundamental para la comprensión de problemas y fenómenos que poseen una gran cantidad de detalles, su idea principal consiste en manejar un problema, fenómeno, objeto, tema o idea como un concepto general, sin considerar la gran cantidad de detalles que estos puedan tener. El proceso de abstracción presenta dos aspectos complementarios.

1.Destacar los aspectos relevantes del objeto.2.Ignorar los aspectos irrelevantes del mismo (la irrelevancia depende del nivel de abstracción, ya que si se pasa a niveles más concretos, es posible que ciertos aspectos pasen a ser relevantes).De modo general podemos decir que la abstracción permite establecer un nivel jerárquico en el estudio de los fenómenos, el cual se establece por niveles sucesivos de detalles. Generalmente, se sigue un sentido descendente de detalles, desde los niveles más generales a los niveles más concretos.

Por ejemplo: los lenguajes de programación de alto nivel permiten al programador abstraerse del sin fin de detalles de los lenguajes ensambladores. Otro ejemplo, la memoria de la computadora es una estructura unidimensional formada por celdas y sin embargo trabajamos como si fuera única. La abstracción nos brinda la posibilidad de ir definiendo una serie de refinamientos sucesivos a nuestro TDA y entiéndase bien que cuando decimos refinamientos sucesivos nos estamos refiriendo a la estrategia que se utiliza para descomponer un problema en subproblemas. Conforme evoluciona el diseño de software a cada nivel de módulos se representa un refinamiento en el nivel de abstracción. Esto es, incluir detalles que fueron obviados en un nivel superior, en un nivel más bajo de la jerarquía.

Veamos los diferentes tipos de abstracción que podemos encontrar en un programa:

1. Abstracción funcional: crear procedimientos y funciones e invocarlos mediante un nombre donde se destaca qué hace la función y se ignora cómo lo hace. El usuario sólo necesita conocer la especificación de la abstracción (el qué) y puede ignorar el resto de los detalles (el cómo).

2. Abstracción de datos:

Tipo de datos: proporcionado por los leguajes de alto nivel. La representación usada es invisible al programador, al cual solo se le permite ver las operaciones predefinidas para cada tipo.Tipos definidos: por el programador que posibilitan la definición de valores de datos más cercanos al problema que se pretende resolver.TDA: para la definición y representación de tipos de datos (valores + operaciones), junto con sus propiedades.Objetos: Son TDA a los que se añade propiedades de reutilización y de compartición de código.Si profundizamos más al mundo de la programación y sus conceptos, existen dos de estos conceptos que no se deben confundir, ellos son: tipo de datos y estructura de datos.

Un tipo de dato, en un lenguaje de programación, define un conjunto de valores que una determinada variable puede tomar, así como las operaciones básicas sobre dicho conjunto. Ahora veamos como se van relacionando estos conceptos. Los tipos de datos constituyen un primer nivel de abstracción, ya que no se tiene en cuenta cómo se implementan o se representan realmente la información sobre la memoria de la máquina. Para el usuario, el proceso de implementación o representación es invisible.

Veamos entonces que son las estructuras de datos. Las estructuras de datos son colecciones de variables, no necesariamente del mismo tipo, relacionadas entre sí de alguna forma. Las estructuras de datos están caracterizadas por el tipo de dato de los elementos guardados en la estructura y por la relación definida sobre estos elementos.

Al nivel de las estructuras de datos son totalmente irrelevantes las operaciones sobre un elemento en particular, solamente tienen carácter relevante las operaciones que envuelvan la estructura de forma global.

Ejemplos de utilización de TDAsAlgunos ejemplos de utilización de TDAs en programación son:

Conjuntos: Implementación de conjuntos con sus operaciones básicas (unión, intersección y diferencia), operaciones de inserción, borrado, búsqueda...Árboles Binarios de Búsqueda: Implementación de árboles de elementos, utilizados para la representación interna de datos complejos. Aunque siempre se los toma como un TDA separado son parte de la familia de los grafos.Pilas y Colas: Implementación de los algoritmos FIFO y LIFO.Grafos: Implementación de grafos; una serie de vértices unidos mediante una serie de arcos o aristas.

Recursión

Recurrencia, Recursión (incorrecto en castellano) o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.

Para que se entienda mejor a continuación se exponen algunos ejemplos:

Factorial(x: Entero): Sea N := x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x - 1); como el tamaño de Factorial(x - 1) es menor que N podemos aplicar inducción por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1.

Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por inducción podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.

En estos ejemplos podemos observar como un problema se divide en varias (>= 1) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base)..

Nota: aunque los términos "recursión" y "recursividad" son ampliamente empleados en el campo de la informática, el término correcto en castellano es recurrencia. Sin embargo este último término es algo más específico. Véase relación de recurrencia.

Contenido

1 Los números naturales 2 Funciones definidas de forma recurrente 3 Algoritmo recursivo 4 Ejemplos de recurrencias 5 Véase también 6 Enlaces externos

Los números naturales

Un ejemplo de conjunto definido de forma recurrente es el de los números naturales:

a) 0 pertenece a Nb) Si n pertenece a N, entonces n+1 pertenece a Nc) Si X verifica a) y b) , entonces N está incluido en X

Los números naturales es el conjunto de números enteros no negativos.

Funciones definidas de forma recurrente

Aquellas funciones cuyo dominio puede ser recursivamente definido pueden ser definidas de forma recurrente.

El ejemplo más conocido es la definición recurrente de la función factorial n!:

Con esta definición veamos como funciona esta función para el valor del factorial de 3:

3! = 3 · (3-1)! = 3 · 2! = 3 · 2 · (2-1)! = 3 · 2 · 1!

= 3 · 2 · 1 · (1-1)! = 3 · 2 · 1 · 0! = 3 · 2 · 1 · 1 = 6

Algoritmo recursivo

Artículo principal: Algoritmo recursivo

Un método usual de simplificación de un problema complejo es la división de este en subproblemas del mismo tipo. Esta técnica de programación se conoce como divide y vencerás y es el núcleo en el diseño de numerosos algoritmos de gran importancia, así como también es parte fundamental de la programación dinámica.

El ejemplo del cálculo recursivo del factorial de un número llevado al campo de la programación, en este ejemplo C++:

int factorial (int x){ if (x < 2) return 1; // Caso base: Cuando X < 2 devolvemos 1 puesto que 1! = 1 return x*factorial(x - 1); // Si X >= 2 devolvemos el producto de 'X' por el factorial de 'X'-1}

El seguimiento de la recursividad programada es casi exactamente igual al ejemplo antes dado, para intentar ayudar a que se entienda mejor se ha acompañado con muchas explicaciones y con colores que diferencia los distintos sub-procesos de la recursividad.

X = 3 //Queremos 3!, por lo tanto X inicial es 3X >= 2 -> return 3*factorial(2); X = 2 //Ahora estamos solicitando el factorial de 2 X >= 2 -> return 2*factorial(1); X = 1 // Ahora estamos solicitando el factorial de 1 X < 2 -> return 1; [En este punto tenemos el factorial de 1 por lo que volvemos marcha atrás resolviendo todos los resultados] return 2 [es decir: return 2*1 = return 2*factorial(1)]return 6 [es decir: return 3*2 = return 3*factorial(2)*factorial(1)] // El resultado devuelto es 6

Ejemplos de recurrencias

Resolución de ecuaciones homogéneas de primer grado, segundo orden:

a) Se pasan al primer miembro los términos an, an − 1, an − 2, los cuales también podrían figurar como an + 2, an + 1, an

b) Se reemplaza an por r2, an − 1 por r y an − 2 por 1, quedando una ecuación de segundo grado con raíces reales y distintas r1 y r2.

c) Se plantea

d) Debemos tener como dato los valores de los dos primeros términos de la sucesión: y . Utilizando estos datos ordenamos el sistema de 2x2:

La resolución de este sistema nos da como resultado los valores u0 y v0, que son números reales conocidos.

e) La solución general es:

Algunos ejemplos de recurrencia:

Factorial -- n! = n × (n-1)! Sucesión de Fibonacci -- f(n) = f(n-1) + f(n-2) Números de Catalan -- C(2n, n)/(n+1) Las Torres de Hanói Función de Ackermann

II. ArreglosObjetivo General: El alumno elaborará programas que integren el uso de recursividady definir estructuras de datos para generar alternativas de programación.

Contenido

1 Arrays y cadenas de texto 2 Indices de un arreglo 3 Dimensiones de un arreglo

o 3.1 Arreglo unidimensionalo 3.2 Arreglo bidimensional

4 Declaración de arreglos en C, C++ o 4.1 Iteraciones dentro de un arreglo (vector)o 4.2 Iteraciones dentro de un arreglo (matriz)

5 Cadenas de caracteres o 5.1 La biblioteca string

6 Cadenas en C++ 7 Arreglos en C++

Arrays y cadenas de texto

Los arreglos son usados extensamente por los programadores para contener listas de datos en la memoria, por ejemplo, los datos almacenados en un disco suelen leerse y ponerse dentro de un arreglo con el objetivo de facilitar la manipulación de dichos datos, ya que los datos en memoria pueden ser modificados, clasificados, marcados para su eliminacion, etc. para luego ser reescritos al disco. Otro ejemplo podría ser el de un menú de opciones que se desplegarán dentro de una ventana para que el usuario pueda elegir una de éstas, en tales casos y cuando las opciones son numerosas, solamente se ponen unas cuantas de ellas dentro de la ventana pero se le da al usuario la oportunidad de poder subir y bajar a su antojo para ver el resto de opciones que, aunque no se vean en la ventana, forman parte del menú o arreglo de opciones.

Arreglo:

Un arreglo es un conjunto de datos del mismo tipo ordenados en forman líneal uno despues de otro. Los componentes de un arreglo se han de referenciar por medio del nombre del arreglo y un índice de desplazamiento para indicar el componente deseado.

Indices de un arreglo

Los índices son números que se utilizan para identificar a cada uno de los componentes de un arreglo. A manera de ejemplo, podemos pensar que los índices son como los números de cuartos de un hotel, es decir, para poder dirijirnos a un hotel específico es necesario saber el nombre del mismo, luego, si queremos llegar a un cuarto específico de dicho hotel necesitaremos, ademas del nombre del hotel, el número de cuarto deseado. También, podemos pensar en los casilleros del estante de paquetería de un supermercado, asi que si deseamos guardar o retirar un paquete nos direjimos a paquetería el cual sería el nombre del arreglo; luego, el empleado guarda nuestro paquete dentro de un casillero con un número específico el cual sería el índice para identificar el lugar del casillero en paquetería donde quedó guardado el paquete. Supongamos que el empleado nos entrega una ficha con el número 12 impreso sobre la misma; de tal manera que podemos decir que nuestro paquete está guardado en paqueteria(12) ó paqueteria[12].

Dimensiones de un arreglo

De acuerdo a la forma en que se construye o declara un arreglo, éste puede ser clasificado como: unidimensional, bidimensional y multidimensional. Los arreglos que se emplean con mucha más frecuencia son los estructurados a manera de vector ( arreglo unidimensional ) y los estructurados a manera de matriz ( arreglo bidimensional ), así, aunque en C++ se pueden crear estructuras multidimensionales, en este capítulo solo trataremos con vectores y matrices.

Arreglo unidimensional

Una arreglo uni-dimensional es aquel en donde los componentes son accesados por medio de uno y solamente un índice que apunte al componente requerido. Los arreglos de este tipo son conocidos también con el nombre de vectores. Conceptualmente, podemos pensar en un arreglo unidimensional como en una lista compuesta de líneas o filas en donde para referinos a una de ellas emplearemos un número para indicar la posición de la misma dentro de la lista. Por ejemplo, consideremos el caso de la tabla o arreglo VentaSemanal, la cual está pensada para registrar las ventas de cada uno de los días de la semana. Luego, de manera conceptual podemos ver al arreglo como se muestra en seguida.

Nota: en C++ los arreglos estan basados en 0 ( cero ), es decir, el primer elemento de un arreglo se indexa mediante el 0, y el índice para el último de los elementos es igual al número de componentes menos uno.

arreglo: VentaSemanal

+------+| dato | <-- componente 0, ( fila 0 )|------|| dato | <-- componente 1, ( fila 1 )|------|| dato | ...|------|| dato | ...|------|| dato | ...|------|| dato | ...|------|| dato | <-- componente 6, ( fila 6 )|------|

Si en el arreglo VentaSemanal queremos que el elemento 4 ( por ejemplo ) contenga el valor de 8987 lo podemos lograr con la instrucción: VentaSemanal[4] = 8987; y el estado del arreglo sería:

arreglo: VentaSemanal

+------+| dato ||------|| dato ||------|| dato ||------|| dato ||------|| 8987 | <--- componente 4|------|| dato ||------|| dato ||------|

Arreglo bidimensional

Una arreglo bi-dimensional es aquel en donde los componentes son accesados por medio de una pareja de índices que apunten a la fila y columna del componente requerido. Los arreglos de este tipo son conocidos también con el nombre de matrices. Conceptualmente, podemos pensar en un arreglo bidimensional como en una lista compuesta de filas y columnas, en donde para referinos a una de ellas emplearemos un número para indicar la posición de fila y otro número para indicar la posición de la columna del componente deseado. Por ejemplo, consideremos el caso de la tabla o arreglo VentaSemanaQ, la cual está pensada para registrar las ventas de cada uno de los días de la semana por cuatro semanas, o sea , una tabla de 7 x 4 elementos. Luego, de manera conceptual podemos ver al arreglo como se muestra en seguida.

arreglo: VentaSemanaQ

C O L U M N A S

+--- componente ( 0, 0 ) | +------+------+------+------+ | dato | dato | dato | dato | |------|------|------|------| F | dato | dato | dato | dato | |------|------|------|------| I | dato | dato | dato | dato | |------|------|------|------| L | dato | dato | dato | dato | |------|------|------|------| A | dato | dato | dato | dato | |------|------|------|------| S | dato | dato | dato | dato | |------|------|------|------| | dato | dato | dato | dato | +------+------+------+------+ | +---- componente ( 6, 3 )

Si en el arreglo VentaSemanaQ queremos que el elemento de la fila 4, columna 3 ( por ejemplo ) contenga el valor de 5000 lo podemos lograr con la instrucción: VentaSemanaQ[4][3] = 5000; y el estado del arreglo sería:

arreglo: VentaSemanaQ

+--- componente ( 0, 0 ) |+------+------+------+------+| dato | dato | dato | dato ||------|------|------|------|| dato | dato | dato | dato ||------|------|------|------|| dato | dato | dato | dato ||------|------|------|------|| dato | dato | dato | dato ||------|------|------|------|| dato | dato | dato | 5000 | <-- componente ( 4, 3 )|------|------|------|------|| dato | dato | dato | dato ||------|------|------|------|| dato | dato | dato | dato |+------+------+------+------+ | +---- componente ( 6, 3 )

Declaración de arreglos en C, C++

En C, C++ para declarar un arreglo se emplea la sintaxis:

tipo identificador [tamaño] = { lista de inicialización } ;

donde,

tipo se refiere al tipo de datos que contendrá el arreglo. El tipo puede ser cualquiera de los tipos estándar (char, int, float, etc.) o un tipo definido por el usuario. Es más, el tipo del arreglo puede ser de una estructura creada con: struct, union y class.

identificador se refiere al nombre que le daremos al arreglo.

tamaño es opcional e indica el número de elementos que contendrá el arreglo. Si un arreglo se declara sin tamaño, el mismo no podrá contener elemento alguno a menos que en la declaración se emplee una lista de inicialización.

lista de inicialización es opcional y se usa para establecer valores para cada uno de los componentes del arreglo. Si el arreglo es declarado con un tamaño especifíco el número de valores inicializados no podrá ser mayor a dicho tamaño.

Ejemplos:

int intA[5];long longA[5] = { 1, 2, 3, 4, 5 };char charA[3] = { 'a', 'b', 'c' );

Iteraciones dentro de un arreglo (vector)

El termino Iterar se refiere al hecho de acceder ( con el fin de leer o escribir) sobre cada uno de los componentes de un arreglo. Así, para poner un ejemplo reconsideremos el caso de la tabla VentaSemanal (vista

en una sección anterior), y que dicho sea de paso es un arreglo de 7 elementos de tipo double. Luego, vamos a mostrar como ejemplo un programa completo en el cual se declara el arreglo mencionado con valores inicializados, mismos que serán mostrados en pantalla y al final la suma de estos. Observe que la variable i usada para iterar dentro del arreglo va desde 0 hasta FILAS - 1 ( FILAS es el tamaño del arreglo ).

Nota: por motivos de simplificación el programa está escrito al estilo de C estándar. Sin embargo puede ser compilado y ejecutado en un compilador de C++.

#include <stdio.h>#include <stdlib.h> #define FILAS 7 int main(){ float ventas[FILAS] = { 123.50, 234.60, 345.45, 321.40, 345.00, 456.65, 0.0 }; float total = 0; int i; puts("Ventas de la semana"); puts("-------------------"); for (i=0; i<FILAS; i++) { total += ventas[i]; printf( "%8.2f\n", ventas[i] ); } puts("--------"); printf("%8.2f\n", total ); system("pause"); return 0;} Esta es la salida del programa:Ventas de la semana------------------- 123.50 234.60 345.45 321.40 345.00 456.65 0.00-------- 1826.60

Iteraciones dentro de un arreglo (matriz)

Con el fin de leer o escribir sobre cada uno de los componentes de una matriz se deben crear dos ciclos de iteración. Así, para poner un ejemplo reconsideremos el caso de la tabla VentaSemanaQ (vista en una sección anterior), y que dicho sea de paso es un arreglo de 4 x 4 elementos de tipo double. Luego, vamos a mostrar como ejemplo un programa completo en el cual se declara el arreglo mencionado con valores inicializados, mismos que serán mostrados en pantalla y al final la suma de estos. Observe que en este caso se utilizan dos variables, una para iterar sobre las filas y otra para iterar sobre las columnas de la matriz.

#include <stdio.h>#include <stdlib.h> #define FILAS 7#define COLS 4 int main(){ float VentaSemanaQ[FILAS][COLS] = { 123.50, 234.60, 345.45, 321.40, 345.00, 456.65, 123.50, 234.60, 345.45, 321.40, 345.00, 456.65, 123.50, 234.60, 345.45, 321.40, 345.00, 456.65, 123.50, 234.60, 345.45, 321.40, 345.00, 456.65, 0.0, 0.0, 0.0, 0.0 }; float totales[COLS] = { 0.0, 0.0, 0.0, 0.0 }; float grantotal = 0; int f, c, t = 0 ; /* indices para filas, columnas y totales */ puts("Ventas de cuatro semanas"); puts("------------------------"); for (f=0; f<FILAS; f++) { for (c=0; c<COLS; c++) { totales[c] += ventas[f][c]; printf("%8.2f ", ventas[f][c] ); } puts(""); } puts("--------------------------------------"); for (t=0; t<COLS; t++) { printf("%8.2f ", totales[t] ); grantotal += totales[t]; } printf("\n\nGran total: %10.2f\n", grantotal); system("pause"); return 0;} Salida del programa: Ventas de cuatro semanas------------------------ 123.50 234.60 345.45 321.40 345.00 456.65 123.50 234.60 345.45 321.40 345.00 456.65 123.50 234.60 345.45 321.40 345.00 456.65 123.50 234.60 345.45 321.40 345.00 456.65 0.00 0.00 0.00 0.00-------------------------------------- 1627.90 2025.30 1627.90 2025.30

Gran total: 7306.40

Cadenas de caracteres

En C,C++ las cadenas de caracteres no son más que arreglos de caracteres, salvo que a este tipo de arreglos el compilador les da un tratamiento especial. Usted puede manipular las cadenas de caracteres de la misma manera en que manipula cualquier otro tipo de arreglo, sin embargo, es preferible hacer uso de una librería estándar especialmente escrita para manipulacion de cadenas de caracteres, me refiero a la librería <string.h> y que viene incluida con todo compilador de C,C++.

Para comenzar y antes de ver algunas de las funciones de la mencionada librería, tenemos los siguientes ejemplos:

1. char nombre[] = "Oscar";2. char nombre2[] = { 'O', 's', 'c', 'a', 'r', '\0' };

En el ejemplo 1 se está declarando la variable nombre como una cadena de caracteres y cuyo contenido inicial es "Oscar".

En el ejemplo 2 se está declarando la variable nombre2 como una cadena de caracteres y cuyo contenido inicial es { 'O', 's', 'c', 'a', 'r', '\0' };.

En ambos casos el resultado es el mismo, es decir, al final se obtiene la misma cadena, pero usted debe poner atención al hecho de que toda cadena de caracteres en C,C++ debe terminar con el caracter NULL, mismo que normalmente es igual a cero y se puede escribir como '\0'. Ahora bien, cuando usted usa la sintaxis mostrada en el ejemplo 1 no tiene que preocuparse por agregar el caracter NULL, ya que esto lo hace el compilador automáticamente.

La biblioteca string

Los compiladores de C, C++ dan soporte a la biblioteca de funciones <string.h>, misma que accesible por medio de la directiva #include <string.h>. No veremos en detalle todas las funciones contenidas en dicha biblioteca, y nos limitaremos a mostrar algunos ejemplos de ciertas funciones importantes.

strlen(): Obtener longitud de cadenas

Sintaxis: size_t strlen(const char *s);Comentarios: La función strlen() devuelve la longitud de la cadena s.

Ejemplo:

char *nombre = "Oscar E. Palacios";cout << strlen(nombre) << endl;

strcpy(): Copiar cadenas

Sintaxis: char *stpcpy(char *dest, const char *src);Comentarios: stpcpy copia la cadena src hacia dest, la función termina hasta haber encontrado en src el caracter de terminación null.

Ejemplo:

char *nombre = "Oscar E. Palacios";char copia[80];strcpy(copia, nombre);cout << copia << endl;

strcat(): Concatenar cadenas

Sintaxis: char *strcat(char *dest, const char *src);Comentarios: strcat agrega la cadena src a dest, la función termina hasta haber encontrado en src el caracter de terminación null.

Ejemplo:

char nombre[] = "Oscar E.";char copia[80] = " Palacios";strcat(copia, nombre);cout << copia << endl;

strlwr(): Convertir a minúsculas.

Sintaxis: char *strlwr(char *dest);Comentarios: strlwr convierte todos los caracteres alfabéticos ( 'A' .. 'Z' ) en dest a sus correspondientes caracteres alfabéticos ( 'a' .. 'z' ).

Ejemplo:

char nombre[] = "Oscar E. Palacios";strlwr(nombre);cout << nombre << endl;

strupr(): Convertir a mayúsculas.

Sintaxis: char *strupr(char *dest);Comentarios: strupr convierte todos los caracteres alfabéticos ( 'a' .. 'z' ) en dest a sus correspondientes caracteres alfabéticos ( 'A' .. 'Z' ).

strchr(): Buscar caracter ( hacia adelante )

Sintaxis: char *strchr(char *s, int c);Comentarios: strchr busca en s el caracter c. La busqueda se lleva a cabo desde el inicio hasta el final de s.Regreso: si la operación es exitosa strchr regresa un puntero hacia la primera ocurrencia de c en s, en caso contrario strchr regresa null.

Ejemplo:

char nombre[] = "Oscar E. Palacios";char *p; p = strchr(nombre, 'E');if (p) { cout << "nombre contiene a E" << endl; cout << "indice = " << (p - nombre) << endl; }else cout << "E no está en nombre" << endl;

strrchr(): Buscar caracter ( hacia atras )

Sintaxis: char *strrchr(char *s, int c);

Comentarios: strchr busca en s el caracter c. La busqueda se lleva a cabo desde el final hasta el inicio de s.Regreso: si la operación es exitosa strchr regresa un puntero hacia la última ocurrencia de c en s, en caso contrario strchr regresa null.

Ejemplo:

char nombre[] = "Oscar E. Palacios";char *p; p = strrchr(nombre, 'E');if (p) { cout << "nombre contiene a E" << endl; cout << "indice = " << (p - nombre) << endl; }else cout << "E no está en nombre" << endl;

strstr(): Buscar subcadena

Sintaxis: char *strstr(const char *s1, char *s2);Comentarios: strstr busca en s1 la subcadena s2. La busqueda se lleva a cabo desde el el inicio hasta el final de s1.Regreso: si la operación es exitosa strstr regresa un puntero hacia la primera ocurrencia de s2 en s1, en caso contrario strstr regresa null.

Ejemplo:

char s[] = "Un barco de tristeza";char *p; p = strstr(s, "barco");if (p) { cout << "barco está en s" << endl; cout << "indice = " << (p - s) << endl; }else cout << "barco no está en s" << endl;

Cadenas en C++

En la sección anterior descubrimos algunas funciones para trabajar con cadenas de caracteres al estilo de C estándar, si bien no está de más tener tal conocimiento tambien es cierto que C++ es un lenguaje de programacíón orientado al objeto, de tal manera que ciertos compiladores ( como el gcc, utilzado por Bloodshed Dev-C++ y otros tantos entornos de desarrolo ) dan soporte a la clase cstring, que no debe confundires con la <string.h>.

Nota: Bloodshed Dev-C++ es un IDE (Editor con Depurador Integrado) para programar en C++ en un ambiente gráfico para Windows, distibuido gratuitamente bajo licencia GPL GNU y usted puede encontrarlo aquí: www.bloodshed.net. Actualmente (febrero de 2008) se recomienda bajar la versión Dev-C++ 4.9.9.2.

Una de las ventajas que ofrece la clase cstring es que, a diferencia de las cadenas estándar, ésta posee la capacidad de crecer o disminuir su tamaño en tiempo de ejecución. Además, entre otras caracteristicas destacables, la clase string soporta operaciones de asignación tales como: =, +, +=, etc.; y de comparación tales como: ==, <=, etc.

Para tener una idea básica sobre las cadenas en C++ veamos el siguiente programa:

Nota: en el programa se debe de observar el uso del operador de asignación +=, algo que no es posible hacer con las cadenas estándar.

// Ejemplo: demostración de la clase string// Compilado y ejecutado con exito en Bloodshed Dev-C++#include <cstdlib>#include <iostream> using namespace std; int main(int argc, char *argv[]){ string s("Hola, "); s += "cómo estan ustedes..."; cout << s << endl; system("PAUSE"); return EXIT_SUCCESS;}

Un estudio exaustivo sobre la clase string requiere de un capítulo completo, ya que la misma, según el manual de referencia de C++, posee aproximadamente 33 métodos y unos 7 constructores; además de los atributos.

Arreglos en C++

Así como C++ da aternativas elegantes para la manipulación de cadenas de caracteres, también da el soporte para la manipulacíon de arreglos dinámicos. Este tema será ampliado en el capítulo Libreria de Plantillas Estándar STL, sin embargo para tener una idea de lo que vendrá mostraremos aquí un ejemplo sencillo en donde se usará la clase plantilla vector.

// Ejemplo: demostración de la clase vector// Compilado y ejecutado con exito en Bloodshed Dev-C++#include <cstdlib>#include <iostream>#include <vector> using namespace std; int main(int argc, char *argv[]){ // creación de un vector de enteros vector<int> v; // metiendo datos en el vector for (int x = 500; x<1000; x+=50) v.push_back(x); // desplegando los datos del vector for (int x = 0; x < v.size(); x++) cout << "v[" << x << "] = " << v[x] << endl; system("PAUSE"); return EXIT_SUCCESS;}

Métodos de ordenamiento y búsqueda

Ordenamiento de burbuja

El Ordenamiento de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Contenido

1 Descripción 2 Análisis

o 2.1 Rendimiento en casos óptimos o 2.2 Conejos y Tortugas (Yo-yos) (?)

3 En la práctica 4 Implementación 5 Véase también 6 Enlaces externos

Descripción

Una manera simple de expresar el ordenamiento de burbuja en pseudocódigo es la siguiente:

En este algoritmo se trata de ordenar una lista de valores: a, de n términos numerados del termino 0 al n-1, consta de dos bucles anidados uno con el índice i, que acota el recorrido de la burbuja en sentido inverso de 2 a n, y un segundo bucle con el índice j, con un recorrido desde 0 hasta n-i, para cada iteración del primer bucle, que indica el lugar de la burbuja.

La burbuja son dos términos de la lista seguidos, j y j+1, que se comparan, si el primero es menor que el segundo sus valores se intercambian.

Esta comparación se repite en el centro de los dos bucles, dando lugar a la postre a una lista ordenada, puede verse que el número de repeticiones sola depende de n, y no del orden de los términos, esto es si pasamos al algoritmo una lista ya ordenada, realizara todas las comparaciones exactamente igual que para una lista no ordenada, esta es una característica de este algoritmo, luego veremos una variante que evita este problema.

Para comprender el funcionamiento, veamos un ejemplo sencillo:

Partimos de una lista de números que hay que ordenar:

Podemos ver que la lista tiene cinco términos, luego:

El índice i hará un recorrido de 2 hasta n:

Que en este caso será de 2 a 5. Para cada uno de los valores de i, j tomara sucesivamente los valores de 0 hasta n-i:

Para cada valor de j, obtenido en ese orden, se compara el valor del índice j con el siguiente:

Si el termino j es menor, en su caso podría se mayor, que el termino j+1, los valores se permutan, en caso contrario se continúa con la iteración.

Para el caso del ejemplo, tenemos que:

Para la primera iteración del primer bucle:

y j tomara los valores de 0 hasta 3:

Cuando j vale 0, se comparan , el 55 y el 86, dado que 55 < 86 no se permutan el orden.

Ahora j vale 1 y se comparan el 86 y el 48 Como 86 > 48, se permutan, dando lugar a una nueva lista.

Se repite el proceso hasta que j valga 3, dando lugar a una lista parcialmente ordenada, podemos ver que el termino de mayor valor esta en el lugar más alto.

Ahora i vale 3, y j hará un recorrido de 0 a 2.

Primero j vale 0, se comparan , el 55 y el 48, como 55 > 48 se permutan dando lugar a la nueva lista.

Para j = 1 se compara el 55 con el 16 y se cambian de orden.

Para j = 2 se compara el 55 y el 82 y se dejan como están, finalizando el bucle con una lista mejor ordenada, puede verse que los dos valores más altos ya ocupan su lugar. No se ha realizado ninguna comparación con el termino cuarto, dado que ya se sabe que después del primer ciclo es el mayor de la lista.

El algoritmo consiste en comparaciones sucesivas de dos términos consecutivos, ascendiendo de abajo a arriba en cada iteración, como la ascensión de las burbujas de aire en el agua, de ahí el nombre del procedimiento, en la primera iteración el recorrido ha sido completo, en el segundo se ha dejado él ultimo termino, al tener ya el mayor de los valores, en los sucesivos sé ira dejando re realizar las ultimas comparaciones, como se puede ver.

Ahora ya i vale 4 y j recorrerá los valores de 0 a 1.

Cuando j vale 0, se comparan esto es el 48 y el 16 dado que 48 es mayor que 16 se permutan los valores, dando lugar a una lista algo más ordenada que la anterior, desde esta nueva ordenación, j pasa a valer 1, con lo que se comparan los términos el 48 y el 55 que quedan en el mismo orden.

En este caso la burbuja ha ascendido menos que en los casos anteriores, y la lista esta ya ordenada, pero el algoritmo tendrá que completarse, realizando una ultima iteración.

Hay que tener en cuenta que el bucle para realiza un número fijo de repeticiones y para finalizar tendrán que completarse, aun en el caso extremo, de que la lista estaría previamente ordenada.

Por ultimo i vale 5 y j solo puede vale 0, con lo que solo se realizara una comparación de el 16 y el 48, que ya están ordenados y se dejan igual.

Los bucles finalizan y también el procedimiento, dejando la lista ordenada.

Una variante que finaliza en caso de que la lista este ordenada, puede ser la siguiente, empleando un centinela ordenado, que detecta que no se ha modificado la lista en un recorrido de la burbuja, y que por tanto la lista ya esta ordenada, finalizando.

Análisis

Ejemplo del ordenamiento de burbuja ordenando una lista de números aleatorios.

Rendimiento en casos óptimos

El ordenamiento de burbuja tiene una complejidadΩ(n²). Cuando una lista ya está ordenada, a diferencia del ordenamiento por inserción que pasará por la lista una vez, y encontrará que no hay necesidad de intercambiar las posiciones de los elementos, el método de ordenación por burbuja está forzado a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadrática en el mejor de los casos, esto lo cataloga como el algoritmo mas ineficiente que existe aunque para muchos programadores sea el más sencillo de implementar.

Conejos y Tortugas (Yo-yos) (?)

La posición de los elementos en el ordenamiento de burbuja juegan un papel muy importante en la determinación del rendimiento. Los elementos mayores al principio de la lista son rápidamente movidos hacia abajo. En cambio, elementos menores en el fondo de la lista, se mueven a la parte superior muy lentamente. Esto llevó a nombrar estos elementos conejos y tortugas, respectivamente.

Varios esfuerzos se han realizado para eliminar las tortugas véase Exterminación y mejorar la velocidad del ordenamiento de burbuja, la cual será más redonda que nunca. El Ordenamiento por sacudida es un buen ejemplo, aunque aún mantiene, en el peor de los casos, una complejidad O (n2). El ordenamiento por combinación compara los elementos primero en pedazos grandes de la lista, moviendo tortugas extremadamente rápido, antes de proceder a pedazos cada vez más pequeños para alisar la lista. Su velocidad promedio es comparable a algoritmos rápidos (y complejos) como el ordenamiento rápido.

En la práctica

A pesar de que el ordenamiento de burbuja es uno de los algoritmos más sencillos de implementar, su orden O (n2) lo hace muy ineficiente para usar en listas que tengan más que un número reducido de elementos. Incluso entre los algoritmos de ordenamiento de orden O (n2), otros procedimientos como el Ordenamiento por inserción son considerados más eficientes.

Dada su simplicidad, el ordenamiento de burbuja es utilizado para introducir el concepto de algoritmo, o de algoritmo de ordenamiento para estudiantes de ciencias de la computación. Aunque algunos investigadores como Owen Astrachan han criticado al ordenamiento de burbuja y su popularidad en la educación de la computación, recomendando que ya no debe ser enseñado.

El ordenamiento de burbuja es asintóticamente equivalente, en tiempos de ejecución con el Ordenamiento por inserción en el peor de los casos, pero ambos algoritmos difieren principalmente en la cantidad de intercambios que son necesarios. Resultados experimentales, como los descubiertos por Astrachan han demostrado que el ordenamiento por inserción funcionan considerablemente mejor incluso con listas aleatorias. Por esta razón, muchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, utilizando en cambio el ordenamiento por inserción.

El ordenamiento de burbuja interactúa vagamente con el hardware de las CPU modernas. Requiere al menos el doble de escrituras que el ordenamiento por inserción, el doble de pérdidas de cache, y asintóticamente más

predicción de saltos. Varios experimentos, hechos por Astrachan, de ordenamiento de cadenas en Java, muestran que el ordenamiento de burbuja es 5 veces más lento que el ordenamiento por inserción y 40% más lento que el ordenamiento por selección.

Implementación

A continuación se muestra el Ordenamiento de burbuja en distintos lenguajes de programación:

C

void ordenamientoBurbuja(int v[], int util_v) { int temp, i, j;

for (i = 0; i < util_v - 1; i++) { for (j = i + 1; j < util_v; j++) {

if (v[i] > v[j]) { temp = v[i]; v[i] = v[j]; v[j] = temp; } }

}}

C++

template<typename _Ty>void bubble_sort(vector<_Ty> & v){

for (size_t i = 0; i < v.size() - 1; ++i){for (size_t j = i + 1; j < v.size(); ++j){

if (v[i] > v[j])swap(v[i], v[j]);

}}

}

C#

Public int[] OrdenarBurbuja(int[]x) { int t= x.Length, temp; for(int i=1 ; i< t ; i++) for(int j = t-1 ; j >= i; j--) { if(x[j] < x[j-1]) { temp= x[j]; x[j]= x[j-1]; x[j-1]= temp; } } }

Java

//Ordenamiento por Burbuja // by ramses2999 public static int[] OrdenarBurbuja(int[] n){ int temp; int t = n.length; for (int i = 1; i < t; i++) { for (int k = t- 1; k >= i; k--) {

if(n[k] < n[k-1]){ temp = n[k]; n[k] = n[k-1]; n[k-1]= temp; }//fin if }// fin 2 for }//fin 1 for return n; }//fin

Quicksort

Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote.

El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Contenido

1 Descripción del algoritmo o 1.1 Demostración

2 Optimización del algoritmo o 2.1 Técnicas de elección del pivote o 2.2 Técnicas de reposicionamiento o 2.3 Transición a otro algoritmo

3 Ejemplo 4 Implementaciones 5 Véase también 6 Referencias

Descripción del algoritmo

El algoritmo fundamental es el siguiente:

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos

los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).

En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el

array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.

En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

Demostración

Podríamos probar el orden de ejecución en el mejor caso de la siguiente manera:

Vamos a suponer que el número total de elementos a ordenar es potencia de dos, es decir, n = 2k. de aquí podemos ver que k = log2(n), donde k es el número de divisiones que realizará el algoritmo.

En la primera fase del algoritmo habrán n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.

En conclusión, el número total de comparaciones que hace el algoritmo es:

n + n + n + ..... + n = kn, donde k = log2(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log2n)

Optimización del algoritmo

Cabe destacar que de usarse en su versión recursiva las siguientes optimizaciones y sus desventajas no se ven vistas en el tiempo de ejecución del mismo manteniéndose, así el tiempo de ejecución planteado en un principio.

Técnicas de elección del pivote

El algoritmo básico Quicksort permite tomar cualquier elemento de la lista como pivote, dependiendo de la partición n que se elija, el algoritmo será más o menos eficiente.

Tomar un elemento cualquiera como pivote tiene la ventaja de no requerir ningún cálculo adicional, lo cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo tenga un orden de O(n²) para ciertas permutaciones de los elementos en la lista.

Otra opción puede ser recorrer la lista para saber de antemano qué elemento ocupará la posición central de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(n·log n). No obstante, el cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio.

La opción a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el último - y compararlos, eligiendo el valor del medio como pivote.

Técnicas de reposicionamiento

Una idea preliminar para ubicar el pivote en su posición final sería contar la cantidad de elementos menores que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda, para que pueda aplicarse la recursividad.

Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente:

Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).

Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas posiciones.

Repetir esto hasta que se crucen los índices. El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos

que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).

Transición a otro algoritmo

Como se comentó antes, el algoritmo quicksort ofrece un orden de ejecución O(n²) para ciertas permutaciones "críticas" de los elementos de la lista, que siempre surgen cuando se elige el pivote «a ciegas». La permutación concreta depende del pivote elegido, pero suele corresponder a secuencias ordenadas. Se tiene que la probabilidad de encontrarse con una de estas secuencias es inversamente proporcional a su tamaño.

Los últimos pases de quicksort son numerosos y ordenan cantidades pequeña de elementos. Un porcentaje medianamente alto de ellos estarán dispuestos de una manera similar al peor caso del algoritmo, volviendo a éste ineficiente. Una solución a este problema consiste en ordenar las secuencias pequeñas usando otro algoritmo. Habitualmente se aplica el algoritmo de inserción para secuencias de tamaño menores de 8-15 elementos.

Pese a que en secuencias largas de elementos la probabilidad de hallarse con una configuración de elementos "crítica" es muy baja, esto no evita que sigan apareciendo (a veces, de manera intencionada). El algoritmo introsort es una extensión del algoritmo quicksort que resuelve este problema utilizando heapsort en vez de quicksort cuando el número de recursiones excede al esperado.

Parámetros: o Se debe llamar a la función Quicksort desde donde quiera ejecutarseo Ésta llamará a colocar pivote para encontrar el valor del mismoo Se ejecutará el algoritmo Quicksort de forma recursiva a ambos lados del pivote

int colocar(int *v, int b, int t){ int i; int pivote, valor_pivote; int temp; pivote = b; valor_pivote = v[pivote]; for (i=b+1; i<=t; i++){ if (v[i] < valor_pivote){ pivote++; temp=v[i]; v[i]=v[pivote]; v[pivote]=temp; } } temp=v[b]; v[b]=v[pivote]; v[pivote]=temp; return pivote;} void Quicksort(int* v, int b, int t)

{ int pivote; if(b < t){ pivote=colocar(v, b, t); Quicksort(v, b, pivote-1); Quicksort(v, pivote+1, t); } }

Nota: Los tres parámetros de la llamada inicial a Quicksort serán array[0], 0, numero_elementos -1, es decir, si es un array de 6 elementos array[0], 0, 5

Ejemplo

En el siguiente ejemplo se marcan el pivote y los índices i y j con las letras p, i y j respectivamente.

Comenzamos con la lista completa. El elemento pivote será el 4:

5 - 3 - 7 - 6 - 2 - 1 - 4 p

Comparamos con el 5 por la izquierda y el 1 por la derecha.

5 - 3 - 7 - 6 - 2 - 1 - 4 i j p

5 es mayor que 4 y 1 es menor. Intercambiamos:

1 - 3 - 7 - 6 - 2 - 5 - 4i j p

Avanzamos por la izquierda y la derecha:

1 - 3 - 7 - 6 - 2 - 5 - 4 i j p

3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí.

1 - 3 - 7 - 6 - 2 - 5 - 4 i j p

7 es mayor que 4 y 2 es menor: intercambiamos.

1 - 3 - 2 - 6 - 7 - 5 - 4 i j p

Avanzamos por ambos lados:

1 - 3 - 2 - 6 - 7 - 5 - 4 iyj p

En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora intercambiamos lista[i] con lista[sup] (pasos 16-18):

1 - 3 - 2 - 4 - 7 - 5 - 6 p

Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo siguiente:

1 - 3 - 2

1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los índices termina el ciclo. Se intercambia lista[i] con lista[sup]:

1 - 2 - 3

El mismo procedimiento se aplicará a la otra sublista. Al finalizar y unir todas las sublistas queda la lista inicial ordenada en forma ascendente.

1 - 2 - 3 - 4 - 5 - 6 - 7

Implementaciones

El algoritmo de ordenamiento rápido (Quicksort) en:

Pseudocódigo

function quicksort(array) var list, less, greater if length(array) ≤ 1 return array seleccionar y eliminar un valor pivote pivot en el array for each x in array if x < pivot then añadir x a less else añadir x a greater return concadenar(quicksort(less), pivot, quicksort(greater))

C

int pivotar (int v[], int izq, int der){ int posicionPivote = (izq + der) / 2; int valorPivote = v[posicionPivote]; int indiceAlmacenamiento; swap (v, posicionPivote, der);//Se situal pivote al final del vector indiceAlmacenamiento = izq; for (int indiceLectura = izq; indiceLectura < der; indiceLectura++){ if (v[indiceLectura] <= valorPivote){ swap (v, indiceLectura, indiceAlmacenamiento); indiceAlmacenamiento++; } } swap (v, indiceAlmacenamiento, der); //Se coloca el pivote en su lugar. return indiceAlmacenamiento;} void quicksort (int v[], int izq, int der){ int pivote; if(izq < der){

pivote = pivotar (v, izq, der); //Esta operación coloca el pivote en su lugar. quicksort(v, izq, pivote-1); quicksort(v, pivote+1, der); } }

Otra en C. Trabaja sólo con punteros (no índices). Ordena enteros de menor a mayor. Pivot: El primero del vector.

void quicksort(int* izq, int* der) /*Se llama con: quicksort(&vector[0],&vector[n-1]);*/{

if(der<izq) return;int pivot=*izq;int* ult=der;int* pri=izq;

while(izq<der){

while(*izq<=pivot && izq<der+1) izq++;while(*der>pivot && der>izq-1) der--;if(izq<der) swap(izq,der);

}swap(pri,der);quicksort(pri,der-1);quicksort(der+1,ult);

} void swap(int* a, int* b){

int temp=*a;*a=*b;*b=temp;

}

Java

//Recibe un vector de enteros y el índice del primer y último elemento válido del mismo void ordenarQuicksort(int[] vector, int primero, int ultimo){ int i=primero, j=ultimo; int pivote=vector[(primero + ultimo) / 2]; int auxiliar; do{ while(vector[i]<pivote) i++; while(vector[j]>pivote) j--; if (i<=j){ auxiliar=vector[j]; vector[j]=vector[i]; vector[i]=auxiliar; i++; j--; } } while (i<=j); if(primero<j) ordenarQuicksort(vector,primero, j); if(ultimo>i) ordenarQuicksort(vector,i, ultimo); }

C#

void Quicksort(int[] v, int prim, int ult){

if (prim < ult)

{/* Selecciona un elemento del vector y coloca los menores que él a su izquierda y los mayores a su derecha */int p = Pivote(v, prim, ult, ult);

/* Repite el proceso para cada una de las particiones generadas en el paso anterior */Quicksort(v, prim, p - 1);Quicksort(v, p + 1, ult);

}} /* Implementación no clásica de la función Pivote. En lugar derecorrer el vector simultáneamente desde ambos extremos hasta elcruce de índices, se recorre desde el comienzo hasta el final */int Pivote(int[] v, int prim, int ult, int piv){

int p = v[piv];int j = prim;

// Mueve el pivote a la última posición del vectorIntercambia(v, piv, ult);

/* Recorre el vector moviendo los elementos menores o iguales que el pivote al comienzo del mismo */for (int i = prim; i < ult; i++){

if (v[i] <= p){

Intercambia(v, i, j);j++;

}}

// Mueve el pivote a la posición que le correspondeIntercambia(v, j, ult);

return j;

} void Intercambia(int[] v, int a, int b){

if (a != b){

int tmp = v[a];v[a] = v[b];v[b] = tmp;

}}

Python

def quicksort(datos, primero, ultimo): i = primero j = ultimo pivote = (datos[primero] + datos[ultimo]) / 2 while i < j: while datos[i] < pivote: i+=1 while datos[j] > pivote: j-=1 if i <= j: aux = datos[i] datos[i] = datos[j] datos[j] = aux i+=1 j-=1

if primero < j: datos = quicksort(datos, primero, j) if ultimo > i: datos = quicksort(datos, i, ultimo) return datos

Otra en Python

def qsort(list): try: x=list.pop() except: return [] return qsort(filter((lambda y: y<x), list)) + [x] + qsort(filter((lambda y: y>=x), list))

Haskell

qsort :: Ord a => [a] -> [a]qsort [] = []qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Otra en Haskell

qsort :: Ord a => [a] -> [a]qsort [] = []qsort (x:xs) = qsort elmts_lt_x ++ [x] ++ qsort elmts_greq_x

whereelmts_lt_x = [y | y <- xs, y < x]elmts_greq_x = [y | y <- xs, y >= x]

Asm

quicksort: push ebp mov ebp,esp push esi push ebx push ecx push edx mov ebx,dword[ebp + 12] mov ecx,dword[ebp + 16] cdq mov eax, ebx add eax, ecx push ecx mov ecx,2 div ecx pop ecx xchg edx,eax mov esi, [ebp + 8] mov edx,dword[esi + edx * 4] qs@L1: qs@L1@L1: cmp dword[esi + ebx * 4],edx jge qs@L1@L1@out inc ebx jmp qs@L1@L1 qs@L1@L1@out: qs@L1@L2: cmp dword[esi + ecx * 4],edx jle qs@L1@L2@out dec ecx jmp qs@L1@L2

qs@L1@L2@out: qs@L1@IF1: cmp ebx, ecx jg qs@L1@IF1@out mov eax, dword[esi + ebx * 4] xchg eax, dword[esi + ecx * 4] mov dword[esi + ebx * 4], eax inc ebx dec ecx qs@L1@IF1@out: cmp ebx,ecx jle qs@L1 qs@L1@out: qs@IF1: cmp dword[ebp + 12],ecx jge qs@IF1@out push ecx push dword[ebp + 12] push esi call quicksort qs@IF1@out: qs@IF2: cmp ebx, dword[ebp + 16] jge qs@IF2@out push dword[ebp + 16] push ebx push esi call quicksort qs@IF2@out: pop edx pop ecx pop ebx pop esi pop ebpretn 12

Prolog

quicksort([], []).quicksort([CABEZA | COLA], ORDENADO) :- partir(CABEZA, COLA, IZDA, DCHA), quicksort(IZDA, ORDENADO_IZDA), quicksort(DCHA, ORDENADO_DCHA), concatenar(ORDENADO_IZDA, [CABEZA | ORDENADO_DCHA], ORDENADO). partir(PIVOTE, [], [], []).partir(PIVOTE, [CABEZA | COLA], [CABEZA | IZDA], DCHA) :- CABEZA @=< PIVOTE, partir(PIVOTE, COLA, IZDA, DCHA).partir(PIVOTE, [CABEZA | COLA], IZDA, [CABEZA | DCHA]) :- CABEZA @> PIVOTE, partir(PIVOTE, COLA, IZDA, DCHA). concatenar([], LISTA, LISTA).concatenar([CABEZA | LISTA_1], LISTA_2, [CABEZA | LISTA_3]) :- concatenar(LISTA_1, LISTA_2, LISTA_3).

Ordenamiento ShellEl ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(nlog2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por

algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.

El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición

cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

Contenido

1 Ejemplo 2 Secuencia de espacios 3 Implementaciones

o 3.1 ActionScript o 3.2 C o 3.3 C# o 3.4 Java o 3.5 Perl o 3.6 Python o 3.7 Visual Basic

4 Referencias 5 Enlaces externos

Ejemplo

Considere un pequeño valor que está inicialmente almacenado en el final del vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios.

Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna. Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++).

Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas. Esto quedaría así:

13 14 94 33 8225 59 94 65 2345 27 73 25 3910

Entonces ordenamos cada columna, lo que nos da

10 14 73 25 2313 27 94 33 3925 59 94 65 8245

Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).

El Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo publicó en 1959. Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste." [1]

Secuencia de espacios

La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.

La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción, se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.

Quizás la propiedad más crucial del Shell sort es que los elementos permanecen k-ordenados incluso mientras el espacio disminuye. Se dice que un vector dividido en k subvectores esta k-ordenado si cada uno de esos subvectores esta ordenado en caso de considerarlo aislado. Por ejemplo, si una lista fue 5-ordenada y después 3-ordenada, la lista está ahora no sólo 3-ordenada, sino tanto 5-ordenada como 3-ordenada. Si esto no fuera cierto, el algoritmo desharía el trabajo que había hecho en iteraciones previas, y no conseguiría un tiempo de ejecución tan bajo.

Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de O(n2) (usando los incrementos de Shell que comienzan con 1/2 del tamaño del vector y se dividen por 2 cada vez), O(n3 / 2) (usando los incrementos de Hibbard de 2k − 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i) − 9(2i) + 1, o 4i + 1 + 3(2i) + 1), o O(nlog2n), y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación O(nlogn) en el peor caso del Shell sort permanece como una pregunta por resolver.

Implementaciones

El Shell sort se usa comúnmente en lenguajes de programación; esto es una implementación del algoritmo en C/C++ para ordenar un vector de enteros. La secuencia de incrementos usada en este ejemplo de código da un tiempo de ejecución O(n2) en el peor caso.

ActionScriptvar arrayOriginal:Array = new Array(2,5,6,8,10,2,3,64,23,76,43,27,75,33,23,45,67,89);trace("Array desordenado: "+arrayOriginal);

ordenamiento_shell(arrayOriginal,arrayOriginal.length); function ordenamiento_shell(arrayDesordenado:Array, tamano:uint){

var i:uint;var j:uint;var incremento:uint;var temp:uint;

incremento = tamano / 2;while (incremento>0){

for (i=incremento; i<tamano; i++){

j = i;temp = arrayDesordenado[i];while ((j >= incremento) && (arrayDesordenado[j-incremento] >

temp)){

arrayDesordenado[j] = arrayDesordenado[j - incremento];j = j - incremento;

}arrayDesordenado[j] = temp;

}incremento = incremento/2;

}trace("Array ordenado: "+arrayDesordenado);

}

Cvoid shell_sort(int A[], int size){ int i, j, incrmnt, temp; incrmnt = size/2; while (incrmnt > 0) { for (i=incrmnt; i < size; i++) { j = i; temp = A[i]; while ((j >= incrmnt) && (A[j-incrmnt] > temp)) { A[j] = A[j - incrmnt]; j = j - incrmnt; } A[j] = temp; } incrmnt /= 2; }}

C#using System;public class ShellSorter{ public void Sort(int [] list) { int j,inc; inc=list.length/2; while(inc>0) { for(int i=inc+1;i<list.length;i++) { j=i-inc; while(j>0) { if(list[j] > list[j+inc])

{ Swap(list[j],list[j+inc]); j=j-inc; } else { j=0; } } } inc=inc/2; } }}public class MainClass{ public static void Main() { int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}; ShellSorter sh=new ShellSorter(); sh.Sort(iArrary); for(int m=0;m<=13;m++) Console.WriteLine("{0}",iArrary[m]); }}

Javapublic static void shellSort(int[] a) { for ( int increment = a.length / 2; increment > 0; increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) { for (int i = increment; i < a.length; i++) { for (int j = i; j >= increment && a[j - increment] > a[j]; j -= increment) { int temp = a[j]; a[j] = a[j - increment]; a[j - increment] = temp; } } }}

Perlsub shellsort { my $array = shift; # Recibimos una referencia a un array my $i; # Índice del elemento a comparar my $j; # Índice del elemento actual a comparar my $shell; # Tamaño del incremento # Calculamos el valor del incremento for ( $shell = 1; $shell < @$array; $shell = 2 * $shell + 1 ) { ; } do { $shell = int( ( $shell - 1 ) / 2 ); # Para todos los elementos, elegidos con un incremento for ( $i = $shell; $i < @$array; $i++ ) { for ( $j = $i - $shell; $j >= 0 && $array->[ $j ] > $array->[ $j + $shell ]; $j -= $shell ) { # Intercambiamos valores @$array[ $j, $j + $shell ] = @$array[ $j + $shell, $j ]; } }

} while $shell > 1;}

Pythondef shellsort(a): def new_increment(a): i = int(len(a) / 2) yield i while i<>1: if i==2: i = 1 else: i = int(round(i/2.2)) yield i for increment in new_increment(a): for i in range(increment, len(a)): for j in range(i, increment-1, -increment): if a[j-increment] < a[j]: break a[j],a[j-increment] = a[j - increment],a[j] return a

Visual BasicSub Shell_Sort(ByRef V) 'debemos pasarle el arreglo(de enteros) desde el programa principal()Dim I, Medio, J, Temp As IntegerDim Ordenado As Boolean Medio = UBound(V) While (Medio > 0) Medio = Medio \ 2 Do Ordenado = True For J = 0 To UBound(V) - Medio ' se asume que el arreglo va de 0 a UBound(V) elementos I = J + Medio If V(J) > V(I) Then ' Se intercambian los elementos Temp = V(J) V(J) = V(I) V(I) = Temp Ordenado = False End If Next Loop Until Ordenado WendEnd Sub Sub principal()Dim Arr(99) As IntegerDim I As Integer For I = 0 To 99 Arr(I) = Int(Rnd() % 1000) ' Se llena el arreglo con números menores que 1000 Next I Call Shell_Sort(Arr)End Sub

Merge Sort

El método Quicksort divide la estructura en dos y ordena cada mitad recursivamente. El caso del MergeSort es el opuesto, es decir, en éste método de unen dos estructuras ordenadas para formar una sola ordenada correctamente.

Tiene la ventaja de que utiliza un tiempo proporcional a: n log (n), su desventaja radica en que se requiere de un espacio extra para el procedimiento.

Este tipo de ordenamiento es útil cuando se tiene una estructura ordenada y los nuevos datos a añadir se almacenan en una estructura temporal para después agregarlos a la estructura original de manera que vuelva a quedar ordenada.

Procedimiento MergeSort

/*recibe el arreglo a ordenar un índice l que indica el límite inferior del arreglo a ordenar y un índice r que indica el límite superior*/

void mergesort(int a[], int l, int r){

int i,j,k,m,b[MAX];if (r > l) {

m = (r+l) /2;mergesort(a, l, m);mergesort(a, m+1, r);for (i= m+1; i > l;i--)

b[i-1] = a[i-1];for (j= m; j < r;j++)

b[r+m-j] = a[j+1];for (k=l ; k <=r; k++)

if(b[i] < b[j]) a[k] = b[i++];else a[k] = b[j--];

}}

a = {a,s,o,r,t,i,n,g,e,x,a,m,p,l,e} {a,s, o,r, a,o,r,s, i,t, g,n, g,i,n,t, a,g,i,n,o,r,s,t, e,x, a,m, a,e,m,x, l,p, e,l,p} a,e,e,l,m,p,x}

a = {a,a,e,e,g,i,l,m,n,o,p,r,s,t,x}

Algoritmo de ordenamiento

En computación y matemáticas un algoritmo de ordenamiento recursivo es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.

Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y

familiar. Por ejemplo, BubbleSort fue analizado desde 1956.[1] Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, el ordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.

1 Clasificación 2 Estabilidad 3 Lista de algoritmos de ordenamiento 4 Referencias 5 Enlaces externos

Clasificación

Los algoritmos de ordenamiento se pueden clasificar de las siguientes maneras:

La más común es clasificar según el lugar donde se realice la ordenación o Algoritmos de ordenamiento interno : en la memoria del ordenador.o Algoritmos de ordenamiento externo : en un lugar externo como un disco duro.

Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas:

o Algoritmos de ordenación natural : Tarda lo mínimo posible cuando la entrada está ordenada.o Algoritmos de ordenación no natural : Tarda lo mínimo posible cuando la entrada está

inversamente ordenada.

Por estabilidad: un ordenamiento estable mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Por ejemplo, si una lista ordenada por fecha se reordena en orden alfabético con un algoritmo estable, todos los elementos cuya clave alfabética sea la misma quedarán en orden de fecha. Otro caso sería cuando no interesan las mayúsculas y minúsculas, pero se quiere que si una clave aBC estaba antes que AbC, en el resultado ambas claves aparezcan juntas y en el orden original: aBC, AbC. Cuando los elementos son indistinguibles (porque cada elemento se ordena por la clave completa) la estabilidad no interesa. Los algoritmos de ordenamiento que no son estables se pueden implementar para que sí lo sean. Una manera de hacer esto es modificar artificialmente la clave de ordenamiento de modo que la posición original en la lista participe del ordenamiento en caso de coincidencia.

Los algoritmos se distinguen por las siguientes características:

Complejidad computacional (peor caso, caso promedio y mejor caso) en términos de n, el tamaño de la lista o arreglo. Para esto se usa el concepto de orden de una función y se usa la notación O(n). El mejor comportamiento para ordenar (si no se aprovecha la estructura de las claves) es O(n log n). Los algoritmos más simples son cuadráticos, es decir O(n²). Los algoritmos que aprovechan la estructura de las claves de ordenamiento (p. ej. bucket sort) pueden ordenar en O(kn) donde k es el tamaño del espacio de claves. Como dicho tamaño es conocido a priori, se puede decir que estos algoritmos tienen un desempeño lineal, es decir O(n).

Uso de memoria y otros recursos computacionales. También se usa la notación O(n).

Estabilidad

Los algoritmos de ordenamiento estable mantienen un relativo preorden total. Esto significa que un algoritmo es estable solo cuando hay dos registros R y S con la misma clave y con R apareciendo antes que S en la lista original.

Cuando elementos iguales (indistinguibles entre sí), como números enteros, o más generalmente, cualquier tipo de dato en donde el elemento entero es la clave, la estabilidad no es un problema. De todas formas, se asume que los siguientes pares de números están por ser ordenados por su primer componente:

(4, 1) (3, 7) (3, 1) (5, 6)

En este caso, dos resultados diferentes son posibles, uno de los cuales mantiene un orden relativo de registros con claves iguales, y una en la que no:

(3, 7) (3, 1) (4, 1) (5, 6) (orden mantenido)(3, 1) (3, 7) (4, 1) (5, 6) (orden cambiado)

Los algoritmos de ordenamiento inestable pueden cambiar el orden relativo de registros con claves iguales, pero los algoritmos estables nunca lo hacen. Los algoritmos inestables pueden ser implementados especialmente para ser estables. Una forma de hacerlo es extender artificialmente el cotejamiento de claves, para que las comparaciones entre dos objetos con claves iguales sean decididas usando el orden de las entradas original. Recordar este orden entre dos objetos con claves iguales es una solución poco práctica, ya que generalmente acarrea tener almacenamiento adicional.

Ordenar según una clave primaria, secundaria, terciara, etc., puede ser realizado utilizando cualquier método de ordenamiento, tomando todas las claves en consideración (en otras palabras, usando una sola clave compuesta). Si un método de ordenamiento es estable, es posible ordenar múltiples ítems, cada vez con una clave distinta. En este caso, las claves necesitan estar aplicadas en orden de aumentar la prioridad.

Ejemplo: ordenar pares de números, usando ambos valores

(4, 1) (3, 7) (3, 1) (4, 6) (original)(4, 1) (3, 1) (4, 6) (3, 7) (después de ser ordenado por el segundo valor)(3, 1) (3, 7) (4, 1) (4, 6) (después de ser ordenado por el primer valor)

Por otro lado:

(3, 7) (3, 1) (4, 1) (4, 6) (después de ser ordenado por el primer valor)(3, 1) (4, 1) (4, 6) (3, 7) (después de ser ordenando por el segundo valor, el orden por el primer valor es perturbado)

Lista de algoritmos de ordenamiento

Algunos algoritmos de ordenamiento agrupados según estabilidad tomando en cuenta la complejidad computacional.

Estables

Nombre traducido Nombre original ComplejidadMemoria

Método

Ordenamiento de burbuja Bubblesort O(n²) O(1) Intercambio

Ordenamiento de burbuja Cocktail sort O(n²) O(1) Intercambio

bidireccional

Ordenamiento por inserción Insertion sort O(n²) O(1) Inserción

Ordenamiento por casilleros Bucket sort O(n) O(n)No comparativo

Ordenamiento por cuentas Counting sort O(n+k) O(n+k)No comparativo

Ordenamiento por mezcla Merge sort O(n log n) O(n) Mezcla

Ordenamiento con árbol binario Binary tree sort O(n log n) O(n) Inserción

Pigeonhole sort O(n+k) O(k)

Ordenamiento Radix Radix sort O(nk) O(n)No comparativo

Distribution sort O(n³) versión recursiva O(n²)

Gnome sort O(n²)

Inestables

Nombre traducido Nombre original ComplejidadMemoria

Método

Ordenamiento Shell Shell sort O(n1.25) O(1) Inserción

Comb sort O(n log n) O(1) Intercambio

Ordenamiento por selección Selection sort O(n²) O(1) Selección

Ordenamiento por montículos Heapsort O(n log n) O(1) Selección

Smoothsort O(n log n) O(1) Selección

Ordenamiento rápido QuicksortPromedio: O(n log n),peor caso: O(n²)

O(log n) Partición

Several Unique Sort

Promedio: O(n u),peor caso: O(n²);u=n; u = número único de registros

Cuestionables, imprácticos

Nombre traducido Nombre original ComplejidadMemoria

Método

Bogosort O(n × n!), peor: no termina

Pancake sortingO(n), excepto enmáquinas de Von Neumann

Randomsort

Algoritmo de búsquedaUn algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o la mejor movida en una partida de ajedrez.

La variante más simple del problema es la búsqueda de un número en un vector.

Búsqueda secuencial

Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del array hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del array. A continuación se muestra el pseudocódigo del algoritmo:

Datos de entrada: vec: vector en el que se desea buscar el dato tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive. dato: elemento que se quiere buscar.

Variables pos: posición actual en el array

pos = 0Mientras pos < tam: Si vec[pos] == dato devolver verdadero y/o pos, de lo contrario: pos = pos + 1Fin (Mientras)Devolver falso

Búsqueda binaria (dicotómica)

Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.

Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.

A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del array.

Datos de entrada: vec: vector en el que se desea buscar el dato tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive. dato: elemento que se quiere buscar.

Variables centro: subíndice central del intervalo inf: límite inferior del intervalo sup: límite superior del intervalo

inf = 0sup = tam-1

Mientras inf <= sup: centro = ((sup - inf) / 2) + inf // División entera: se trunca la fracción Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario: Si dato < vec[centro] entonces: sup = centro - 1 En caso contrario: inf = centro + 1Fin (Mientras)Devolver Falso

III. ListasObjetivo General: El alumno elaborará programas que integren el uso de recursividady definir estructuras de datos para generar alternativas de programación.

Listas

En Ciencias de la Computación, una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales 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 eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso 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 como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.

1 Historia 2 Tipos de Listas Enlazadas

o 2.1 Listas enlazadas lineales 2.1.1 Listas simples enlazadas 2.1.2 Lista Doblemente Enlazada

o 2.2 Listas enlazadas circulares 2.2.1 Listas enlazadas circulares simples 2.2.2 Lista Enlazada Doblemente Circular

o 2.3 Nodos Centinelas 3 Aplicaciones de las listas enlazadas 4 Ventajas

o 4.1 Listas Enlazadas vs. Vectores o Matrices o 4.2 Doblemente Enlazadas vs. Simples Enlazadas o 4.3 Circulares Enlazadas vs. Lineales Enlazadas o 4.4 Nodos Centinelas (header nodes)

5 Listas enlazadas usando Arrays de Nodos 6 Lenguajes soportados 7 Almacenamiento interno y externo 8 Agilización de la búsqueda 9 Estructuras de datos relacionadas 10 Implementaciones

o 10.1 Operaciones sobre listas enlazadas 10.1.1 Listas Enlazadas Lineales

10.1.1.1 Listas Simples Enlazadas 10.1.1.2 Listas Doblemente Enlazadas

10.1.2 Listas Enlazadas Circulares 10.1.2.1 Listas Enlazadas Doblemente Circulares

o 10.2 Listas enlazadas usando arrays de nodos o 10.3 Implementación de una lista enlazada en C o 10.4 Implementación de una lista enlazada en Maude o 10.5 Ejemplos de almacenamiento interno y externo

11 Referencias 12 Enlaces externos

Historia

Las listas enlazadas fueron desarrolladas en 1955-56 por Cliff Shaw y Herbert Simon en RAND Corporation como la principal estructura de datos para su Lenguaje de Procesamiento de la Información (IPL). IPL fue usado por los autores para desarrollar varios programas relacionados con la inteligencia artificial, incluida la Máquina de la Teoría General, el Solucionador de Problemas Generales, y un programa informático de ajedrez. Se publicó en IRE Transactions on Information Theory en 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 información de la Unesco) en 1959. El diagrama clásico 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 básicas a la inteligencia artificial, a la psicología del conocimiento humano y al procesamiento de las listas”.

El problema de los traductores del procesamiento natural del lenguaje condujo a Victor Yngve del Instituto Tecnológico de Massachusetts (MIT) a usar listas enlazadas como estructura de datos en su COMIT, lenguaje de programación para computadoras, que investigó en el campo de la Lingüística computacional. Un informe de este lenguaje, titulado “A programming language for mechanical translation” apareció en Mechanical Translation en 1958.

LISP, el principal procesador de listas, fue creado en 1958. Una de las mayores estructuras de datos de LISP es la lista enlazada.

En torno a los 60, la utilidad de las listas enlazadas y los lenguajes que utilizaban estas estructuras como su principal representación de datos estaba bien establecida. Bert Green del MIT Lincoln Laboratory, publicó un estudio titulado Computer languages for symbol manipulation en IRE Transaction on Human Factors in Electronics en marzo de 1961 que resumía las ventajas de las listas enlazadas. Un posterior artículo, A Comparison of list-processing computer languages by Bobrow and Raphael, aparecía en Communications of the ACM en abril de 1964.

Muchos sistemas operativos desarrollados por Technical Systems Consultants (originalmente de West Lafayette Indiana y después 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 localización del fichero mediante punteros. Los sistemas que utilizaban esta técnica incluían 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 máquinas System 360/370, usaba una lista doblemente enlazada para su catálogo de ficheros de sistema. La estructura del directorio era similar a Unix, donde un directorio podía contener ficheros u otros directorios que se podían extender a cualquier profundidad. Una utilidad fue creada para arreglar problemas del sistema después de un fallo desde las porciones modificadas del catálogo de ficheros que estaban a veces en memoria cuando ocurría el fallo. Los problemas eran detectados por comparación 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 básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

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

[editar] Lista Doblemente Enlazada

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anterior

En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque el uso de esta técnica no se suele utilizar.

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están 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 dirección 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 más 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 simples

Cada nodo tiene un enlace, similar al de las listas 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 después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo. [1]

Lista Enlazada Doblemente Circular

En 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 algún 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 Centinelas

A veces las listas enlazadas tienen un nodo centinela (también llamado falso nodo o nodo ficticio) al principio o al final de la lista, el cual no es usado para guardar datos. Su propósito 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.

Aplicaciones de las listas enlazadas

Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.

El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta practica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.

A veces, las listas enlazadas son usadas para implementar arrays asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar éstas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer ésta serie de datos

Ventajas

Como muchas opciones en programación y desarrollo, no existe un único método 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 un algunas de las ventajas más comunes que implican las estructuras de tipo lista. En general, teniendo una colección dinámica donde los elementos están siendo añadidos y eliminados frecuentemente e importa la localización de los nuevos elementos introducidos se incrementa el beneficio de las listas enlazadas.

[editar] Listas Enlazadas vs. Vectores o Matrices

Array Lista Enlazada

Indexado O(1) O(n)

Inserción / Eliminación al final O(1) O(1) or O(n)[2]

Inserción / Eliminación en la mitad

O(n) O(1)

Persistencia No Simples sí

Localización Buena Mala

Las listas enlazadas poseen muchas ventajas sobre los arrays. Los elementos se pueden insertar en una lista indefinidamente mientras que un array tarde o temprano se llenará ó necesitará ser redimensionado, una costosa operación 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 más listas – es decir, la lista acaba en la misma secuencia de elementos. De este modo, uno puede añadir 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 datos persistente.

Por otra parte, los arrays permiten acceso aleatorio mientras que las listas enlazadas sólo permiten acceso secuencial a los elementos. Las listas enlazadas simples, de hecho, solo pueden ser recorridas en una dirección. Esto hace que las listas sean inadecuadas para aquellos casos en los que es útil buscar un elementos por su índice rápidamente, como el heapsort. El acceso secuencial en los arrays también es más rápido 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 prácticas para listas de pequeños datos como caracteres o valores booleanos.

También 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 implementación de un programa que resuelva el problema de Josephus. Este problema consiste en un grupo de personas dispuestas en forma de círculo. Se empieza a partir de una persona predeterminadas y se cuenta n veces, la persona n-ésima se saca del círculo 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 más fácil 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 búsqueda de la n-ésima persona tan sólo basta con indicar el índice n para acceder a él resultando mucho más eficiente.

Doblemente Enlazadas vs. Simples Enlazadas

Las listas doblemente enlazadas requieren más espacio por nodo y sus operaciones básicas resultan más costosas pero ofrecen una mayor facilidad para manipular ya que permiten el acceso secuencial a lista en ambas direcciones. En particular, uno puede insertar o borrar un nodo en un número fijo de operaciones dando únicamente la dirección de dicho nodo (Las listas simples requieren la dirección del nodo anterior para insertar o suprimir correctamente). Algunos algoritmos requieren el acceso en ambas direcciones.

Circulares Enlazadas vs. Lineales Enlazadas

Las listas circulares son más útiles para describir estructuras circulares y tienen la ventaja de poder recorrer la lista desde cualquier punto. También permiten el acceso rápido al primer y último elemento por medio de un puntero simple.

Nodos Centinelas (header nodes)

La búsqueda común y los algoritmos de ordenación son menos complicados si se usan los llamados Nodos Centinelas o Nodos Ficticios, donde cada elemento apunta a otro elemento y nunca a nulo. El Nodo Centinela o Puntero Cabeza contiene, como otro, un puntero siguiente que apunta al que se considera como primer elemento de la lista . También contiene un puntero previo que hace lo mismo con el último elemento . El Nodo Centinela es definido como otro nodo en una lista doblemente enlazada , la asignación del puntero frente no es necesaria y los puntero anterior y siguiente estarán apuntando a sí mismo en ese momento. Si los punteros anterior y siguiente apuntan al Nodo Centinela la lista se considera vacía. En otro caso, si a la lista se le añaden elementos ambos puntero apuntarán a otros nodos. Estos Nodos Centinelas simplifican muchos las operaciones pero hay que asegurarse de que los punteros anterior y siguiente existen en cada momento. Como ventaja eliminan la necesidad de guardar la referencia al puntero del prinicipio de la lista y la posibilidad de asignaciones accidentales. Por el contrario, usan demasiado almacenamiento extra y resultan complicados en algunas operaciones.

Listas enlazadas usando Arrays de Nodos

Los lenguajes que no aceptan cualquier tipo de referencia pueden crear uniones reemplazando los punteros por índices de un array. La ventaja es de mantener un array de entradas , donde cada entrada tiene campos enteros indicando el índice del siguiente elemento del array. Puede haber nodos sin usarse. Si no hay suficiente espacio, pueden usarse arrays paralelos.

Entonces una lista enlazada puede ser construida, creado un array con esta estructura, y una variable entera para almacenar el índice del primer elemento. (ver en la sección de implementaciones).

Las utilidades de esta propuesta son:

La lista enlazada puede ser movida sobre la memoria y también ser rápidamente serializada para almacenarla en un disco o transferirla sobre una red.

Especialmente para una lista pequeña, los arrays indexados pueden ocupar mucho menos espacio que un conjunto de punteros.

La localidad de referencia puede ser mejorada guardando los nodos juntos en memoria y siendo reordenados periódicamente.

Algunas desventajas son:

Incrementa la complejidad de la implementación. Usar un fondo general de memoria deja más memoria para otros datos si la lista es más pequeña de lo

esperado ó si muchos nodos son liberados. El crecimiento de un array cuando está lleno no puede darse lugar (o habría que redimensionarlo)

mientras que encontrar espacio para un nuevo nodo en una lista resulta posible y más fácil.

Por estas razones, la propuesta se usa principalmente para lenguajes que no soportan asignación de memoria dinámica. Estas desventajas se atenúan también si el tamaño máximo de la lista se conoce en el momento en el que el array se crea.

Lenguajes soportados

Muchos lenguajes de programación tales como Lisp y Scheme tienen listas enlazadas simples ya construidas. En muchos lenguajes de programación, estas listas están construidas por nodos, cada uno llamado cons o celda cons. Las celdas cons tienen dos campos: el car, una referencia del dato al nodo, y el cdr, una referencia al siguiente nodo. Aunque las celdas cons pueden ser usadas para construir otras estructuras de datos, este es su principal objetivo.

En lenguajes que soportan tipos abstractos de datos o plantillas, las listas enlazadas ADTs o plantillas están disponibles para construir listas enlazadas. En otros lenguajes, las listas enlazadas son típicamente construidas usando referencias junto con el tipo de dato record.

En la sección de implementaciones hay un ejemplo completo en C y en Maude

Almacenamiento interno y externo

Cuando se construye una lista enlazada, nos enfrentamos a la elección de si almacenar los datos de la lista directamente en los nodos enlazados de la lista, llamado almacenamiento interno, o simplemente almacenar una referencia al dato, llamado almacenamiento externo. El almacenamiento interno tiene la ventaja de hacer accesos a los datos más eficientes, requiriendo menos almacenamiento global, teniendo mejor referencia de localidad, y simplifica la gestión de memoria para la lista (los datos son alojados y desalojados al mismo tiempo que los nodos de la lista).

El almacenamiento externo, por otro lado, tiene la ventaja de ser más genérico, en la misma estructura de datos y código máquina puede ser usado para una lista enlazada, no importa cual sea su tamaño o los datos. Esto hace que sea más fácil colocar el mismo dato en múltiples listas enlazadas. Aunque con el almacenamiento interno los mismos datos pueden ser colocados en múltiples listas incluyendo múltiples referencias siguientes en la estructura de datos del nodo, esto podría ser entonces necesario para crear rutinas separadas para añadir o borrar celdas basadas en cada campo. Esto es posible creando listas enlazadas de elementos adicionales que usen almacenamiento interno usando almacenamiento externo, y teniendo las celdas de las listas enlazadas adicionales almacenadas las referencias a los nodos de las listas enlazadas que contienen los datos.

En general, si una serie de estructuras de datos necesita ser incluida en múltiples listas enlazadas, el almacenamiento externo es el mejor enfoque. Si una serie de estructuras de datos necesitan ser incluidas en una sola lista enlazada, entonces el almacenamiento interno es ligeramente mejor, a no ser que un paquete genérico de listas genéricas que use almacenamiento externo esté disponible. Asimismo, si diferentes series de datos que

pueden ser almacenados en la misma estructura de datos son incluidos en una lista enlazada simple, entonces el almacenamiento interno puede ser mejor.

Otro enfoque que puede ser usado con algunos lenguajes implica tener diferentes estructuras de datos, pero todas tienen los campos iniciales, incluyendo la siguiente (y anterior si es una lista doblemente enlazada) referencia en la misma localización. Después de definir estructuras distintas para cada tipo de dato, una estructura genérica puede ser definida para que contenga la mínima cantidad de datos compartidos por todas las estructuras y contenidos al principio de las estructuras. Entonces las rutinas genéricas pueden ser creadas usando las mínimas estructuras para llevar a cabo las operaciones de los tipos de las listas enlazadas, pero separando las rutinas que pueden manejar los datos específicos. Este enfoque es usado a menudo en rutinas de análisis de mensajes, donde varios tipos de mensajes son recibidos, pero todos empiezan con la misma serie de campos, generalmente incluyendo un campo para el tipo de mensaje. Las rutinas genéricas son usadas para añadir nuevos mensajes a una cola cuando son recibidos, y eliminarlos de la cola en orden para procesarlos. El campo de tipo de mensaje es usado para llamar a la rutina correcta para procesar el tipo específico de mensaje.

En la sección implementaciones (en este mismo artículo) se expone código referente a este tema.

Hay que notar que cuando usamos almacenamiento externo, se necesita dar un paso extra para extraer la información del nodo y hacer un casting dentro del propio tipo del dato. Esto es porque ambas listas, de familias y miembros, son almacenadas en dos listas enlazadas usando la misma estructura de datos (nodo), y este lenguaje no tiene tipos paramétricos.

Si conocemos el número de familias a las que un miembro puede pertenecer en tiempo de compilación, el almacenamiento interno trabaja mejor. Si, sin embargo, un miembro necesita ser incluido en un número arbitrario de familias, sabiendo el número específico de familias solo en tiempo de ejecución, el almacenamiento externo será necesario.

Agilización de la búsqueda

Buscando un elemento específico en una lista enlazada, incluso si esta es ordenada, normalmente requieren tiempo O (n) (búsqueda lineal). Esta es una de las principales desventajas de listas enlazadas respecto a otras estructuras. Además algunas de las variantes expuestas en la sección anterior, hay numerosas vías simples para mejorar el tiempo de búsqueda.

En una lista desordenada, una forma simple para decrementar el tiempo de búsqueda medio es el mover al frente de forma heurística, que simplemente mueve un elemento al principio de la lista una vez que es encontrado. Esta idea, útil para crear cachés simples, asegura que el ítem usado más recientemente es también el más rápido en ser encontrado otra vez.

Otro enfoque común es indizar una lista enlazada usando una estructura de datos externa más eficiente. Por ejemplo, podemos construir un árbol rojo-negro o una tabla hash cuyos elementos están referenciados por los nodos de las listas enlazadas. Pueden ser construidos múltiples índices en una lista simple. La desventaja es que estos índices puede necesitar ser actualizados cada vez que uno nodo es añadido o eliminado (o al menos, antes que el índice sea utilizado otra vez).

Estructuras de datos relacionadas

Tanto las pilas como las colas son a menudo implementadas usando listas enlazadas, y simplemente restringiendo el tipo de operaciones que son soportadas.

La skip list, o lista por saltos, es una lista enlazada aumentada con capas de punteros para saltos rápidos sobre grandes números de elementos, y descendiendo hacía la siguiente capa. Este proceso continúa hasta llegar a la capa inferior, la cual es la lista actual.

Un árbol binario puede ser visto como un tipo de lista enlazada donde los elementos están enlazados entre ellos mismos de la misma forma. El resultado es que cada nodo puede incluir una referencia al primer nodo de una o dos listas enlazadas, cada cual con su contenido, formando así los subárboles bajo el nodo.

Una lista enlazada desenrollada es una lista enlazada cuyos nodos contiene un array de datos. Esto mejora la ejecución de la caché, siempre que las listas de elementos estén contiguas en memoria, y reducen la sobrecarga de la memoria, porque necesitas menos metadatos para guardar cada elemento de la lista.

Una tabla hash puede usar listas enlazadas para guardar cadenas de ítems en la misma posición de la tabla hash.

Implementaciones

Aquí se expone el código necesario para complementar el artículo a fin de poder realizar una lectura ágil sobre el artículo y a su vez quien necesite el código pueda fácilmente encontrar el mismo si está contenido.

Operaciones sobre listas enlazadas

Cuandos se manipulan listas enlazadas, hay que tener cuidado con no usar valores que hayamos invalidado en asignaciones anteriores. Esto hace que los algoritmos de insertar y borrar nodos en las listas sean algo especiales. A continuación se expone el pseudocódigo para añadir y borrar nodos en listas enlazadas simples, dobles y circulares.

Listas Enlazadas Lineales

Listas Simples Enlazadas

Nuestra estructura de datos tendrá dos campos. Vamos a mantener la variables PrimerNodos que siempre apunta al primer nodo de tal lista, ó nulo para la lista vacía.

record Node { data // El dato almacenado en el nodo next // Una referencia al nodo siguiente, nulo para el último nodo } record List { Node PrimerNodo // Apunta al primer nodo de la lista; nulo para la lista vacía }

El recorrido en una lista enlazada es simple, empezamos por el primer nodo y pasamos al siguiente hasta que la lista llegue al final.

node := list.PrimerNodo while node not null { node := node.next }

El siguiente código inserta un elemento a continuación de otro en una lista simple. El diagrama muestra como funciona.

function insertAfter(Node node, Node newNode) { newNode.next := node.next node.next := newNode }

Insertar al principio de una lista requiere una función por separado. Se necesita actualizar PrimerNodo.

function insertBeginning(List list, Node newNode) { newNode.next := list.firstNode list.firstNode := newNode }

De forma similar, también tenemos funciones para borrar un nodo dado ó para borrar un nodo del principio de la lista. Ver diagrama.

function removeAfter(Node node) { obsoleteNode := node.next node.next := node.next.next destroy obsoleteNode } function removeBeginning(List list) { obsoleteNode := list.firstNode list.firstNode := list.firstNode.next destroy obsoleteNode }

Advertimos que BorrarPrincipio pone PrimerNodo a nulo cuando se borra el último elemento de la lista. Adjuntar una lista enlazada a otra puede resultar ineficiente a menos que se guarde una referencia a la cola de la lista, porque si no tendríamos que recorrer la lista en orden hasta llegar a la cola y luego añadir la segunda lista.

Listas Doblemente Enlazadas

Con estas listas es necesario actualizar muchos más punteros pero también se necesita menos información porque podemos usar un puntero para recorrer hacia atrás y consultar elementos. Se crean nuevas operaciones y elimina algunos casos especiales. Añadimos el campo anterior a nuestros nodos, apuntando al elemento anterior, y UltimoNodo a nuestra estructura, el cual siempre apunta al último elemento de la lista. PrimerNodo y UltimoNodo siempre están a nulo en la lista vacía.

record Node { data // El dato almacenado en el nodo next // Una referencia al nodo siguiente, nulo para el último nodo prev // Una referencia al nodo anterior, nulo para el primer nodo } record List { Node firstNode // apunta al primer nodo de la lista; nulo para la lista vacía Node lastNode // apunta al último nodo de la lista; nulo para la lista vacía }

Formas de recorrer la lista:

Hacia Delante

node := list.firstNode while node ≠ null <do something with node.data> node := node.next

Hacia Atrás

node := list.lastNode while node ≠ null <do something with node.data> node := node.prev

Estas funciones simétricas añaden un nodo después o antes de uno dado.

function insertAfter(List list, Node node, Node newNode) newNode.prev := node newNode.next := node.next if node.next = null node.next := newNode list.lastNode := newNode else node.next.prev := newNode node.next := newNode function insertBefore(List list, Node node, Node newNode) newNode.prev := node.prev newNode.next := node if node.prev is null node.prev := newNode list.firstNode := newNode else node.prev.next := newNode node.prev := newNode

También necesitamos una función para insertar un nodo al comienzo de una lista posiblemente vacía.

function insertBeginning(List list, Node newNode) if list.firstNode = null list.firstNode := newNode list.lastNode := newNode newNode.prev := null newNode.next := null else insertBefore (list, list.firstNode, newNode)

Una función simétrica que inserta al final:

function insertEnd(List list, Node newNode) if list.lastNode = null insertBeginning (list, newNode) else insertAfter (list, list.lastNode, newNode)

Borrar un nodo es fácil, solo requiere usar con cuidado firstNode y lastNode.

function remove(List list, Node node) if node.prev = null list.firstNode := node.next else node.prev.next := node.next if node.next = null list.lastNode := node.prev else node.next.prev := node.prev destroy node

Una consecuencia especial de este procedimiento es que borrando el último elemento de una lista se ponen PrimerNodo y UltimoNodo a nulo, habiendo entonces un problema en una lista que tenga un único elemento.

Listas Enlazadas Circulares

Estas pueden ser simples o doblemente enlazadas. En una lista circular todos los nodos están enlazados como un círculo, sin usar nulo. Para listas con frente y final (como una cola), se guarda una referencia al último nodo de la lista. El siguiente nodo después del último sería el primero de la lista. Los elementos se pueden añadir por el final y borrarse por el principio en todo momento. Ambos tipos de listas circulares tienen la ventaja de poderse recorrer completamente empezando desde cualquier nodo. Esto nos permite normalmente evitar el uso de PrimerNodo y UltimoNodo, aunque si la lista estuviera vacía necesitaríamos un caso especial, como una variables UltimoNodo que apunte a algún nodo en la lista o nulo si está vacía. Las operaciones para estas listas simplifican el insertar y borrar nodos en una lista vacía pero introducen casos especiales en la lista vacía.

Listas Enlazadas Doblemente Circulares

Asumiendo que someNodo es algún nodo en una lista no vacía, esta lista presenta el comienzo de una lista con someNode.

Hacia Delante

node := someNode do do something with node.value node := node.next while node != someNode

Hacia Atrás

node := someNode do do something with node.value node := node.prev while node := someNode

Esta función inserta un nodo en una lista enlazada doblemente circular después de un elemento dado:

function insertAfter(Node node, Node newNode) newNode.next := node.next newNode.prev := node node.next.prev := newNode node.next := newNode

Para hacer "insertBefore", podemos simplificar "insertAfter (node.prev, newNode)". Insertar un elemento en una lista que puede estar vacía requiere una función especial.

function insertEnd(List list, Node node) if list.lastNode = null node.prev := node node.next := node else insertAfter (list.lastNode, node) list.lastNode := node

Para insertar al principio simplificamos "insertAfter (list.lastNode, node)".

function remove(List list, Node node) if node.next = node list.lastNode := null else node.next.prev := node.prev

node.prev.next := node.next if node = list.lastNode list.lastNode := node.prev; destroy node

Como una lista doblemente enlazada, "removeAfter" y "removeBefore" puede ser implementada con "remove (list, node.prev)" y "remove (list, node.next)".

Listas enlazadas usando arrays de nodos

Previamente se crea una estructura que contiene los apuntadores:

record Entry { integer next; // índice de la nueva entrada en el array integer prev; // entrada previa string name; real balance; }

Y finalmente se declara el array: integer listHead;

Entry Records[1000];

Implementación de una lista enlazada en C

Las listas enlazadas son típicamente construidas usando referencias junto con el tipo de dato record

#include <stdio.h> /* for printf */#include <stdlib.h> /* for malloc */ typedef struct ns {

int data;struct ns *next;

} node; node *list_add(node **p, int i) { /* algunos compiladores no requieren un casting del valor del retorno para malloc */ node *n = (node *)malloc(sizeof(node)); if (n == NULL) return NULL; n->next = *p; *p = n; n->data = i; return n;} void list_remove(node **p) { /* borrar cabeza*/ if (*p != NULL) { node *n = *p;

*p = (*p)->next;free(n);

}} node **list_search(node **n, int i) { while (*n != NULL) { if ((*n)->data == i) { return n; } n = &(*n)->next; } return NULL;} void list_print(node *n) {

if (n == NULL) { printf("lista esta vacía\n"); } while (n != NULL) { printf("print %p %p %d\n", n, n->next, n->data); n = n->next; }} int main(void) { node *n = NULL; list_add(&n, 0); /* lista: 0 */ list_add(&n, 1); /* lista: 1 0 */ list_add(&n, 2); /* lista: 2 1 0 */ list_add(&n, 3); /* lista: 3 2 1 0 */ list_add(&n, 4); /* lista: 4 3 2 1 0 */ list_print(n); list_remove(&n); /* borrar primero(4) */ list_remove(&n->next); /* borrar nuevo segundo (2) */ list_remove(list_search(&n, 1)); /* eliminar la celda que contiene el 1 (primera) */ list_remove(&n->next); /* eliminar segundo nodo del final(0)*/ list_remove(&n); /* eliminar ultimo nodo (3) */ list_print(n); return 0;}

Implementación de una lista enlazada en Maude

fmod LISTA-GENERICA {X :: TRIV} is protecting NAT .

*** tipos sorts ListaGenNV{X} ListaGen{X} . subsort ListaGenNV{X} < ListaGen{X} .

*** generadores op crear : -> ListaGen{X} [ctor] . op cons : X$Elt ListaGen{X} -> ListaGenNV{X} [ctor] .

*** constructores op _::_ : ListaGen{X} ListaGen{X} -> ListaGen{X} [assoc id: crear ] . *** concatenacion op invertir : ListaGen{X} -> ListaGen{X} . op resto : ListaGenNV{X} -> ListaGen{X} .

*** selectores op primero : ListaGenNV{X} -> X$Elt . op esVacia? : ListaGen{X} -> Bool . op longitud : ListaGen{X} -> Nat .

*** variables vars L L1 L2 : ListaGen{X} . vars E E1 E2 : X$Elt .

*** ecuaciones

eq esVacia?(crear) = true .eq esVacia?(cons(E, L)) = false .

eq primero(cons(E, L)) = E . eq resto(cons(E, L)) = L .

eq longitud(crear) = 0 .eq longitud(cons(E, L)) = 1 + longitud(L) . eq cons(E1, L1) :: cons(E2, L2) = cons(E1, L1 :: cons(E2, L2)) .

eq invertir(crear) = crear .eq invertir(cons(E, L)) = invertir(L) :: cons(E, crear) .

endfm

Ejemplos de almacenamiento interno y externo

Suponiendo que queremos crear una lista enlazada de familias y sus miembros. Usando almacenamiento interno, la estructura podría ser como la siguiente:

record member { // miembro de una familia member next string firstName integer age } record family { // // la propia familia family next string lastName string address member members // de la lista de miembros de la familia }

Para mostrar una lista completa de familias y sus miembros usando almacenamiento interno podríamos escribir algo como esto:

aFamily := Families // comienzo de la lista de familias while aFamily ≠ null { // bucle a través de la lista de familias print information about family aMember := aFamily.members // coger cabeza de esta lista de miembros de esta familia while aMember ≠ null { //bucle para recorrer la lista de miembros print information about member aMember := aMember.next } aFamily := aFamily.next }

Usando almacenamiento externo, nosotros podríamos crear las siguientes estructuras:

record node { // estructura genérica de enlace node next pointer data // puntero genérico del dato al nodo } record member { // estructura de una familia string firstName integer age }

record family { // estructura de una familia string lastName string address node members // cabeza de la lista de miembros de esta familia }

Para mostrar una lista completa de familias y sus miembros usando almacenamiento externo, podríamos escribir:

famNode := Families // comienzo de la cabeza de una lista de familias while famNode ≠ null { // bucle de lista de familias aFamily = (family) famNode.data // extraer familia del nodo print information about family memNode := aFamily.members // coger lista de miembros de familia while memNode ≠ null { bucle de lista de miembros aMember := (member) memNode.data // extraer miembro del nodo print information about member memNode := memNode.next } famNode := famNode.next }

IV. PilasObjetivo General: El alumno elaborará programas que integren el uso de recursividady definir estructuras de datos para generar alternativas de programación.

Pila (informática)Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura.

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

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención 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 analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:

Evaluación de expresiones en notación postfija (notación polaca inversa). Reconocedores sintácticos de lenguajes independientes del contexto Implementación de recursividad.

Contenido

1 Historia 2 Pila de llamadas 3 Pila como tipo abstracto de datos

o 3.1 Operaciones o 3.2 Implementación

3.2.1 EN PYTHON 3.2.2 EN MAUDE 3.2.3 PILA CON PUNTEROS EN C++

o 3.3 Estructuras de datos relacionadas 4 Pilas Hardware 5 Arquitectura básica de una pila 6 Soporte de Hardware 7 Soporte de Software 8 Expresión de evaluación y análisis sintáctico

o 8.1 Tiempo de ejecución de la gestión de memoria o 8.2 Solucionar problemas de búsqueda

9 Seguridad 10 Véase también

Historia

El método de pila para la evaluación de expresiones fue propuesto en 1955 y dos años después patentado por Fiedrich L.Bauer, quién recibió en 1988 el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.

Pila de llamadas

La pila de llamadas es un segmento de memoria que utiliza esta estructura de datos para almacenar información sobre las llamadas a subrutinas actualmente en ejecución en un programa en proceso.

Cada vez que una nueva subrutina es llamada, se apila una nueva entrada con información sobre ésta tal como sus variables locales. En especial, se almacena aquí el punto de retorno al que regresar cuando esta subrutina termine (para volver a la subrutina anterior y continuar su ejecución después de esta llamada)..

Pila como tipo abstracto de datos

A modo de resumen tipo de datos, la pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). 'Push' añade 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. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primera placa es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas. A medida que la placa superior se elimina de la pila, la segunda placa se convierte en la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: En primer lugar la última salida es un principio, la segunda es que el contenido de la pila está oculto. Sólo la placa de la parte superior es visible, por lo que para ver lo que hay en la tercera placa, el primer y segundo platos tendrán que ser retirados.

Operaciones

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

Crear: 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) Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.

Implementación

Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O(1) las operaciones también son fáciles de satisfacer con un array o con listas enlazadas simples.

La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.

Estos son ejemplos sencillos de una pila con las operaciones descritas anteriormente (pero no hay comprobación de errores).

EN PYTHONclass Stack(object): def __init__(self): self.stack_pointer = None def push(self, element): self.stack_pointer = Node(element, self.stack_pointer) def pop(self): e = self.stack_pointer.element self.stack_pointer = self.stack_pointer.next return e def peek(self): return self.stack_pointer.element

def __len__(self): i = 0 sp = self.stack_pointer while sp: i += 1 sp = sp.next return i class Node(object): def __init__(self, element=None, next=None): self.element = element self.next = next if __name__ == '__main__': # small use example s = Stack() [s.push(i) for i in xrange(10)] print [s.pop() for i in xrange(len(s))]

EN MAUDE

La PilaNV es la pila no vacía, que diferenciamos de la pila normal a la hora de tomar en cuenta errores. El elemento X representa el tipo de valor que puede contener la pila: entero, carácter, registro....

fmod PILA-GENERICA {X :: TRIV} is sorts Pila{X} PilaNV{X}. subsorts PilaNV{X} < Pila{X}. ***generadores: op crear: -> Pila {X} [ctor]. op apilar : X$Elt Pila{X} -> PilaNV{X} [ctor]. ***constructores op desapilar : Pila{X} -> Pila{X}. ***selectores op cima : PilaNV{X} -> X$Elt. ***variables var P : Pila{X}. var E : X$Elt. ***ecuaciones eq desapilar (crear) = crear. eq desapilar(apilar(E, P)) = P. eq cima(apilar(E, P)) = E.endfm

PILA CON PUNTEROS EN C++#include<stdio.h>#include<conio.h> #define TAM 6#define MAX TAM-1 typedef struct{ int tope; int item[TAM];}pila; int full(pila *);int empty(pila *);

void push(pila *, int);void pop(pila *,int *); void main(){ pila p,t; int dato,opc,elemento,flag=0; p.tope=0; do { clrscr(); printf("\nMENU-PILA"); printf("\n1-> Insertar elemento"); printf("\n2-> Eliminar elemento"); printf("\n3-> Eliminar elemento X"); printf("\n4-> Visualizar"); printf("\n5-> Salir"); printf("\n\nDe su opci¢n : "); scanf("%d",&opc); switch(opc) {

case 1: if(!full(&p)) // si pila no esta llena { printf("\nDe el elemento a insertar: "); scanf("%d",&dato); push(&p,dato); printf("\nElemento insertado..."); } else { printf("\nERROR: Pila llena"); } break;

case 2: if(!empty(&p)) { pop(&p,&dato); printf("\nEl elemento eliminado es %d",dato); } else { printf("\nERROR: Pila vac¡a"); } break;

case 3: if(!empty(&p)) { printf("eliminar elemento seleccionado: "); scanf("%d",&elemento);

if(p.tope != 1){ t.tope=0; do { pop(&p,&dato);

if (dato != elemento) { push(&t,dato); }

}while(!empty(&p));

do {

pop(&t,&dato); push(&p,dato);

}while(!empty(&t)); } else if(dato == elemento){pop(&p,&dato);}

else {printf("el elemento no se encuentra en la pila");} } else { printf("\nERROR: Pila vac¡a"); } break;

case 4: if(!empty(&p)) { t.tope=0; do {

pop(&p,&dato); printf("\n%d",dato); push(&t,dato);

}while(!empty(&p)); do {

pop(&t,&dato); push(&p,dato);

}while(!empty(&t)); } else { printf("\nERROR: Pila vac¡a"); } break; case 5: flag=1; break; case 6: flag=0; break;

default: printf("\nOpci¢n no v lida...");

} if(!flag) {

printf("\n\nPresione una tecla para continuar..."); getch();

} }while(!flag); } int full(pila *p){ return(p->tope==MAX);} int empty(pila *p){ return(p->tope==0);} void push(pila *p,int dato){ if(!full(p)) { (p->tope)++; p->item[p->tope]=dato; //elemento[1]=dato }

else printf("\nOVERFLOW");} void pop(pila *p,int *dato){ if(!empty(p)) { *dato=p->item[p->tope]; (p->tope)--; } else printf("\nUNDERFLOW"); }

Estructuras de datos relacionadas

El tipo base de la estructura FIFO (el primero en entrar es el primero en salir)es la cola, y la combinación de las operaciones de la pila y la cola es proporcionado por el deque. Por ejemplo, el cambio de una pila en una cola en un algoritmo de búsqueda puede cambiar el algoritmo de búsqueda en primera profundidad (en inglés, DFS) por una búsqueda en amplitud (en inglés, BFS). Una pila acotada es una pila limitada a un tamaño máximo impuesto en su especificación.

Pilas Hardware

Un uso muy común de las pilas a nivel de arquitectura hardware es la asignación de memoria.

Arquitectura básica de una pila

Una pila típica es un área de la memoria de los computadores con un origen fijo y un tamaño variable. Al principio, el tamaño de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la más reciente localización en la pila; cuando la pila tiene un tamaño de cero, el puntero de pila de puntos en el origen de la pila.

Las dos operaciones aplicables a todas las pilas son:

Una operación apilar, en el que un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la dirección en el puntero de pila se ajusta por el tamaño de los datos de partida.

Una operación desapilar: un elemento de datos en la ubicación actual apuntado por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamaño de los datos de partida.

Hay muchas variaciones en el principio básico de las operaciones de pila. Cada pila tiene un lugar fijo en la memoria en la que comienza. Como los datos se añadirán 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 aplicación concreta).

Por ejemplo, una pila puede comenzar en una posición 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 número limitado de direcciones, ya sea por encima o por debajo del origen (dependiendo de la dirección 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 dirección 1000 y la pila crece hacia abajo (hacia las direcciones 999, 998, y así sucesivamente), el puntero de pila nunca debe ser incrementado más allá de 1000 (para 1001, 1002, etc.) Si un desapilar operación en la pila hace que el puntero de pila se deje atrás el origen de la pila, una pila se produce desbordamiento. Si una operación de apilar hace

que el puntero de pila incremente o decremente más allá del máximo 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 máximo elemento de la pila en una posición fija, o creciente, de izquierda a derecha, por lo que el máximo elemento se convierte en el máximo a "la derecha". Esta visualización 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 posición, la segunda a la primera y la tercera a la segunda. Aquí hay dos equivalentes visualizaciones de este proceso:

Manzana Plátano Plátano ==rotar a la derecha==> Fresa Fresa Manzana

Fresa Manzana Plátano ==rotar a la izquierda==> Fresa Manzana Plátano

Una pila es normalmente representada en los ordenadores por un bloque de celdas de memoria, con los "de abajo" en una ubicación fija, y el puntero de pila de la dirección actual de la "cima" de células de la pila. En la parte superior e inferior se utiliza la terminología con independencia de que la pila crece realmente a la baja de direcciones de memoria o direcciones de memoria hacia mayores.

Apilando un elemento en la pila,se ajusta el puntero de pila por el tamaño de elementos (ya sea decrementar o incrementar, en función de la dirección en que crece la pila en la memoria), que apunta a la próxima celda, y copia el nuevo elemento de la cima en área de la pila. Dependiendo de nuevo sobre la aplicación exacta, al final de una operación de apilar, el puntero de pila puede señalar a la siguiente ubicación no utilizado en la pila, o tal vez apunte al máximo elemento de la pila. Si la pila apunta al máximo elemento de la pila, el puntero de pila se actualizará antes de que un nuevo elemento se apile, si el puntero que apunta a la próxima ubicación disponible en la pila, que se actualizará después de que el máximo elemento se apile en la pila.

Desapilando es simplemente la inversa de apilar. El primer elemento de la pila es eliminado y el puntero de pila se actualiza, en el orden opuesto de la utilizada en la operación de apilar.

Soporte de Hardware

Muchas CPUs tienen registros que se pueden utilizar como punteros de pila. Algunos, como el Intel x86, tienen instrucciones especiales que implícitamente el uso de un registro dedicado a la tarea de ser un puntero de pila. Otros, como el DEC PDP-11 y de la familia 68000 de Motorola tienen que hacer frente a los modos de hacer posible la utilización de toda una serie de registros como un puntero de pila. La serie Intel 80x87 numérico de coprocessors tiene un conjunto de registros que se puede acceder ya sea como una pila o como una serie de registros numerados. Algunos microcontroladores, por ejemplo algunos PICs, tienen un fondo fijo de pila que no es directamente accesible. También hay una serie de microprocesadores que aplicar una pila directamente en el hardware:

Computer vaqueros MuP21 Harris RTX línea Novix NC4016

Muchas pilas basadas en los microprocesadores se utilizan para aplicar el lenguaje de programación Forth en el nivel de microcódigo. Pila también se utilizaron como base de una serie de mainframes y miniordenadores. Esas máquinas fueron llamados pila de máquinas, el más famoso es el Burroughs B5000

Soporte de Software

En programas de aplicación escrito en un lenguaje de alto nivel, una pila puede ser implementada de manera eficiente, ya sea usando vectores o listas enlazadas. En LISP no hay necesidad de aplicar la pila, ya que las funciones apilar y desapilar están disponibles para cualquier lista. Adobe PostScript también está diseñada en torno a una pila que se encuentra directamente visible y manipuladas por el programador. El uso de las pilas está muy presente en el desarrollo de software por ello la importancia de las pilas como tipo abstracto de datos.

Expresión de evaluación y análisis sintáctico

Se calcula empleando la notación polaca inversa utilizando una estructura de pila para los posibles valores. Las expresiones pueden ser representadas en prefijo, infijo, postfijo. La conversión de una forma de la expresión a otra forma necesita de una pila. Muchos compiladores utilizan una pila para analizar la sintaxis de las expresiones, bloques de programa, etc. Antes de traducir el código de bajo nivel. La mayoría de los lenguajes de programación son de contexto libre de los idiomas que les permite ser analizados con máquinas basadas en la pila.

Por ejemplo, el cálculo: ((1 + 2) * 4) + 3, puede ser anotado como en notación postfija con la ventaja de no prevalecer las normas y los paréntesis necesario:

1 2 + 4 * 3 +

La expresión es evaluada de izquierda a derecha utilizando una pila:

Apilar cuando se enfrentan a un operando y Desafilar dos operandos y evaluar el valor cuando se enfrentan a una operación. Apilar el resultado.

De la siguiente manera (la Pila se muestra después de que la operación se haya llevado a cabo):

ENTRADA OPERACION PILA 1 Apilar operando 1 2 Apilar operando 1, 2 + Añadir 3 4 Apilar operando 3, 4 * Multiplicar 12 3 Apilar operando 12, 3 + Añadir 15

El resultado final, 15, se encuentra en la parte superior de la pila al final del cálculo.

Tiempo de ejecución de la gestión de memoria

Artículo principal: Pila basada en la asignación de memoria y Pila máquina. Una serie de lenguajes de programación están orientadas a la pila, lo que significa que la mayoría definen operaciones básicas (añadir dos números, la impresión de un carácter) cogiendo sus argumentos de la pila, y realizando de nuevo los valores de retorno en la pila. Por ejemplo, PostScript tiene una pila de retorno y un operando de pila, y también tiene un montón de gráficos estado y un diccionario de pila.

Forth utiliza dos pilas, una para pasar argumentos y una subrutina de direcciones de retorno. El uso de una pila de retorno es muy común, pero el uso poco habitual de un argumento para una pila legible para humanos es el lenguaje de programación Forth razón que se denomina una pila basada en el idioma.

Muchas máquinas virtuales también están orientadas hacia la pila, incluida la p-código máquina y la máquina virtual Java.

Casi todos los entornos de computación de tiempo de ejecución de memoria utilizan una pila especial PILA para tener información sobre la llamada de un procedimiento o función y de la anidación con el fin de cambiar al contexto de la llamada a restaurar cuando la llamada termina. Ellos siguen un protocolo de tiempo de ejecución entre el que llama y el llamado para guardar los argumentos y el valor de retorno en la pila. Pila es una forma importante de apoyar llamadas anidadas o a funciones recursivas. Este tipo de pila se utiliza implícitamente por el compilador para apoyar CALL y RETURN estados (o sus equivalentes), y no es manipulada directamente por el programador.

Algunos lenguajes de programación utilizar la pila para almacenar datos que son locales a un procedimiento. El espacio para los datos locales se asigna a los temas de la pila cuando el procedimiento se introduce, y son borradas cuando el procedimiento termina. El lenguaje de programación C es generalmente aplicado de esta manera. Utilizando la misma pila de los datos y llamadas de procedimiento tiene importantes consecuencias para la seguridad (ver más abajo), de los que un programador debe ser consciente, a fin de evitar la introducción de graves errores de seguridad en un programa.

Solucionar problemas de búsqueda

La búsqueda de la solución de un problema, es independientemente de si el enfoque es exhaustivo u óptimo, necesita espacio en la pila. Ejemplos de búsqueda exhaustiva métodos son fuerza bruta y backtraking. Ejemplos de búsqueda óptima a explorar métodos,son branch and bound y soluciones heurísticas. Todos estos algoritmos utilizan pilas para recordar la búsqueda de nodos que se han observado, pero no explorados aún. La única alternativa al uso de una pila es utilizar la recursividad y dejar que el compilador sea recursivo (pero en este caso el compilador todavía está utilizando una pila interna). El uso de pilas es frecuente en muchos problemas, que van desde almacenar la profundidad de los árboles hasta resolver crucigramas o jugar al ajedrez por ordenador. Algunos de estos problemas pueden ser resueltos por otras estructuras de datos como una cola.

Seguridad

La seguridad a la hora de desarrollar software usando estructuras de datos de tipo pila es un factor a tener en cuenta debido a ciertas vulnerabilidad que un uso incorrecto de éstas puede originar en la seguridad de nuestro software o en la seguridad del propio sistema que lo ejecuta. Por ejemplo, algunos lenguajes de programación usan una misma pila para almacenar los datos para un procedimientos y el link que permite retornar a su invocador. Ésto significa que el programa introduce y extrae los datos de la misma pila en la que se encuentra información crítica con las direcciones de retorno de las llamadas a procedimiento, supongamos que al introducir datos en la pila lo hacemos en una posición errónea de manera que introducimos una datos de mayor tamaño al soportado por la pila corrompiendo así las llamadas a procedimientos provocariamos un fallo en nuestro programa. Ésta técnica usada de forma maliciosa (es similar pero en otro ámbito al buffer overflow) permitiría a un atacante modificar el funcionamiento normal de nuestro programa y nuestro sistema, y es al menos una técnica útil si no lo evitamos en lenguajes muy populares como el ejemplo C.

V. ColasObjetivo General: El alumno elaborará programas que integren el uso de recursividady definir estructuras de datos para generar alternativas de programación.

Cola (informática)Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde 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 en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

Contenido

1 Usos concretos de la cola 2 Información adicional 3 Operaciones Básicas 4 Implementaciones

o 4.1 Colas en Maude o 4.2 Colas en C++ o 4.3 Colas en JAVA o 4.4 Colas en C#

5 Tipos de colas 6 Véase también 7 Enlaces externos

Usos concretos de la cola

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

En estos casos, el primer elemento de la lista realiza su función (pagar comida, pagar entrada para el partido o para el cine) y deja la cola. Este movimiento está representado en la cola por la función pop o desencolar. Cada vez que otro elemento se añade a la lista de espera se añaden al final de la cola representando la función push o encolar. Hay otras funciones auxiliares para ver el tamaño de la cola (size), para ver si está vacía en el caso de que no haya nadie esperando (empty) o para ver el primer elemento de la cola (front).

Información adicional

En caso de estar vacía borrar un elemento sería imposible hasta que no se añade un nuevo elemento. A la hora de añadir un elemento podríamos darle una mayor importancia a unos elementos que a otros (un cargo VIP) y para ello se crea un tipo de cola especial que es la cola de prioridad.

Operaciones Básicas

Crear: se crea la cola vacía. Encolar (añadir, entrar, push): se añade un elemento a la cola. Se añade 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 elemento frontal de la cola, es decir, el primero elemento que

entró.

Implementaciones

Colas en Maude

La ColaNV es la cola no vacía, que diferenciamos de la cola normal a la hora de tomar en cuenta errores. A su vez, el elemento X representa el tipo de valor que puede contener la cola: entero, carácter, registro....

fmod COLA {X :: TRIV} is sorts ColaNV{X} Cola{X} . subsort ColaNV{X} < Cola{X} . *** generadores op crear : -> Cola{X} [ctor] . op encolar : X$Elt Cola{X} -> ColaNV {X} [ctor] .

*** constructores op desencolar : Cola{X} -> Cola{X} .

*** selectores op frente : ColaNV{X} -> X$Elt .

*** variables var C : ColaNV{X} . vars E E2 : X$Elt .

*** ecuaciones eq desencolar(crear) = crear . eq desencolar(encolar(E, crear)) = crear . eq desencolar(encolar(E, C)) = encolar(E, desencolar(C)) .

eq frente(encolar(E, crear)) = E . eq frente(encolar(E, C)) = frente(C) . endfm

Especificación de una cola de colas de enteros en Maude:

view VInt from TRIV to INT is sort Elt to Int . endv

view VColaInt from TRIV to COLA{VInt} is sort Elt to Cola{VInt} . endv fmod COLA-COLAS-INT is protecting INT . protecting COLA{VColaInt} . *** operaciones propias de la cola de colas de enteros

op encolarInt : Int ColaNV{VColaInt} -> ColaNV{VColaInt} .op desencolarInt : Cola{VColaInt} -> Cola{VColaInt} .op frenteInt : ColaNV{VColaInt} -> [Int] .

*** variablesvar CCNV : ColaNV{VColaInt} .var CC : Cola{VColaInt} .var CE : Cola{VInt} .var E : Int .

*** ecuacioneseq encolarInt(E, encolar(CE, CC)) = encolar(encolar(E, CE), CC) .

eq desencolarInt (encolar(CE, crear)) = encolar(desencolar(CE), crear) . eq desencolarInt (encolar(CE, CCNV)) = encolar(CE, desencolarInt(CCNV)) .

eq frenteInt(CCNV) = frente(frente(CCNV)) . endfm

Colas en C++ #ifndef COLA #define COLA // Define la cola template <class T> class Cola{ private: struct Nodo{ T elemento; struct Nodo* siguiente; // coloca el nodo en la segunda posición }* primero; struct Nodo* ultimo; unsigned int elementos; public: Cola(){ elementos = 0; } ~Cola(){ while (elementos != 0) pop(); } void push(const T& elem){ Nodo* aux = new Nodo; aux->elemento = elem; if (elementos == 0) primero = aux; else ultimo->siguiente = aux; ultimo = aux; ++elementos; } void pop(){ Nodo* aux = primero; primero = primero->siguiente; delete aux; --elementos; } T consultar() const{ return primero->elemento; } bool vacia() const{ return elementos == 0; } unsigned int size() const{ return elementos;

} }; #endif

Colas en JAVA public void inserta(Elemento x) { Nodo Nuevo; Nuevo = new Nodo(x, null); if (NodoCabeza == null) { NodoCabeza = Nuevo; } else { NodoFinal.Siguiente = Nuevo; } NodoFinal = Nuevo; } public Elemento cabeza() throws IllegalArgumentException { if (NodoCabeza == null) { throw new IllegalArgumentException(); } else { return NodoCabeza.Info; } } public Cola() { // Devuelve una Cola vacía NodoCabeza = null; NodoFinal = null; //Realizado Por Lic: Helton Petters }

Colas en C#public partial class frmPrincipal { // Variables globales public static string[] Cola; public static int Frente; public static int Final; public static int N; [STAThread] public static void Main(string[] args) { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new frmPrincipal()); } public frmPrincipal() // Constructor { InitializeComponent(); Cola = new string[5]; // Arreglo lineal de 5 N = 4; Frente = -1; Final = -1; } void CmdInsercionClick(object sender, System.EventArgs e) { frmInsercion Insercion = new frmInsercion(); Insercion.Show(); } void CmdRecorridoClick(object sender, System.EventArgs e) { frmRecorrido Recorrido = new frmRecorrido(); Recorrido.Show();

} void CmdBusquedaClick(object sender, EventArgs e) { frmBusqueda Busqueda = new frmBusqueda(); Busqueda.Show(); } void CmdEliminacionClick(object sender, EventArgs e) { frmEliminacion Eliminar = new frmEliminacion(); Eliminar.Show(); } }

Algoritmo Insertar(Cola, N, Frente, Final, Elemento)

void CmdInsertarClick(object sender, System.EventArgs e) { elemento = txtInsercion.Text; // Se verifica que haya espacio en la Cola if (frmPrincipal.Frente == 0 && frmPrincipal.Final == frmPrincipal.N) { MessageBox.Show("La Cola esta llena"); return; } if (frmPrincipal.Frente == frmPrincipal.Final + 1) { MessageBox.Show("La Cola esta llena"); return; } // Si la cola esta vacia se inicializan punteros if (frmPrincipal.Frente == -1) { frmPrincipal.Frente = 0; frmPrincipal.Final = 0; } else if (frmPrincipal.Final == frmPrincipal.N) { frmPrincipal.Final = 0; } else { frmPrincipal.Final = frmPrincipal.Final + 1; } // Se agrega elemento a la Cola frmPrincipal.Cola[frmPrincipal.Final] = elemento; txtInsercion.Text = ""; }

Algoritmo Eliminación (Cola, Frente, Final, N)

void CmdEliminarClick(object sender, EventArgs e) { if (frmPrincipal.Frente == -1) { MessageBox.Show("Cola Vacia"); return; } string elemento = frmPrincipal.Cola[frmPrincipal.Frente]; // si la cola tiene un solo elemento if (frmPrincipal.Frente == frmPrincipal.Final) { frmPrincipal.Frente = -1;

frmPrincipal.Final = -1; } else if (frmPrincipal.Frente == frmPrincipal.N) { frmPrincipal.Frente = 0; } else { frmPrincipal.Frente = frmPrincipal.Frente + 1; } lsEliminado.Items.Add(elemento); }

Tipos de colas

Colas circulares (anillos) : en las que el último elemento y el primero están 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 atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

1. Añadir 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 añadir 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 inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.

Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

VI. ÁrbolesObjetivo General: El alumno elaborará programas que integren el uso de recursividady definir estructuras de datos para generar alternativas deprogramación.

Árbol (informática)En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Contenido

1 Definición 2 Tipos de árboles 3 Operaciones de árboles. Representación 4 Uso de los árboles 5 Véase también

o 5.1 Algoritmos de búsqueda en árboles

Definición

Formalmente, podemos definir un árbol de la siguiente forma:

Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).

Un nuevo árbol a partir de un nodo nr y k árboles de raíces con

elementos cada uno, puede construirse estableciendo una relación padre-hijo entre nr

y cada una de las raíces de los k árboles. El árbol resultante de nodos tiene como raíz el nodo nr, los nodos son los hijos de nr y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles Ai se les denota ahora subárboles de la raíz.

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero 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 nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:

El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y

luego cada uno de los hijos en orden previo. El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado

en los árboles binarios) consiste en recorrer en primer lugar A1, luego la raíz y luego cada uno de los

hijos en orden simétrico. El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada

uno de los hijos en orden posterior y por último la raíz.

Finalmente, puede decirse que esta estructura es una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico (ver también teoría de grafos y Glosario en teoría de grafos).

Tipos de árboles

Ejemplo de árbol (binario).

Árboles Binarios o Árbol de búsqueda binario auto-balanceable

Árboles AVL Árboles Rojo-Negro Árbol AA

Árboles Multicamino o Árboles B (Arboles de búsqueda multicamino autobalanceados)

Árbol-B+ Árbol-B*

Operaciones de árboles. Representación

Las operaciones comunes en árboles son:

Enumerar todos los elementos. Buscar un elemento. Dado un nodo, listar los hijos (si los hay). Borrar un elemento. Eliminar un subárbol (algunas veces llamada podar). Añadir un subárbol (algunas veces llamada injertar). Encontrar la raíz de cualquier nodo.

Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:

Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre. Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen

dadas por la posición del nodo en el array.

Uso de los árboles

Usos comunes de los árboles son:

Representación de datos jerárquicos. Como ayuda para realizar búsquedas en conjuntos de datos (ver también: algoritmos de búsqueda en

Árboles).

Árbol binarioEn ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Contenido

1 Definición de teoría de grafos 2 Tipos de árboles binarios 3 Implementación en C 4 Recorridos sobre árboles binarios

o 4.1 Recorridos en profundidad 4.1.1 Recorrido en preorden 4.1.2 Recorrido en postorden 4.1.3 Recorrido en inorden

o 4.2 Recorridos en amplitud (o por niveles) 5 Métodos para almacenar árboles binarios 6 Codificación de árboles n-arios como árboles binarios

Definición de teoría de grafos

Un árbol binario sencillo de tamaño 9 y altura 3, con un nodo raíz cuyo valor es 2.

En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.

Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.

Tipos de árboles binarios

Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos. Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos. Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos)

están a la misma profundidad (distancia desde la raíz, también llamada altura).

A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Implementación en C

Un árbol binario puede declararse de varias maneras. Algunas de ellas son:

Estructura con manejo de memoria dinámica, siendo puntA el puntero que apunta al árbol de tipo tArbol:

struct celda { telemento dato; struct celda *izdo, *dcho;};typedef struct celda *arbolbin;

Estructura con arreglo indexado:

typedef struct tArbol{ int clave; int hIzquierdo, hDerecho;} tArbol;tArbol árbol[NUMERO_DE_NODOS];

En el caso de un árbol binario casi-completo (o un árbol completo), puede utilizarse un sencillo arreglo de enteros con tantas posiciones como nodos deba tener el árbol. La información de la ubicación del nodo en el árbol es implícita a cada posición del arreglo. Así, si un nodo está en la posición i, sus hijos se encuentran en las posiciones 2i+1 y 2i+2, mientras que su padre (si tiene), se encuentra en la posición truncamiento((i-1)/2) (suponiendo que la raíz está en la posición cero). Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia, particularmente durante un recorrido en preorden. La estructura para este caso sería por tanto:

int árbol[NUMERO_DE_NODOS];

Recorridos sobre árboles binarios

Recorridos en profundidad

El método de este recorrido es tratar de encontrar de la cabecera a la raíz en nodo de unidad binaria. Ahora pasamos a ver la implementación de los distintos recorridos:

Recorrido en preorden

En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.

En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

void preorden(tArbol *a){ if (a != NULL) {

tratar(a); //Realiza una operación en nodo preorden(a->hIzquierdo); preorden(a->hDerecho); }}

Implementación en pseudocódigo de forma iterativa:

push(s,NULL); //insertamos en una pila (stack) el valor NULL, para asegurarnos de que esté vacíapush(s,raíz); //insertamos el nodo raízMIENTRAS (s <> NULL) HACER p = pop(s); //sacamos un elemento de la pila tratar(p); //realizamos operaciones sobre el nodo p SI (D(p) <> NULL) //preguntamos si p tiene árbol derecho ENTONCES push(s,D(p)); FIN-SI SI (I(p) <> NULL) //preguntamos si p tiene árbol izquierdo ENTONCES push(s,I(p)); FIN-SIFIN-MIENTRAS

Recorrido en postorden

En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda, nodo derecha, nodo raiz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

void postorden(tArbol *a){ if (a != NULL) { postorden(a->hIzquiedo); postorden(a->hDerecho); tratar(a); //Realiza una operación en nodo }}

Recorrido en inorden

En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda,nodo raiz,nodo derecha. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4 y 9.

Esquema de implementación:

void inorden(tArbol *a){ if (a != NULL) { inorden(a->hIzquierdo); tratar(a); //Realiza una operación en nodo inorden(a->hDerecho); }}

Recorridos en amplitud (o por niveles)

En este caso el recorrido se realiza en orden por los distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que sólo contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En el árbol de la figura el recorrido en amplitud sería: 2, 7, 5, 2, 6, 9, 5, 11 y 4.

Al contrario que en los métodos de recorrido en profundidad, el recorrido por niveles no es de naturaleza recursiva. Por ello, se debe utilizar una cola para recordar los subárboles izquierdos y derecho de cada nodo.

El esquema algoritmo para implementar un recorrido por niveles es exactamente el mismo que el utilizado en la versión iterativa del recorrido en preorden pero cambiando la estructura de datos que almacena los nodos por una cola.

Implementación en C:

void arbol_recorrido_anch (tipo_Arbol* A) { tipo_Cola cola_nodos; // esta cola esta implementada previamente, almacena punteros (posiciones de nodos de arbol) tipo_Pos nodo_actual; // este es un puntero llevara el recorrido if (vacio(A)) // sie el arbol esta vacio, salimos return; cola_inicializa(&cola_nodos); // obvio, y necesario cola_enqueue(A, &cola_nodos); // se encola la raiz while (!vacia(&cola_nodos)) { // mientras la cola no se vacie se realizara el recorrido nodo_actual = cola_dequeue(&cola_nodos) // de la cola saldran los nodos ordenados por nivel printf("%c,", nodo_actual->info); // se "procesa" el nodo donde va el recorrido, en este caso se imprime if (nodo_actual->izq != null) // si existe, ponemos el hijo izquierdo en la cola cola_enqueue(nodo_actual->izq, &cola_nodos); if (nodo_actual->der != null) // si existe, ponemos el hijo derecho en la cola cola_enqueue(nodo_actual->der, &cola_nodos); } // al vaciarse la cola se han visitado todos los nodos del arbol }

Métodos para almacenar árboles binarios

Los árboles binarios pueden ser construidos a partir de lenguajes de programación de varias formas. En un lenguaje con registros y referencias, los árboles binarios son construidos típicamente con una estructura de nodos y punteros en la cual se almacenan datos, cada uno de estos nodos tiene una referencia o puntero a un nodo izquierdo y a un nodo derecho denominados hijos. En ocasiones, también contiene un puntero a un único nodo. Si un nodo tiene menos de dos hijos, algunos de los punteros de los hijos pueden ser definidos como nulos para indicar que no dispone de dicho nodo. En la figura adjunta se puede observar la estructura de dicha implementación.

Los árboles binarios también pueden ser almacenados como una estructura de datos implícita en vectores, y si el árbol es un árbol binario completo, este método no desaprovecha el espacio en memoria. Tomaremos como notación la siguiente: si un nodo tiene un índice i, sus hijos se encuentran en índices 2i + 1 y 2i + 2, mientras

que sus padres (si los tiene) se encuentra en el índice (partiendo de que la raíz tenga índice cero). Este método tiene como ventajas el tener almacenados los datos de forma más compacta y por tener una forma más rápida y eficiente de localizar los datos en particular durante un preoden transversal. Sin embargo, desperdicia mucho espacio en memoria.

Codificación de árboles n-arios como árboles binarios

Hay un mapeo uno a uno entre los árboles generales y árboles binarios, el cual en particular es usado en Lisp para representar árboles generales como árboles binarios. Cada nodo N ordenado en el árbol corresponde a un nodo N 'en el árbol binario; el hijo de la izquierda de N’ es el nodo correspondiente al primer hijo de N, y el hijo derecho de N' es el nodo correspondiente al siguiente hermano de N, es decir, el próximo nodo en orden entre los hijos de los padres de N.

Esta representación como árbol binario de un árbol general, se conoce a veces como un árbol binario primer hijo hermano, o un árbol doblemente encadenado.

Una manera de pensar acerca de esto es que los hijos de cada nodo estén en una lista enlazada, encadenados junto con el campo derecho, y el nodo sólo tiene un puntero al comienzo o la cabeza de esta lista, a través de su campo izquierdo.

Por ejemplo, en el árbol de la izquierda, la A tiene 6 hijos (B, C, D, E, F, G). Puede ser convertido en el árbol binario de la derecha.

Un ejemplo de transformar el árbol n-ario a un árbol binario Cómo pasar de árboles n-arios a árboles FLOFO.

El árbol binario puede ser pensado como el árbol original inclinado hacia los lados, con los bordes negros izquierdos representando el primer hijo y los azules representado los siguientes hermanos.

Las hojas del árbol de la izquierda serían escritas en Lisp como:

(((M N) H I) C D ((O) (P)) F (L))

Que se ejecutará en la memoria como el árbol binario de la derecha, sin ningún tipo de letras en aquellos nodos que tienen un hijo izquierdo.

Árbol binario de búsqueda auto-balanceable

En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son

insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave.

Tiempos para varias operaciones en términos del número de nodos en el árbol n:

Operación Tiempo en cota superior asintótica

Búsqueda O(log n)

Inserción O(log n)

Eliminación O(log n)

Iteración en orden O(n)

Para algunas implementaciones estos tiempos son el peor caso, mientras que para otras están amortizados.

Estructuras de datos populares que implementan este tipo de árbol:

Árbol AVL Árbol rojo-negro

Árbol AVLÁrbol AVL es un tipo especial de árbol binario ideado por los matemáticos rusos A delson- V elskii y L andis . Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.

Contenido

1 Descripción 2 Definición formal

o 2.1 Definición de la altura de un árbol o 2.2 Definición de árbol AVL

3 Factor de equilibrio 4 Operaciones

o 4.1 Rotaciones o 4.2 Inserción o 4.3 Extracción o 4.4 Búsqueda

5 Véase también 6 Enlaces externos

Descripción

Un ejemplo de árbol binario no equilibrado (no es AVL)

Un ejemplo de árbol binario equilibrado (si es AVL)

El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, A delson- V elskii y L andis . Lo dieron a conocer en la publicación de un artículo en 1962: "An algorithm for the organization of information" ("Un algoritmo para la organización de la información").

Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.

Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Los árboles AVL más profundos son los árboles de Fibonacci.

Definición formal

Definición de la altura de un árbol

Sea T un árbol binario de búsqueda y sean Ti y Td sus subárboles, su altura H(T), es:

0 si el árbol T contiene solo la raíz 1 + max(H(Ti),H(Td)) si contiene más nodos

Definición de árbol AVL

Un árbol vacío es un árbol AVL Si T es un árbol no vacío y Ti y Td sus subárboles, entonces T es AVL si y solo si:

Ti es AVL

Td es AVL | H(Ti) − H(Td) | < = 1

Factor de equilibrio

Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los árboles binarios de búsqueda (ABB), y además el dato que controla el factor de equilibrio.

El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:

FE = altura subárbol derecho - altura subárbol izquierdo;Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.

Si el factor de equilibrio de un nodo es:

0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.1 -> el nodo está equilibrado y su subárbol derecho es un nivel más alto.-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.

Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.

Operaciones

Las operaciones básicas de un árbol AVL implican generalmente el realizar los mismos algoritmos que serían realizados en un árbol binario de búsqueda desequilibrado, pero precedido o seguido por una o más de las llamadas "rotaciones AVL".

Rotaciones

El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.

ROTACIÓN SIMPLE A LA DERECHA.

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).

op rotDer: AVL{X} -> [AVL{X}] .eq rotDer(arbolBin(R1, arbolBin(R2, I2, D2), D1)) ==arbolBin(R2, I2, arbolBin(R1, D2, D)) .

ROTACIÓN SIMPLE A LA IZQUIERDA.

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).

Precondición : Tiene que tener hijo derecho no vacío.

op rotIzq: AVL{X} -> [AVL{X}] .eq rotIzq(arbolBin(R1, I, arbolBin(R2, I2, D2))) ==arbolBin(R2, arbolBin(R1, I, I2), D2) .

Si la inserción se produce en el hijo derecho del hijo izquierdo del nodo desequilibrado (o viceversa) hay que realizar una doble rotación.

ROTACIÓN DOBLE A LA DERECHA.

ROTACIÓN DOBLE A LA IZQUIERDA.

Inserción

La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibrado y después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción.

Proceso de inserción:

1.buscar hasta encontrar la posición de inserción o modificación (proceso idéntico a inserción en árbol binario de búsqueda)2.insertar el nuevo nodo con factor de equilibrio “equilibrado”3.desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario

Debido a que las rotaciones son una operación que tienen complejidad constante y a que la altura esta limitada a O (log(n)), el tiempo de ejecución para la inserción es del orden O (log(n)).

op insertar: X$Elt AVL{X} -> AVLNV{X} .eq insertar(R, crear) == arbolBin(R, crear, crear) .

ceq insertar(R1, arbolBin(R2, I, D)) ==if (R1==R2) then

arbolBin(R2, I, D)elseif (R1<R2) then

if ( (altura(insertar(R1,I)) – altura(D)) < 2) thenarbolBin(R2, insertar(R1, I), D)

else ***hay que reequilibrarif (R1 < raiz(I)) then

rotarDer(arbolBin(R2, insertar(R1, I), D))else

rotarDer(arbolBin(R2, rotarIzq(insertar(R1, I)), D))

fi .

fi .else

if ( (altura(insertar(R1,I)) – altura(D)) < 2) thenarbolBin(R2, insertar(R1, I), D)

else *** hay que reequilibrarif (R1 > raiz(D)) then

rotarIzq(arbolBin(R, I, insertar(R1, D)))else

rotatIzq(arbolBin(R, I, rotarDer(insertar(R1, D))))fi .

fi .fi .

Extracción

El procedimiento de borrado es el mismo que en el caso de árbol binario de búsqueda.La diferencia se encuentra en el proceso de reequilibrado posterior. El problema de la extracción puede resolverse en O (log n) pasos. Una extracción trae consigo una disminución de la altura de la rama donde se extrajo y tendrá como efecto un cambio en el factor de equilibrio del nodo padre de la rama en cuestión, pudiendo necesitarse una rotación.

Esta disminución de la altura y la corrección de los factores de equilibrio con sus posibles rotaciones asociadas pueden propagarse hasta la raíz.

Borrar A, y la nueva raíz será M.

Borrado A, la nueva raíz es M. Aplicamos la rotación a la derecha.

El árbol resultante ha perdido altura.

En borrado pueden ser necesarias varias operaciones de restauración del equilibrio, y hay que seguir comprobando hasta llegar a la raíz.

op eliminar: X$Elt AVL{X} -> AVL{X} .eq eliminar(R, crear) == crear .ceq eliminar(R1, arbolBin(R2, I, D)) ==

if (R1 == R2) thenif esVacio(I) then

Delseif esVacio(D) then

Ielse

if (altura(I) - altura(eliminar(min(D),D)) < 2) thenarbolBin(min(D), I, eliminar(min(D), D))

***tenemos que reequilibrarelseif (altura(hijoIzq(I) >= altura(hijoDer(I)))) then

rotDer(arbolBin(min(D), I, eliminar(min(D),D)))else

rotDer(arbolBin(min(D), rotIzq(I), eliminar(min(D),D)))

Búsqueda

public class Nodo {

int numMat; Nodo izqda, drcha; public Nodo(int mat){ numMat = mat; izqda = drcha = null; } public void re_enorden(){ if(izqda != null) izqda.re_enorden(); System.out.println("Matricula: " +numMat); if(drcha != null) drcha.re_enorden(); }

} public class ABB {

private Nodo raiz; public ABB(){ raiz = null; } public void insertar(int nuevoM){ if(raiz==null){ raiz = new Nodo(nuevoM); } else{ insertar(raiz,nuevoM); } } private void insertar(Nodo rz, int nm){ if (rz == null) rz = new Nodo(nm); else if(nm < rz.numMat) insertar(rz.izqda,nm); else if(nm > rz.numMat) insertar(rz.drcha,nm); else System.out.println("Numero Duplicados"); } public void visualizar(){ if(raiz!=null) raiz.re_enorden(); }

} public class Ejecutar {

public static void main(String []args){ ABB arbol = new ABB(); arbol.insertar(6); arbol.insertar(3); arbol.insertar(7); arbol.visualizar(); }

}

Ejemplo de TAD AVL

#include <stdio.h> typedef struct AVL{

int dato, FB; // FB es la altura del subarbol izquierdo menos la altura del subarbol derecho

AVL *izq, *der;bool borrado;

} AVL; void rotarLL(AVL* &A){ //precond: el arbol necesita una rotacion LL

AVL* aux = A->izq->der;A->izq->der = A;A->izq->FB = 0; AVL* aux2 = A->izq;A->izq = aux;A->FB = 0;A = aux2;

} void rotarRR(AVL* &A){ //precond: el arbol necesita una rotacion RR

AVL* aux = A->der->izq;A->der->izq = A;A->der->FB = 0; AVL* aux2 = A->der;A->der = aux;A->FB = 0;A = aux2;

} void rotarLRalter(AVL* &A){ //precond: el arbol necesita una rotacion LR

rotarRR(A->izq);rotarLL(A);

} void rotarRLalter(AVL* &A){ //precond: el arbol necesita una rotacion RL

rotarLL(A->der);rotarRR(A);

} AVL* Crear(){

return NULL;} void Insert(int n, bool &aumento, AVL* &A){

if (A == NULL){A = new AVL;A->dato = n;A->FB = 0;A->izq = NULL;A->der = NULL;aumento = true;A->borrado = false;

}else{if (n < A->dato){

Insert(n, aumento, A->izq);if (aumento){

switch (A->FB){case -1:{

A->FB = 0;aumento = false;break;

}case 0:{

A->FB = 1;aumento = true;break;

}case 1:{

if (A->izq->FB == 1){ // Si es 1 necesita una rotacion LL si es -1 necesita una rotacion LR

rotarLL(A);}else{

rotarLRalter(A);}aumento = false;break;

}}

}}else{

Insert(n, aumento, A->der);if (aumento){

switch (A->FB){case -1:{

if (A->der->FB == 1){ // Si es 1 necesita una rotacion RL si es -1 necesita una rotacion RR

rotarRLalter(A);}else{

rotarRR(A);}aumento = false;break;

}case 0:{

A->FB = -1;aumento = true;break;

}case 1:{

A->FB = 0;aumento = false;break;

}}

}}

}} void Insertar(AVL* &A, int n){

bool aumento;Insert(n, aumento, A);

} bool EsVacio(AVL* A){

return A == NULL;} bool Pertenece(AVL* A, int n){

if (A == NULL){return false;

}else{if (A->dato == n){

if (A->borrado){return false;

}else{return true;

}}else if (n < A->dato){

return Pertenece(A->izq, n);}else{

return Pertenece(A->der, n);}

}} void Borrar(AVL* &A, int n){

if (A->dato == n){A->borrado = true;

}else if (n < A->dato){Borrar(A->izq, n);

}else{Borrar(A->der, n);

}}

Árbol rojo-negroUn árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de “árboles-B binarios simétricos”, pero tomó su nombre moderno en un trabajo de Leo J. Guibas y Robert Sedgewick realizado en 1978. Es complejo, pero tiene un buen peor caso de tiempo de ejecución para sus operaciones y es eficiente en la práctica. Puede buscar, insertar y borrar en un tiempo O(log n), donde n es el número de elementos del árbol.

Sería ideal exponer la especificación algebraica completa de este tipo abstracto de datos (TAD) escrita en algún lenguaje de especificación de TADs como podría ser Maude; sin embargo, la complejidad de la estructura hace que la especificación quede bastante ilegible, y no aportaría nada. Por tanto, explicaremos su funcionamiento con palabras, esquemas e implementaciones de funciones en el lenguaje de programación C.

Contenido

1 Terminología 2 Propiedades 3 Usos y ventajas 4 Operaciones

o 4.1 Rotación o 4.2 Búsqueda o 4.3 Inserción o 4.4 Eliminación

5 Demostración de cotas 6 Complejidad 7 Referencias 8 Véase también 9 Enlaces externos

o 9.1 Demos y simuladores o 9.2 Implementaciones

Terminología

Un árbol rojo-negro es un tipo especial de árbol binario usado en informática para organizar información compuesta por datos comparables (como por ejemplo números).

En los árboles rojo-negro las hojas no son relevantes y no contienen datos. A la hora de implementarlo en un lenguaje de programación, para ahorrar memoria, un único nodo (nodo-centinela) hace de nodo hoja para todas las ramas. Así,todas las referencias de los nodos internos a las hojas van a parar al nodo centinela.

En los árboles rojo-negro, como en todos los árboles binarios de búsqueda, es posible moverse ordenadamente a través de los elementos de forma eficiente si hay forma de localizar el padre de cualquier nodo. El tiempo de desplazarse desde la raíz hasta una hoja a través de un árbol equilibrado que tiene la mínima altura posible es de O(log n).

Propiedades

Un ejemplo de árbol rojo-negro

Un árbol rojo-negro es un árbol binario de búsqueda en el que cada nodo tiene un atributo de color cuyo valor es o bien rojo o bien negro. Además de los requisitos impuestos a los árboles binarios de búsqueda convencionales, se deben satisfacer los siguientes para tener un árbol rojo-negro válido:

1. Todo nodo es o bien rojo o bien negro.2. La raíz es negra.3. Todas las hojas son negras (las hojas son los hijos nulos).4. Los hijos de todo nodo rojo son negros (también llamada "Propiedad del rojo").5. Cada camino simple desde un nodo a una hoja descendiente contiene el mismo número de nodos negros,

ya sea contando siempre los nodos negros nulos, o bien no contándolos nunca (el resultado es equivalente). También es llamada "Propiedad del camino", y al número de nodos negros de cada camino, que es constante para todos los caminos, se le denomina "Altura negra del árbol", y por tanto el cámino no puede tener dos rojos seguidos.

6. El camino más largo desde la raíz hasta una hoja no es más largo que 2 veces el camino más corto desde la raíz del árbol a una hoja en dicho árbol. El resultado es que dicho árbol está aproximadamente equilibrado.

Dado que las operaciones básicas como insertar, borrar y encontrar valores tienen un peor tiempo de búsqueda proporcional a la altura del árbol, esta cota superior de la altura permite a los árboles rojo-negro ser eficientes en el peor caso, de forma contraria a lo que sucede en los árboles binarios de búsqueda. Para ver que estas propiedades garantizan lo dicho, basta ver que ningún camino puede tener 2 nodos rojos seguidos debido a la propiedad 4. El camino más corto posible tiene todos sus nodos negros, y el más largo alterna entre nodos rojos y negros. Como todos los caminos máximos tienen el mismo número de nodos negros, por la propiedad 5, esto muestra que no hay ningún camino que pueda tener el doble de longitud que otro camino.

En muchas presentaciones de estructuras arbóreas de datos, es posible para un nodo tener solo un hijo y las hojas contienen información. Es posible presentar los árboles rojo-negro en este paradigma, pero cambian algunas de las propiedades y se complican los algoritmos. Por esta razón, este artículo utilizan “hojas nulas”, que no contienen información y simplemente sirven para indicar dónde el árbol acaba, como se mostró antes. Habitualmente estos nodos son omitidos en las representaciones, lo cual da como resultado un árbol que parece contradecir los principios expuestos antes, pero que realmente no los contradice. Como consecuencia de esto todos los nodos internos tienen dos hijos, aunque uno o ambos nodos podrían ser una hoja nula.

Otra explicación que se da del árbol rojo-negro es la de tratarlo como un árbol binario de búsqueda cuyas aristas, en lugar de nodos, son coloreadas de color rojo o negro, pero esto no produce ninguna diferencia. El color de cada nodo en la terminología de este artículo corresponde al color de la arista que une el nodo a su padre, excepto la raíz, que es siempre negra (por la propiedad 2) donde la correspondiente arista no existe.

Usos y ventajas

Los árboles rojo-negro ofrecen un peor caso con tiempo garantizado para la inserción, el borrado y la búsqueda. No es esto únicamente lo que los hace valiosos en aplicaciones sensibles al tiempo como las aplicaciones en tiempo real, sino que además son apreciados para la construcción de bloques en otras estructuras de datos que garantizan un peor caso. Por ejemplo, muchas estructuras de datos usadas en geometría computacional pueden basarse en árboles rojo-negro.

El árbol AVL es otro tipo de estructura con O(log n) tiempo de búsqueda, inserción y borrado. Está equilibrado de forma más rígida que los árboles rojo-negro, lo que provoca que la inserción y el borrado sean más lentos pero la búsqueda y la devolución del resultado de la misma más veloz.

Los árboles rojo-negro son particularmente valiosos en programación funcional, donde son una de las estructuras de datos persistentes más comúnmente utilizadas en la construcción de arrays asociativos y conjuntos que pueden retener versiones previas tras mutaciones. La versión persistente del árbol rojo-negro requiere un espacio O(log n) para cada inserción o borrado, además del tiempo.

Los árboles rojo-negro son isométricos a los árboles 2-3-4. En otras palabras, para cada árbol 2-3-4, existe un árbol correspondiente rojo-negro con los datos en el mismo orden. La inserción y el borrado en árboles 2-3-4 son también equivalentes a los cambios de colores y las rotaciones en los árboles rojo-negro. Esto los hace ser una herramienta útil para la comprensión del funcionamiento de los árboles rojo-negro y por esto muchos textos introductorios sobre algoritmos presentan los árboles 2-3-4 justo antes que los árboles rojo-negro, aunque frecuentemente no sean utilizados en la práctica.

Operaciones

Las operaciones de sólo lectura en un árbol rojo-negro no requieren modificación alguna con respecto a las utilizadas en los árboles binarios de búsqueda, ya que cada árbol rojo-negro es un caso especial de árbol binario de búsqueda.

Sin embargo, el resultado inmediato de una inserción o la eliminación de un nodo utilizando los algoritmos de un árbol binario de búsqueda normal podría violar las propiedades de un árbol rojo-negro. Restaurar las propiedades rojo-negro requiere un pequeño número (O(log n))de cambios de color (que son muy rápidos en la práctica) y no más de 3 rotaciones (2 por inserción). A pesar de que las operaciones de inserción y borrado son complicadas, sus tiempos de ejecución siguen siendo O(log n).

Rotación

Para conservar las propiedades que debe cumplir todo árbol rojo-negro, en ciertos casos de la inserción y la eliminación será necesario reestructurar el árbol, si bien no debe perderse la ordenación relativa de los nodos. Para ello, se llevan a cabo una o varias rotaciones, que no son más que reestructuraciones en las relaciones padre-hijo-tío-nieto.

Las rotaciones que se consideran a continuación son simples; sin embargo, también se dan las rotaciones dobles.

En las imágenes pueden verse de forma simplificada cómo se llevan a cabo las rotaciones simples hacia la izquierda y hacia la derecha en cualquier árbol binario de búsqueda, en particular en cualquier árbol rojo-negro. Podemos ver también la implementación en C de dichas operaciones.

voidrotar_izda(struct node *p){

struct node *aux;

aux = p;p = p->dcho;aux-> dcho = p->izdo;p->izdo = aux;

}

voidrotar_dcha(struct node *p){

struct node *aux;aux = p;p = p->izdo;aux->izdo = p->dcho;p->dcho = aux,

}

Búsqueda

La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. La búsqueda de un

elemento en un ABB (Árbol Binario de Búsqueda) en general, y en un árbol rojo negro en particular, se puede realizar de dos formas, iterativa o recursiva.

Ejemplo de versión iterativa en el lenguaje de programación C, suponiendo que estamos buscando una clave alojada en un nodo donde está el correspondiente "dato" que precisamos encontrar:

data Buscar_ABB(abb t,clave k) { abb p; dato e; e=NULL; p=t; if (!estaVacio(p)) { while (!estaVacio(p) && (p->k!=k) ) { if (k < p->k) { p=p->l; } if (p->k < k) { p=p->r; } } if (!estaVacio(p) &&(p->d!=NULL) ) { e=copiaDato(p->d); } } return e;}

Véase ahora la versión recursiva en ese mismo lenguaje:

int buscar(tArbol *a, int elem){ if (a == NULL) return 0; else if (a->clave < elem) return buscar(a->hDerecho, elem); else if (a->clave > elem) return buscar(a->hIzquierdo, elem); else return 1;}

Inserción

La inserción comienza añadiendo el nodo como lo haríamos en un árbol binario de búsqueda convencional y pintándolo de rojo. Lo que sucede después depende del color de otros nodos cercanos. El término tío nodo será usado para referenciar al hermano del padre de un nodo, como en los árboles familiares humanos. Conviene notar que:

La propiedad 3 (Todas las hojas, incluyendo las nulas, son negras) siempre se cumple. La propiedad 4 (Ambos hijos de cada nodo rojo son negros) está amenazada solo por añadir un nodo

rojo, por repintar un nodo negro de color rojo o por una rotación. La propiedad 5 (Todos los caminos desde un nodo dado hasta sus nodos hojas contiene el mismo

número de nodos negros) está amenazada solo por añadir un nodo rojo, por repintar un nodo negro de color rojo o por una rotación.

Al contrario de lo que sucede en otros árboles como puede ser el Árbol AVL, en cada inserción se realiza un máximo de una rotación, ya sea simple o doble. Por otra parte, se asegura un tiempo de recoloración máximo de O(log2n) por cada inserción.

Nota: En los esquemas que acompañan a los algoritmos, la etiqueta N será utilizada por el nodo que está siendo insertado, P para los padres del nodo N, G para los abuelos del nodo N, y U para los tíos del nodo N. Notamos que los roles y etiquetas de los nodos están intercambiados entre algunos casos, pero en cada caso, toda etiqueta continúa representando el mismo nodo que representaba al comienzo del caso. Cualquier color mostrado en el diagrama está o bien supuesto en el caso o implicado por dichas suposiciones.

Los nodos tío y abuelo pueden ser encontrados por las siguientes funciones:

struct node *abuelo(struct node *n){

if ((n != NULL) && (n->padre != NULL))return n->padre->padre;

elsereturn NULL;

} struct node *tio(struct node *n){

struct node *a = abuelo(n);if (n->padre == a->izdo)

return a->dcho;else

return a->izdo;}

Estudiemos ahora cada caso de entre los posibles que nos podemos encontrar al insertar un nuevo nodo.

Caso 1: El nuevo nodo N es la raíz de del árbol. En este caso, es repintado a color negro para satisfacer la propiedad 2 (la raíz es negra). Como esto añade un nodo negro a cada camino, la propiedad 5 (todos los caminos desde un nodo dado a sus hojas contiene el mismo número de nodos negros) se mantiene. En C quedaría así:

voidinsercion_caso1(struct node *n){

if (n->padre == NULL)n->color = NEGRO;

elseinsercion_caso2(n);

}

Caso 2: El padre del nuevo nodo (esto es, el nodo P) es negro, así que la propiedad 4 (ambos hijos de cada nodo rojo son negros) se mantiene. En este caso, el árbol es aun válido. La propiedad 5 (todos los caminos desde cualquier nodo dado a sus hojas contiene igual número de nodos negros) se mantiene, porque el nuevo nodo N tiene dos hojas negras como hijos, pero como N es rojo, los caminos a través de cada uno de sus hijos tienen el mismo número de nodos negros que el camino hasta la hoja que reemplazó, que era negra, y así esta propiedad se mantiene satisfecha. Su implementación:

void

insercion_caso2(struct node *n){

if (n->padre->color == NEGRO)return; /* Árbol válido. */

elseinsercion_caso3(n);

}

Nota: En los siguientes casos se puede asumir que N tiene un abuelo, el nodo G, porque su padre P es rojo, y si fuese la raíz, sería negro. Consecuentemente, N tiene también un nodo tío U a pesar de que podría ser una hoja en los casos 4 y 5.

Caso 3: Si el padre P y el tío U son rojos, entonces ambos nodos pueden ser repintados de negro y el abuelo G se convierte en rojo para mantener la propiedad 5 (todos los caminos desde cualquier nodo dado hasta sus hojas contiene el mismo número de nodos negros). Ahora, el nuevo nodo rojo N tiene un padre negro. Como cualquier camino a través del padre o el tío debe pasar a través del abuelo, el número de nodos negros en esos caminos no ha cambiado. Sin embargo, el abuelo G podría ahora violar la propiedad 2 (la raíz es negra) o la 4 (ambos hijos de cada nodo rojo son negros), en el caso de la 4 porque G podría tener un padre rojo. Para solucionar este problema, el procedimiento completo se realizará de forma recursiva hacia arriba hasta alcanzar el caso 1. El código en C quedaría de la siguiente forma:voidinsercion_caso3(struct node *n){

struct node *t = tio(n), *a;

if ((t != NULL) && (t->color == ROJO)) {n->padre->color = NEGRO;t->color = NEGRO;a = abuelo(n);a->color = ROJO;insercion_caso1(a);

} else {insercion_caso4(n);

}}

Nota: En los casos restantes, se asume que el nodo padre P es el hijo izquierdo de su padre. Si es el hijo derecho, izquierda y derecha deberían ser invertidas a partir de los casos 4 y 5. El código del ejemplo toma esto en consideración.

Caso 4: El nodo padre P es rojo pero el tío U es negro; también, el nuevo nodo N es el hijo derecho de P, y P es el hijo izquierdo de su padre G. En este caso, una rotación a la izquierda que cambia los roles del nuevo nodo N y su padre P puede ser realizada; entonces, el primer nodo padre P se ve implicado al usar el caso 5 de inserción (reetiquetando N y P ) debido a que la propiedad 4 (ambos hijos de cada nodo rojo son negros) se mantiene aún incumplida. La rotación causa que algunos caminos (en el sub-árbol etiquetado como “1”) pasen a través del nuevo nodo donde no lo hacían antes, pero ambos nodos son rojos, así que la propiedad 5 (todos los caminos desde cualquier nodo dado a sus hojas contiene el mismo número de nodos negros) no es violada por la rotación. Aquí tenemos una posible implementación:voidinsercion_caso4(struct node *n){

struct node *a = abuelo(n);

if ((n == n->padre->dcho) && (n->padre == a->izdo)) {rotar_izda(n->padre);n = n->izdo;

} else if ((n == n->padre->izdo) && (n->padre == a->dcho)) {rotar_dcha(n->padre);n = n->dcho;

}insercion_caso5(n);

}

Caso 5: El padre P es rojo pero el tío U es negro, el nuevo nodo N es el hijo izquierdo de P, y P es el hijo izquierdo de su padre G. En este caso, se realiza una rotación a la derecha sobre el padre P; el resultado es un árbol donde el padre P es ahora el padre del nuevo nodo N y del inicial abuelo G. Este nodo G ha de ser negro, así como su hijo P rojo. Se intercambian los colores de ambos y el resultado satisface la propiedad 4 (ambos hijos de un nodo rojo son negros). La propiedad 5 (todos los caminos desde un nodo dado hasta sus hojas contienen el mismo número de nodos negros) también se mantiene satisfecha, ya que todos los caminos que iban a través de esos tres nodos entraban por G antes, y ahora entran por P. En cada caso, este es el único nodo negro de los tres. Una posible implementación en C es la siguiente:voidinsercion_caso5(struct node *n){

struct node *a = abuelo(n);

n->padre->color = NEGRO;a->color = ROJO;if ((n == n->padre->izdo) && (n->padre == a->izdo)) {

rotar_dcha(a);} else {

/*

* En este caso, (n == n->padre->dcho) && (n->padre == a->dcho). */rotar_izda(a);

}}

Nótese que la inserción se realiza sobre el propio árbol y que los códigos del ejemplo utilizan recursión de cola.

Eliminación

En un árbol binario de búsqueda normal, cuando se borra un nodo con dos nodos internos como hijos, tomamos el máximo elemento del subárbol izquierdo o el mínimo del subárbol derecho, y movemos su valor al nodo que es borrado (como se muestra aquí). Borramos entonces el nodo del que copiábamos el valor que debe tener menos de dos nodos no hojas por hijos. Copiar un valor no viola ninguna de las propiedades rojo-negro y reduce el problema de borrar en general al de borrar un nodo con como mucho un hijo no hoja. No importa si este nodo es el nodo que queríamos originalmente borrar o el nodo del que copiamos el valor.

Resumiendo, podemos asumir que borramos un nodo con como mucho un hijo no hoja (si solo tiene nodos hojas por hijos, tomaremos uno de ellos como su hijo). Si borramos un nodo rojo, podemos simplemente reemplazarlo con su hijo, que debe ser negro. Todos los caminos hasta el nodo borrado simplemente pasarán a través de un nodo rojo menos, y ambos nodos, el padre del borrado y el hijo, han de ser negros, así que las propiedades 3 (todas las hojas, incluyendo las nulas, son negras) y 4 (los dos hijos de cada nodo rojo son negros) se mantienen. Otro caso simple es cuando el nodo borrado es negro y su hijo es rojo. Simplemente eliminar un nodo negro podría romper las propiedades 4 (los dos hijos de cada nodo rojo son negros) y 5 (todos los caminos desde un nodo dado hasta sus hojas contienen el mismo número de nodos negros), pero si repintamos su hijo de negro, ambas propiedades quedan preservadas.

El caso complejo es cuando el nodo que va a ser borrado y su hijo son negros. Empezamos por reemplazar el nodo que va a ser borrado con su hijo. Llamaremos a este hijo (en su nueva posición) N, y su hermano (el nuevo hijo de su padre) S. En los diagramas de debajo, usaremos P para el nuevo padre de N, SL para el hijo izquierdo de S, y SR para el nuevo hijo derecho de S (se puede mostrar que S no puede ser una hoja).

Nota: Entre algunos casos cambiamos roles y etiquetas de los nodos, pero en cada caso, toda etiqueta sigue representando al mismo nodo que representaba al comienzo del caso. Cualquier color mostrado en el diagrama es o bien supuesto en su caso o bien implicado por dichas suposiciones. El blanco representa un color desconocido (o bien rojo o bien negro).

El cumplimiento de estas reglas en un árbol con n nodos, asegura un máximo de tres rotaciones y hasta O(log2n) recoloraciones.

Encontraremos el hermano usando esta función:

struct node *hermano(struct node *n){

if (n == n->padre->izdo)return n->padre->dcho;

elsereturn n->padre->izdo;

}

Nota: Con el fin de preservar la buena definición del árbol, necesitamos que toda hoja nula siga siendo una hoja nula tras todas las transformaciones (que toda hoja nula no tendrá ningún hijo). Si el nodo que estamos borrando tiene un hijo no hoja N, es fácil ver que la propiedad se satisface. Si, por otra parte N fuese una hoja nula, se verifica por los diagramas o el código que para todos los casos la propiedad se satisface también.

Podemos realizar los pasos resaltados arriba con el siguiente código, donde la función reemplazar_nodo sustituye hijo en el lugar de n en el árbol. Por facilitar la comprensión del ejemplo, en el código de esta sección supondremos que las hojas nulas están representadas por nodos reales en lugar de NULL (el código de la sección inserción trabaja con ambas representaciones).

voidelimina_un_hijo(struct node *n){

/* * Precondición: n tiene al menos un hijo no nulo. */struct node *hijo = es_hoja(n->dcho) ? n->izdo : n->dcho;

reemplazar_nodo(n, hijo);if (n->color == NEGRO) {

if (hijo->color == ROJO)hijo->color = NEGRO;

elseeliminar_caso1(hijo);

}free(n);

}

Nota: Si N es una hoja nula y no queremos representar hojas nulas como nodos reales, podemos modificar el algoritmo llamando primero a eliminar_caso1() en su padre (el nodo que borramos, n en el código anterior) y borrándolo después. Podemos hacer esto porque el padre es negro, así que se comporta de la misma forma que una hoja nula (y a veces es llamada hoja “fantasma”). Y podemos borrarla con seguridad, de tal forma que n seguirá siendo una hoja tras todas las operaciones, como se muestra arriba.

Si N y su padre original son negros, entonces borrar este padre original causa caminos que pasan por N y tienen un nodo negro menos que los caminos que no. Como esto viola la propiedad 5 (todos los caminos desde un nodo dado hasta su nodos hojas deben contener el mismo número de nodos negros), el árbol debe ser reequilibrado. Hay varios casos a considerar.

Caso 1: N es la nueva raíz. En este caso, hemos acabado. Borramos un nodo negro de cada camino y la nueva raíz es negra, así las propiedades se cumplen. Una posible implementación en el lenguaje de programación C sería la siguiente:

voideliminar_caso1(struct node *n){

if (n->padre!= NULL)eliminar_caso2(n);

}

Nota: En los casos 2, 5 y 6, asumimos que N es el hijo izquierdo de su padre P. Si éste fuese el hijo derecho, la izquierda y la derecha deberían ser invertidas en todos estos casos. De nuevo, el código del ejemplo toma ambos casos en cuenta.

Caso 2: S es rojo. En este caso invertimos los colores de P y S, por lo que rotamos a la izquierda P, pasando S a ser el abuelo de N. Nótese que P tiene que ser negro al tener un hijo rojo. Aunque todos los caminos tienen todavía el mismo número de nodos negros, ahora N tiene un hermano negro y un padre rojo, así que podemos proceder a al paso 4, 5 o 6 (este nuevo hermano es negro porque éste era uno de los hijos de S, que es rojo). En casos posteriores, reetiquetaremos el nuevo hermano de N como S. Aquí podemos ver una implementación:voideliminar_caso2(struct node *n){

struct node *hm = hermano_menor(n);

if (hm->color == ROJO) {n->padre->color = ROJO;hm->color = NEGRO;if (n == n->padre->izdo)

rotar_izda(n->padre);else

rotar_dcha(n->padre);}eliminar_caso3(n);

}

Caso 3: P, S y los hijos de S son negros. En este caso, simplemente cambiamos S a rojo. El resultado es que todos los caminos a través de S, precisamente aquellos que no pasan por N, tienen un nodo negro menos. El hecho de borrar el padre original de N haciendo que todos los caminos que pasan por N tengan un nodo negro menos nivela el árbol. Sin embargo, todos los caminos a través de P tienen ahora un nodo negro menos que los caminos que no pasan por P, así que la propiedad 5 aún no se cumple (todos los caminos desde cualquier nodo a su nodo hijo contienen el mismo número de nodos negros). Para corregir esto, hacemos el proceso de reequilibrio en P, empezando en el caso 1. Su implementación en C:voideliminar_caso3(struct node *n){

struct node *hm = hermano_menor(n);

if ((n->padre->color == NEGRO) && (hm->color == NEGRO) && (hm->izdo->color == NEGRO) && (hm->dcho->color == NEGRO)) {

hm->color = ROJO;eliminar_caso1(n->padre);

} elseeliminar_caso4(n);

}

Caso 4: S y los hijos de éste son negros, pero P es rojo. En este caso, simplemente intercambiamos los colores de S y P. Esto no afecta al número de nodos negros en los caminos que no van a través de S, pero añade uno al número de nodos negros a los caminos que van a través de N, compensando así el borrado del nodo negro en dichos caminos. Si lo implementamos en C, quedaría:voideliminar_caso4(struct node *n){

struct node *hm = hermano_menor(n);

if ((n->padre->color == ROJO) && (hm->color == NEGRO) && (hm->izdo->color == NEGRO) && (hm->dcho->color == NEGRO)) {

hm->color = ROJO;n->padre->color = NEGRO;

} elseeliminar_caso5(n);

}

Caso 5: S es negro, su hijo izquierdo es rojo, el derecho es negro, y N es el hijo izquierdo de su padre. En este caso rotamos a la derecha S, así su hijo izquierdo se convierte en su padre y en el hermano de N. Entonces intercambiamos los colores de S y su nuevo padre. Todos los caminos tienen aún el mismo número de nodos negros, pero ahora N tiene un hermano negro cuyo hijo derecho es rojo, así que caemos en el caso 6. Ni N ni su padre son afectados por esta transformación (de nuevo, por el caso 6, reetiquetamos el nuevo hermano de N como S). He aquí la implementación en C:voideliminar_caso5(struct node *n){

struct node *hm = hermano_menor(n);

if ((n == n->padre->izdo) && (hm->color == NEGRO) && (hm->izdo->color == ROJO) && (hm->dcho->color == NEGRO)) {

hm->color = ROJO;hm->izdo->color = NEGRO;rotar_dcha(hm);

} else if ((n == n->padre->dcho) && (hm->color == NEGRO) && (hm->dcho->color == ROJO) && (hm->izdo->color == NEGRO)) {

hm->color = ROJO;hm->dcho->color = NEGRO }

eliminar_caso6(n);}

Caso 6: S es negro, su hijo derecho es rojo, y N es el hijo izquierdo de P, su padre. En este caso rotamos a la izquierda P, así que S se convierte en el padre de P y éste en el hijo derecho de S. Entonces intercambiamos los colores de P y S, y ponemos el hijo derecho de S en negro. El subárbol aún tiene el mismo color que su raíz, así que las propiedades 4 (los hijos de todo nodo rojo son negros) y 5 (todos los caminos desde cualquier nodo a sus nodos hoja contienen el mismo número de nodos negros) se verifican. Sin embargo, N tiene ahora un antecesor negro mas: o bien P se ha convertido en negro, o bien era negro y S se ha añadido como un abuelo negro. De este modo, los caminos que pasan por N pasan por un nodo negro mas. Mientras tanto, si un camino no pasa por N, entonces hay dos posibilidades:

Éste pasa a través del nuevo hermano de N. Entonces, éste debe pasar por S y P, al igual que antes, y tienen sólo que intercambiar los colores. Así los caminos contienen el mismo número de nodos negros.

Éste pasa por el nuevo tío de N, el hijo derecho de S. Éste anteriormente pasaba por S, su padre y su hijo derecho, pero ahora sólo pasa por S, el cual ha tomado el color de su anterior padre, y por su hijo derecho, el cual ha cambiado de rojo a negro. El efecto final es que este camino va por el mismo número de nodos negros.

De cualquier forma, el número de nodos negros en dichos caminos no cambia. De este modo, hemos restablecido las propiedades 4 (los hijos de todo nodo rojo son negros) y 5 (todos los caminos desde cualquier nodo a sus nodos hoja contienen el mismo número de nodos negros). El nodo blanco en diagrama puede ser rojo o negro, pero debe tener el mismo color tanto antes como después de la transformación. Adjuntamos el último algoritmo:voideliminar_caso6(struct node *n){

struct node *hm = hermano_menor(n);

hm->color = n->padre->color;n->padre->color = NEGRO;if (n == n->padre->izdo) {

/* * Aquí, hm->dcho->color == ROJO. */hm->dcho->color = NEGRO;rotar_izda(n->padre);

} else {/* * Aquí, hm->izdo->color == ROJO. */hm->izdo->color = NEGRO;rotar_dcha(n->padre);

}}

De nuevo, todas las llamadas de la función usan recursión de cola así que el algoritmo realiza sus operaciones sobre el propio árbol. Además, las llamadas no recursivas se harán después de una rotación, luego se harán un número de rotaciones (más de 3) que será constante.

Demostración de cotas

Un árbol rojo-negro que contiene n nodos internos tiene una altura de O(log(n)).

Hagamos los siguientes apuntes sobre notación:

H(v) = altura del árbol cuya raíz es el nodo v. bh(v) = número de nodos negros (sin contar v si es negro) desde v hasta cualquier hoja del subárbol

(llamado altura-negra).

Lema: Un subárbol enraizado al nodo v tiene al menos 2bh(v) − 1 nodos internos.

Demostración del lema (por inducción sobre la altura):

Caso base: h(v)=0 Si v tiene altura cero entonces debe ser árbol vacío, por tanto bh(v)=0. Luego:

2bh(''v'') − 1 = 20 − 1 = 1 − 1 = 0

Hipótesis de Inducción: si v es tal que h(v) = k y contiene 2bh(v) − 1 nodos internos, veamos que esto implica que v' tal que h(v') = k+1 contiene 2bh(v') − 1 nodos internos.

Si v' tiene h(v') > 0 entonces es un nodo interno. Como éste tiene dos hijos que tienen altura-negra, o bh(v') o bh(v')-1 (dependiendo si es rojo o negro). Por la hipótesis de inducción cada hijo tiene al menos 2bh(v') − 1 − 1 nodos internos, así que v' tiene :2bh(v') − 1 − 1 + 2bh(v') − 1 − 1 + 1 = 2bh(v') − 1 nodos internos.

Usando este lema podemos mostrar que la altura del árbol es algorítmica. Puesto que al menos la mitad de los nodos en cualquier camino desde la raíz hasta una hoja negra (propiedad 4 de un árbol rojo-negro), la altura-negra de la raíz es al menos h(raíz)/2. Por el lema tenemos que:

Por tanto, la altura de la raíz es O(log(n)).

Complejidad

En el código del árbol hay un bucle donde la raíz de la propiedad rojo-negro que hemos querido devolver a su lugar, x, puede ascender por el árbol un nivel en cada iteración Como la altura original del árbol es O(log n), hay O(log n) iteraciones. Así que en general la inserción tiene una complejidad de O(log n).

Árbol AAEn informática un árbol AA es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, Arne Andersson.

Los árboles AA son una variación del árbol rojo-negro, que a su vez es una mejora del árbol binario de búsqueda. A diferencia de los árboles rojo-negro, los nodos rojos en un árbol AA sólo pueden añadirse como un hijo derecho. En otras palabras, ningún nodo rojo puede ser un hijo izquierdo. De esta manera se simula un árbol 2-3 en lugar de un árbol 2-3-4, lo que simplifica las operaciones de mantenimiento. Los algoritmos de mantenimiento para un árbol rojo-negro necesitan considerar siete diferentes formas para balancear adecuadamente el árbol:

En un árbol AA, al cumplirse el estricto requisito de que sólo los enlaces derechos pueden ser rojos, sólo es necesario considerar dos formas:

Contenido

1 Rotaciones de balanceo 2 Inserción 3 Borrado 4 Rendimiento 5 Véase también 6 Referencias 7 Enlaces externos

Rotaciones de balanceo

En general, los árboles AA se implementan con la idea de un nivel en lugar de la de un color, a diferencia de los árboles rojo-negro. Cada nodo tiene un campo nivel y se deben cumplir las siguientes condiciones para que el árbol sea válido:

1. El nivel de un nodo hoja es uno.2. El nivel de un hijo izquierdo es estrictamente menor que el de su padre.3. El nivel de un hijo derecho es menor o igual que el de su padre.4. El nivel de un nieto derecho es estrictamente menor que el de su abuelo.5. Cada nodo de nivel mayor que uno debe tener dos hijos.

Sólo se necesitan dos operaciones para mantener el equilibrio en un árbol AA. Estas operaciones se llaman torsión (skew) y división (split). La torsión es una rotación derecha que se realiza cuando una inserción o un borrado genera un enlace horizontal izquierdo, puede pensarse como un enlace rojo izquierdo en el contexto del árbol rojo-negro. La división es una rotación izquierda condicional que tiene lugar cuando una inserción o un borrado crea dos enlaces horizontales derechos, lo que de nuevo se corresponde con dos enlaces rojos consecutivos en el contexto de los árboles rojo-negro.

function skew is input: T, a node representing an AA tree that needs to be rebalanced. output: Another node representing the rebalanced AA tree.

if nil(T) then return Nil else if level(left(T)) == level(T) then Swap the pointers of horizontal left links. L = left(T) left(T) := right(L) right(L) := T return L else return T end if

end function

Torsión:

function split is input: T, a node representing an AA tree that needs to be rebalanced. output: Another node representing the rebalanced AA tree.

if nil(T) then return Nil else if level(T) == level(right(right(T))) then We have two horizontal right links. Take the middle node, elevate it, and return it. R = right(T) right(T) := left(R) left(R) := T level(R) := level(R) + 1 return R else return T end ifend function

División:

Inserción

La inserción comienza con la búsqueda normal en un árbol binario y su procedimiento de inserción. Después, a medida que se desenrolla la pila de llamadas, es fácil comprobar la validez del árbol y realizar las rotaciones que se precisen. Si aparece un enlace horizontal izquierdo, se realiza una torsión, y si aparecen dos enlaces horizontales derechos, se realiza una división, posiblemente incrementando el nivel del nuevo nodo raíz del subárbol correspondiente. Observe que el código de muestra realiza un incremento de nivel(T). Lo que hace necesario continuar comprobando la validez del árbol a medida que las modificaciones suben desde las hojas.

function insert is input: X, the value to be inserted, and T, the root of the tree to insert it into. output: A balanced version T including X.

Do the normal binary tree insertion procedure. Set the result of the recursive call to the correct child in case a new node was created or the root of the subtree changes. if nil(T) then Create a new leaf node with X. return node(X, 1, Nil, Nil) else if X < value(T) then left(T) := insert(X, left(T)) else if X > value(T) then right(T) := insert(X, right(T)) end if

Note that the case of X == value(T) is unspecified. As given, an insert will have no effect. The implementor may desire different behavior.

Perform skew and then split. The conditionals that determine whether or not a rotation will occur or not are inside of the procedures, as given above. T := skew(T) T := split(T)

return Tend function

Borrado

Como en la mayoría de árboles binarios balanceados, el borrado de un nodo interno puede convertirse en el borrado de un nodo hoja al intercambiar el nodo interno bien con su predecesor o sucesor más próximo, dependiendo del que esté en el árbol o de los deseos del implementador. Para recuperar un predecesor símplemente se debe seguir un enlace izquierdo y después todos los enlaces derechos restantes. De forma similar, el sucesor se puede encontrar al ir una vez a la derecha una vez y a la izquierda hasta que se encuentre un puntero nulo. Dada la propiedad de los árboles AA de que todos los nodos de un nivel superior a uno tienen dos hijos, el nodo sucesor o predecesor tendrá nivel 1, haciendo que su eliminado sea trivial.

Para re-equilibrar un árbol existen diferentes aproximaciones. La que describió Andersson en su publicación original es la más simple, y se describirá aquí, aunque implementaciones reales pueden optar por un enfoque más optimizado. Tras un borrado, el primer paso para mantener la validez es reducir el nivel de todos los nodos cuyos hijos están dos niveles por debajo de ellos, o a los que les faltan hijos. Después, todo el nivel debe ser torsionado y dividido. Esta aproximación se ha visto favorecida por el hecho de que se basa en tres pasos independientes y fáciles de entender:

1. Decrementar el nivel, si es necesario.2. Torsionar el nivel.3. Dividir el nivel.

Sin embargo, debemos torsionar y dividir todo el nivel en lugar de un solo nodo lo que complica nuestro código.

function delete is input: X, the value to delete, and T, the root of the tree from which it should be deleted. output: T, balanced, without the value X.

if X > value(T) then right(T) := delete(X, right(T)) else if X < value(T) then left(T) := delete(X, left(T)) else If we're a leaf, easy, otherwise reduce to leaf case. if leaf(T) then return Nil else if nil(left(T)) then L := successor(T) right(T) := delete(L, right(T)) value(T) := L else L := predecessor(T) left(T) := delete(L, left(T)) value(T) := L end if end if

Rebalance the tree. Decrease the level of all nodes in this level if necessary, and then skew and split all nodes in the new level. T := decrease_level(T)

T := skew(T) right(T) := skew(right(T)) right(right(T)) := skew(right(right(T))) T := split(T) right(T) := split(right(T)) return Tend functionfunction decrease_level is input: T, a tree for which we want to remove links that skip levels. output: T with its level decreased.

should_be = min(level(left(T)), level(right(T))) + 1 if should_be < level(T) then level(T) := should_be if should_be < level(right(T)) then level(right(T)) := should_be end if end if return Tend function

Un buen ejemplo de borrado por este algoritmo está presente en la publicación de Andersson.

Rendimiento

El rendimiento de un árbol AA es equivalente al de un árbol rojo-negro. Un árbol AA realiza más rotaciones que un árbol red-black, pero la mayor sencillez de sus algoritmos tiende a hacerlos más rápidos, y estos factores se compensan resultando en un rendimiento similar. Un árbol rojo-negro es más constante en su rendimiento que un árbol AA, pero un árbol AA tiende a ser más llano lo que produce unos tiempos de búsqueda ligeramente más pequeños.[cita requerida]

Árbol multicaminoLos árboles multicamino o árboles multirrama son estructuras de datos de tipo árbol usadas en computación.

Contenido

1 Definición 2 Ventajas e inconvenientes

o 2.1 Nota 3 Véase también

Definición

Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.

Sea un árbol de m-caminos A, es un árbol m-caminos si y solo si:

A está vacío Cada nodo de A muestra la siguiente estructura:

[nClaves,Enlace0,Clave1,...,ClavenClaves,EnlacenClaves]

nClaves es el número de valores de clave de un nodo, pudiendo ser: 0 <= nClaves <= g-1Enlacei, son los enlaces a los subárboles de A, pudiendo ser: 0 <= i <= nClaves

Clavei, son los valores de clave, pudiendo ser: 1 <= i <= nClaves

Clavei < Clavei+1

Cada valor de clave en el subárbol Enlacei es menor que el valor de Clavei+1

Los subárboles Enlacei, donde 0 <= i <= nClaves, son también árboles m-caminos.

Existen muchas aplicaciones en las que el volumen de la información es tal, que los datos no caben en la memoria principal y es necesario almacenarlos, organizados en archivos, en dispositivos de almacenaminento secundario. Esta organización de archivos debe ser suficientemente adecuada como para recuperar los datos del mismo en forma eficiente.

Ventajas e inconvenientes

La principal ventaja de este tipo de árboles consiste en que existen más nodos en un mismo nivel que en los árboles binarios con lo que se consigue que, si el árbol es de búsqueda, los accesos a los nodos sean más rápidos.

El inconveniente más importante que tienen es la mayor ocupación de memoria, pudiendo ocurrir que en ocasiones la mayoría de los nodos no tengan descendientes o al menos no todos los que podrían tener desaprovechándose por tanto gran cantidad de memoria. Cuando esto ocurre lo más frecuente es transformar el árbol multicamino en su binario de búsqueda equivalente.

Nota

Un tipo especial de árboles multicamino utilizado para solucionar el problema de la ocupación de memoria son los árboles B o árboles Bayer.

o

5.1.1 Procedimiento o 5.2 Inserción o 5.3 Eliminación

5.3.1 Eliminación en un nodo hoja 5.3.2 Eliminación en un nodo interno

o 5.4 Rebalanceo después de la eliminación o 5.5 Construcción Inicial

6 Notas o 6.1 Multi-modo:combinar y dividir o 6.2 Relación entre U y L o 6.3 Acceso concurrente

7 Véase también 8 Enlaces externos

Definición

La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten. Dado que se permite un rango variable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables, pero por otro lado pueden desperdiciar memoria, porque los nodos no permanecen totalmente ocupados. Los límites superior e

inferior en el número de nodos hijo son definidos para cada implementación en particular. Por ejemplo, en un árbol-B 2-3 (A menudo simplemente llamado árbol 2-3 ), cada nodo sólo puede tener 2 ó 3 nodos hijo.

Un árbol-B se mantiene balanceado porque requiere que todos los nodos hoja se encuentren a la misma altura.

Los árboles B tienen ventajas sustanciales sobre otras implementaciones cuando el tiempo de acceso a los nodos excede al tiempo de acceso entre nodos. Este caso se da usualmente cuando los nodos se encuentran en dispositivos de almacenamiento secundario como los discos rígidos. Al maximizar el número de nodos hijo de cada nodo interno, la altura del árbol decrece, las operaciones para balancearlo se reducen, y aumenta la eficiencia. Usualmente este valor se coloca de forma tal que cada nodo ocupe un bloque de disco, o un tamaño análogo en el dispositivo. Mientras que los árboles B 2-3 pueden ser útiles en la memoria principal, y además más fáciles de explicar, si el tamaño de los nodos se ajustan para caber en un bloque de disco, el resultado puede ser un árbol B 129-513.

Los creadores del árbol B, Rudolf Bayer y Ed McCreight, no han explicado el significado de la letra B de su nombre. Se cree que la B es de balanceado, dado que todos los nodos hoja se mantienen al mismo nivel en el árbol. La B también puede referirse a Bayer, o a Boeing, porque sus creadores trabajaban en el Boeing Scientific Research Labs en ese entonces.

Definición técnica

B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo.

Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface las siguientes propiedades:

1. Cada nodo tiene como máximo M hijos.2. Cada nodo (excepto raíz y hojas) tiene como mínimo M/2 hijos.3. La raíz tiene al menos 2 hijos si no es un nodo hoja.4. Todos los nodos hoja aparecen al mismo nivel.5. Un nodo no hoja con k hijos contiene k-1 elementos almacenados.6. Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertas condiciones:

1. El primero tiene valor menor que r1.2. El segundo tiene valor mayor que r1 y menor que r2, etc.3. El último hijo tiene valor mayor que rm.

Altura: El mejor y el peor caso

En el mejor de los casos,la altura de un árbol-B es:

logMn

En el peor de los casos,la altura de un árbol-B es:

Donde M es el número máximo de hijos que puede tener un nodo.

Estructura de los nodos

Cada elemento de un nodo interno actúa como un valor separador, que lo divide en subárboles. Por ejemplo, si un nodo interno tiene tres nodos hijo, debe tener dos valores separadores o elementos a1 y a2. Todos los valores

del subárbol izquierdo deben ser menores a a1, todos los valores del subárbol del centro deben estar entre a1 y a2, y todos los valores del subárbol derecho deben ser mayores a a2.

Los nodos internos de un árbol B, es decir los nodos que no son hoja, usualmente se representan como un conjunto ordenado de elementos y punteros a los hijos. Cada nodo interno contiene un máximo de U hijos y, con excepción del nodo raíz, un mínimo de L hijos. Para todos los nodos internos exceptuando la raíz, el número de elementos es uno menos que el número de punteros a nodos. El número de elementos se encuentra entre L-1 y U-1. El número U debe ser 2L o 2L-1, es decir, cada nodo interno está por lo menos a medio llenar. Esta relación entre U y L implica que dos nodos que están a medio llenar pueden juntarse para formar un nodo legal, y un nodo lleno puede dividirse en dos nodos legales (si es que hay lugar para subir un elemento al nodo padre). Estas propiedades hacen posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.

Los nodos hoja tienen la misma restricción sobre el número de elementos, pero no tienen hijos, y por tanto carecen de punteros.

El nodo raíz tiene límite superior de número de hijos, pero no tiene límite inferior. Por ejemplo, si hubiera menos de L-1 elementos en todo el árbol, la raíz sería el único nodo del árbol, y no tendría hijos.

Un árbol B de altura n+1 puede contener U veces por elementos más que un árbol B de profundidad n, pero el costo en la búsqueda, inserción y eliminación crece con la altura del árbol. Como todo árbol balanceado, el crecimiento del costo es más lento que el del número de elementos.

Algunos árboles balanceados guardan valores sólo en los nodos hoja, y por lo tanto sus nodos internos y nodos hoja son de diferente tipo. Los árboles B guardan valores en cada nodo, y pueden utilizar la misma estructura para todos los nodos. Sin embargo, como los nodos hoja no tienen hijos, una estructura especial para éstos mejora el funcionamiento.

class nodo árbol B en c++#include <iostream.h>#include <stdlib.h> #define TAMANO 1000 struct stclave { int valor; long registro;}; class bnodo { public: bnodo (int nClaves); // Constructor ~bnodo (); // Destructor private: int clavesUsadas; stclave *clave; bnodo **puntero; bnodo *padre; friend class btree;};

Algoritmos

Búsqueda

La búsqueda es similar a la de los árboles binarios. Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo. Típicamente se utiliza la búsqueda binaria para determinar esta posición relativa.

Procedimiento

ejemplo2 inserción en árbol B.

1. Situarse en el nodo raíz.2. (*) Comprobar si contiene la clave a buscar.

1. Encontrada fin de procedimiento.2. No encontrada:

1. Si es hoja no existe la clave.2. En otro caso el nodo actual es el hijo que corresponde:

1. La clave a buscar k < k1: hijo izquierdo.2. La clave a buscar k > ki y k < ki+1 hijo iésimo.3. Volver a paso 2(*).

Inserción

Todas las inserciones se hacen en los nodos hoja.

1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.

2. Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos.

3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera: 1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.

2. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador.

3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.

Si las divisiones de nodos suben hasta la raíz, se crea una nueva raíz con un único elemento como valor separador, y dos hijos. Es por esto por lo que la cota inferior del tamaño de los nodos no se aplica a la raíz. El máximo número de elementos por nodo es U-1. Así que debe ser posible dividir el número máximo de elementos U-1 en dos nodos legales. Si este número fuera impar, entonces U=2L, y cada uno de los nuevos nodos tendrían (U-2)/2 = L-1 elementos, y por lo tanto serían nodos legales. Si U-1 fuera par, U=2L-1, así que habría 2L-2 elementos en el nodo. La mitad de este número es L-1, que es el número mínimo de elementos permitidos por nodo.

Un algoritmo mejorado admite una sola pasada por el árbol desde la raíz,hasta el nodo donde la inserción tenga lugar,dividiendo todos los nodos que estén llenos encontrados a su paso.Esto evita la necesidad de volver a cargar en memoria los nodos padres,que pueden ser caros si los nodos se encuentran en una memoria secundaria.Sin embargo,para usar este algoritmo mejorado, debemos ser capaces de enviar un elemento al nodo padre y dividir el resto U-2 elementos en 2 nodos legales,sin añadir un nuevo elemento.Esto requiere que U=2L en lugar de U=L-1,lo que explica por qué algunos libros de texto imponen este requisito en la definición de árboles-B.

Eliminación

La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades. Hay dos estrategias populares para eliminar un nodo de un árbol B.

localizar y eliminar el elemento, y luego corregir, o hacer una única pasada de arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar

el árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin necesidad de continuar reestructurando

Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser un separador de un nodo interno. Segundo, puede suceder que al borrar el elemento, el número de elementos del nodo quede debajo de la cota mínima. Estos problemas se tratan a continuación en orden.

Eliminación en un nodo hoja

Busque el valor a eliminar. Si el valor se encuentra en un nodo hoja, se elimina directamente la clave, posiblemente dejándolo con

muy pocos elementos; por lo que se requerirán cambios adicionales en el árbol.

eliminar clave 20 de un nodo interno.

Eliminación en un nodo interno

Cada elemento de un nodo interno actúa como valor separador para dos subárboles, y cuando ese elemento es eliminado, pueden suceder dos casos. En el primero, tanto el hijo izquierdo como el derecho tienen el número mínimo de elementos, L-1. Pueden entonces fundirse en un único nodo con 2L-2 elementos, que es un número que no excede U-1 y por lo tanto es un nodo legal. A menos que se sepa que este árbol B en particular no tiene datos duplicados, también se debe eliminar el elemento en cuestión (recursivamente) del nuevo nodillo.

En el segundo caso, uno de los dos nodos hijos tienen un número de elementos mayor que el mínimo. Entonces se debe hallar un nuevo separador para estos dos subárboles. Note que el mayor elemento del árbol izquierdo es el mayor elemento que es menor que el separador. De la misma forma, el menor elemento del subárbol derecho es el menor elemento que es mayor que el separador. Ambos elementos se encuentran en nodos hoja, y cualquiera de los dos puede ser el nuevo separador.

Si el valor se encuentra en un nodo interno, escoja un nuevo separador (puede ser el mayor elemento del subárbol izquierdo o el menor elemento del subárbol derecho), elimínelo del nodo hoja en que se encuentra, y reemplace el elemento a eliminar por el nuevo separador.

Como se ha eliminado un elemento de un nodo hoja, se debe tratar este caso de manera equivalente.

Rebalanceo después de la eliminación

Si al eliminar un elemento de un nodo hoja el nodo se ha quedado con menos elementos que el mínimo permitido, algunos elementos se deben redistribuir. En algunos casos el cambio lleva la deficiencia al nodo padre, y la redistribución se debe aplicar iterativamente hacia arriba del árbol, quizá incluso hasta a la raíz. Dado que la cota mínima en el número de elementos no se aplica a la raíz, el problema desaparece cuando llega a ésta.

La estrategia consiste en hallar un hermano para el nodo deficiente que tenga más del mínimo número de elementos y redistribuir los elementos entre los hermanos para que todos tengan más del mínimo. Esto también cambia los separadores del nodo padre.

Si el nodo hermano inmediato de la derecha del nodo deficiente tiene más del mínimo número de elementos, escoja el valor medio entre el separador y ambos hermanos como nuevo separador y colóquelo en el padre.

Redistribuya los elementos restantes en los nodos hijo derecho e izquierdo. Redistribuya los subárboles de los dos nodos . Los subárboles son trasplantados por completo, y no se

alteran si se mueven a un otro nodo padre, y esto puede hacerse mientras los elementos se redistribuyen. Si el nodo hermano inmediato de la derecha del nodo deficiente tiene el mínimo número de elementos,

examine el nodo hermano inmediato de la izquierda. Si los dos nodos hermanos inmediatos tienen el mínimo número de elementos, cree un nuevo nodo con

todos los elementos del nodo deficiente, todos los elementos de uno de sus hermanos, colocando el separador del padre entre los elementos de los dos nodos hermanos fundidos.

Elimine el separador del padre, y reemplace los dos hijos que separaba por el nuevo nodo fundido. Si esa acción deja al número de elementos del padre por debajo del mínimo, repita estos pasos en el

nuevo nodo deficiente, a menos que sea la raíz, ya que no tiene cota mínima en el número de elementos.

Construcción Inicial

En aplicaciones, es frecuentemente útil construir un árbol-B para representar un gran número de datos existentes y después actualizarlo de forma creciente usando operaciones Standard de los árboles-B. En este caso, el modo más eficiente para construir el árbol-B inicial no sería insertar todos los elementos en el conjunto inicial sucesivamente, si no construir el conjunto inicial de nodos hoja directamente desde la entrada, y después construir los nodos internos a partir de este conjunto. Inicialmente, todas las hojas excepto la última tienen un elemento más, el cual será utilizado para construir los nodos internos. Por ejemplo, si los nodos hoja tienen un tamaño máximo de 4 y el conjunto inicial es de enteros desde el 1 al 24, tenemos que construir inicialmente 5 nodos hoja conteniendo 5 valores cada uno (excepto el último que contiene 4):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Construiremos el siguiente nivel hacia arriba desde las hojas tomando el último elemento de cada hoja excepto el último. De nuevo, cada nodo excepto el último contendrá un valor más. En el ejemplo, es supuesto que los nodos internos contienen como mucho 2 valores (por lo que pueden tener 3 hijos). Luego el siguiente nivel de nodos internos nos quedaría de la siguiente manera:

510

15 20

1 2 3 4 6 7 8 9 11 12 13 14 16 17 18 19 21 22 23 24

Este proceso se continuará hasta que alcancemos un nivel con un solo nodo y no esta sobrecargado. En nuestro ejemplo solo nos quedaría el nivel de la raíz:

15

5 10 20

1 2 3 4 6 7 8 9 11 12 13 14 16 17 18 19 21 22 23 24

Notas

Cada nodo tendrá siempre entre L y U hijos incluidos con una excepción: el nodo raíz debe tener entre 2 y U hijos. En otras palabras, la raíz está exenta de la restricción del límite inferior. Esto permite al árbol sostener un pequeño número de elementos. Un nodo raíz con un solo hijo no tendría sentido, ya que podríamos añadírselo a la raíz. Un nodo raíz sin hijos es también innecesario, ya que un árbol sin hijos se suele representar sin raíz.

Multi-modo:combinar y dividir

Es posible modificar el algoritmo anterior, cuando tratamos de encontrar más elementos para un nodo al que le faltan, examinamos a los hermanos, y si alguno tiene más del valor mínimo de números, reordenamos los valores de los hermanos de un extremo a otro para rellenar al mínimo el nodo al que le faltan. De la misma manera, cuando un nodo se divide, los elementos extra pueden ser movidos cerca, por ejemplo a hermanos menos poblados; o la división puede dar lugar a un número de hermanos, redistribuyendo los elementos entre ellos en lugar de dividir un nodo.

En la práctica, el uso más común de los árboles-B implica mantener los nodos una memoria secundaria, donde será lento acceder a un nodo que no haya sido usado con anterioridad. Utilizando solo divisiones y combinaciones, disminuimos el número de nodos que se necesitan para la mayoría de situaciones comunes, pero podrían ser útiles en otras.

Relación entre U y L

Es casi universal el dividir nodos eligiendo un elemento medio y creando dos nuevos nodos. Esto limita la relación entre L y U. Si intentamos insertar un elemento dentro de un nodo con U elementos, esto conlleva una redistribución de U elementos. Uno de estos, el intermedio, será trasladado al nodo padre, y los restantes serán divididos equitativamente, en la medida de lo posible, entre los dos nuevos nodos.

Por ejemplo, en un árbol-B 2-3, añadiendo un elemento a un nodo que ya contiene 3 hijos, y por consiguiente 2 valores separadores (padres), da lugar a 3 valores (los dos separadores y el nuevo valor). El valor medio se convierte en el nuevo separador (padre), y los otros valores se hacen independientes y con 2 hijos. Por lo general, si U es impar, cada uno de los nuevos nodos tienen (U+2)/2 hijos. Si U es par, unos tiene U/2 hijos y el otro U/2+1.

Si un nodo está completo y se divide exactamente en 2 nodos, L debe tener un tamaño permitido, lo suficiente pequeño, una vez q el nodo ha sido divido. También es posible dividir nodos completos en más de dos nodos nuevos. Eligiendo dividir un nodo en más de 2 nodos nuevos requerirá un valor más pequeño para L para el mismo valor de U. Como L se hace más pequeño, esto permite que haya más espacio sin usar en los nodos. Esto disminuirá la frecuencia de división de nodos, pero de la misma manera aumentará la cantidad de memoria que se necesita para almacenar el mismo número de valores, y el número de nodos que tienen que ser examinados para una operación particular.

Acceso concurrente

Lehman y Yao nos mostraron que uniendo los bloques de árboles en cada nivel, con un puntero al siguiente nivel, en una estructura de árbol, donde los permisos de lectura de los bloques del árbol se pueden evitar, por que el árbol desciende desde la raíz hasta las hojas por búsqueda e inserción. Los permisos de escritura solo se requieren cuando un bloque del árbol es modificado. Minimizando los permisos a un nodo colgante simple, solo durante su modificación ayuda a maximizar el acceso concurrente por múltiples usuarios. Un dato a ser considerado en las bases de datos, por ejemplo y/o otro árbol basado en ISAM (Métodos Indexados de Acceso Secuencial) métodos de almacenamiento.

Árbol-B+

Un árbol B+ simple (una variación del árbol B) que enlaza los elementos 1 al 7 a valores de datos d1-d7. Note la lista enlazada (en rojo) que permite el recorrido de los elementos en orden.

En informática, un árbol-B es un tipo de estructura de datos de árboles. Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo.

Un árbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste respecto un árbol-B, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo, más bajo nivel. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.

El número máximo de claves en un registro es llamado el orden del árbol-B+.

El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol-B+ es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves.

El número de claves que pueden ser indexadas usando un árbol-B+ está en función del orden del árbol y su altura.

Para un árbol-B+ de orden n, con una altura h:

Número máximo de claves es: nh

Número mínimo de claves es: 2(n / 2)h − 1

El árbol-B+ fue descrito por primera vez en el documento "Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indexes. Acta Informática 1: 173-189 (1972)".

Árbol-B*Un árbol-B* es una estructura de datos de árbol, una variante de Árbol-B utilizado en los sistemas de ficheros HFS y Reiser4, que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2. Para mantener esto los nodos, en lugar de generar inmediatamente un nodo cuando se llenan, comparten sus claves con el nodo adyacente. Cuando ambos están llenos, entonces los dos nodos se transforman en tres. También requiere que la clave más a la izquierda no sea usada nunca.

No se debe confundir un árbol-B* con un árbol-B+, en el que los nodos hoja del árbol están conectados entre sí a través de una lista enlazada, aumentando el coste de inserción para mejorar la eficiencia en la búsqueda.

Transformación de un Arbol Gral. En un Arbol Binario.

En esta sección estableceremos los mecanismos necesarios para convertir un árbol general en un árbol binario. Para esto, debemos seguir los pasos que se describen a continuación:

1. Enlazar los hijos de cada nodo en forma horizontal (los hermanos). 2. Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a la izquierda. Además,

debe eliminarse el vínculo de ese padre con el resto de sus hijos. 3. Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y así se obtendrá el árbol

binario correspondiente.