Estructura De Datos Wikipedia) 2m6y3m

vector v; // Si no se especifica el tamaño inicial es 0 for (int i=0 ; i<5 ; i++) { v.push_back(2*i); // inserta un elemento al final del vector }

El ejemplo anterior está hecho para el lenguaje C++. En C, para crear vectores dinámicos se tendrían que utilizar las instrucciones malloc y realloc para reservar memoria de forma dinámica (ver librería stdlib.h), y la función por free para liberar la memoria utilizada. Resultado: 0 1 2 3 4 0 2 4 6 8

El resultado de los dos ejemplos es el mismo vector

Vectores multidimensionales En Basic, Java y otros lenguajes es posible declarar matrices multidimensionales, entendiéndolas como un vector de vectores. En dichos casos en número de elementos del vector es el producto resultante de cada dimensión. Por ejemplo el vector v(4,1) tiene 10 elementos se calcula del siguiente modo: (0-4) * (0-1). Los elementos de la primera dimensión del vector contiene 5 elementos que van del '0' al '4' y la 2º dimensión tiene 2 elementos que van desde '0' a '1'. Los elementos serían accedidos del siguiente modo: elemento 1: (0,0) elemento 2: (0,1) elemento 3: (1,0) ... 4

elemento 8: (3,1) elemento 9: (4,0) elemento 10: (4,1)

Registro (estructura de datos) Un registro, en programación, es un tipo de dato estructurado formado por la unión de varios elementos bajo una misma estructura. Estos elementos pueden ser, o bien datos elementales (entero, real, carácter,...), o bien otras estructuras de datos. A cada uno de esos elementos se le llama campo. Un registro se diferencia de un vector en que éste es una colección de datos iguales, es decir, todos del mismo tipo, mientras que en una estructura los elementos que la componen, aunque podrían serlo, no tiene porque ser del mismo tipo.

Ejemplo: Creación de un registro (o estructura) en C Un ejemplo de como se declararía un registro en C podría ser: typedef struct TipoNodo { int dato; struct TipoNodo *sig; struct TipoNodo *ant; } TNodo;

En este ejemplo se define el tipo de dato TNodo (o struct TipoNodo, sería equivalente) como una estructura (registro) que contiene un dato de tipo entero y dos punteros sig y ant (siguiente y anterior) que sirven para referenciar a otros registros del tipo TNodo. Ésta es la estructura de datos que se suele utilizar como nodo en las listas doblemente enlazadas.

Registro en bases de datos El concepto de registro que se acaba de presentar es muy similar al concepto de registro en bases de datos, este segundo se refiere a una colección de datos que hacen referencia a un mismo ítem que se van a guardar en una fila de una tabla de la base de datos...

Tipo de datos algebraico En matemáticas discretas es usual introducir definiciones de estructuras recursivas dando los casos de definición y un axioma de clausura indicando que ninguna otra cosa forma parte de lo definido. Por ejemplo, los árboles con información en los nodos pueden definirse como sigue: Sea T un conjunto. Los árboles con información en los nodos son todos los valores que se pueden construir con las reglas siguientes. 1. El árbol vacío es un árbol y es representado con la constante AVacio. 5

2. Si t1 y t2 son árboles, y x es un elemento de T, entonces Nodo(t1,x,t2) es un árbol. 3. Los árboles son únicamente los valores que se construyen utilizando las reglas 1 y 2.

La construcción correspondiente en los lenguajes de programación se llama Tipo de datos algebraico. Sus reglas de tipo polimórficas fueron introducidas por Robin Milner junto con la definición del lenguaje Standard ML y han sido adoptadas desde entonces en diversos lenguajes de programación, sobre todo en los lenguajes de programación funcionales. Por ejemplo, la definición del tipo árbol binario con información en los nodos de tipo T se escribe en Ocaml como sigue: type 'T Arbol = AVacio | Nodo of ('T Arbol * 'T * 'T Arbol)

y en sintaxis de Haskell: data Arbol T = AVacio | Nodo (Arbol T) T (Arbol T)

Los constructores del tipo Árbol son AVacio y Nodo los cuales, al recibir los argumentos necesarios producen un valor del tipo árbol. Por ejemplo, en Ocaml, AVacio es un árbol al igual que Nodo (AVacio,5,AVacio). Las operaciones sobre los tipos recursivos se generalmente se escriben utilizando la construcción de llamada por patrones. Por ejemplo, en Haskell, el número de niveles de un árbol de define como: niveles :: Arbol T -> Int niveles AVacio = 0 niveles (Nodo i n d) = 1 + max (niveles i) (niveles d)

en Standard ML la misma función se escribe fun niveles AVacio = 0 | niveles Nodo(i,n,d) = 1 + max (niveles i) (niveles d)

Corrección de programas A cada tipo de datos algebraico corresponde el orden bien fundamentado de subtérminos y un esquema de inducción estructural sobre la base de la definición del tipo. En el caso de los árboles éstos son los siguientes:

Para demostrar la terminación de la función niveles aplicando este esquema de inducción estructural, se tiene que demostrar, utilizando las reglas semánticas del lenguaje, que la expresión (niveles AVacio) termina y que si (niveles i) y (niveles d) terminan entonces (niveles (Nodo (i, n, d)) termina también. La llamada por patrones es una operación compleja que puede definirse con ayuda de dos primitivas, El operador is permite identificar el caso particular de una definición y la definición estructurada de variables permite obtener los componentes de un caso ya identificado: 6

En el ejemplo de árboles, el predicado e is AVacio es cierto cuando el árbol e es efectivamente un árbol vacío y e is Nodo es cierto cuando e es un nodo. Una definición del tipo let Nodo (u, x, v) = e ..., que sólo tiene sentido cuando e is Nodo es cierto, permite asociar a las variables u, x, v los componentes del nodo.

Lista (informática) 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 y/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 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.

Historia Las listas enlazadas fueron desarrolladas en 1955-56 por Santiago Fazzini, 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 t 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 7

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 U), mini-Flex (la misma U) y Flex9 (para el Motorola 6809 U). 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 y/o 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

8

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 o a la lista vacía si es el primer nodo; y otro que apunta al siguiente nodo siguiente, o apunta al valor NULL o a la lista vacía 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 un 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 s al primer nodo desde el puntero del último nodo.

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 a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de 9

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 y/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 práctica 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 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.

Listas Enlazadas vs. Arrays 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) Persistencia

No

Localización

Buena

O(1) Simples sí Mala 10

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 acaban 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 aleatorio mientras que las listas enlazadas sólo permiten 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 elemento por su índice rápidamente, como el heapsort. El 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 predeterminada 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 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 en ambas direcciones.

11

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 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 contienen, 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 punteros 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 punteros 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 principio de la lista y la posibilidad de asignaciones accidentales. Por el contrario, usan demasiado almacenamiento extra y resultan complicados en algunas operaciones.

Operaciones sobre listas enlazadas Cuando 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 variable PrimerNodos que siempre apunta al primer nodo de la 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 {

12

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

13

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, como el diagrama muestra: 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

14

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 variable UltimoNodo que apunte a algún nodo en la lista

15

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: This simple function inserts a node into a doubly-linked circularly-linked list after a given element: 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

16

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 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. Aquí un ejemplo: record Entry { integer next; // índice de la nueva entrada en el array integer prev; // entrada previa string name; real balance; }

Creado un array con esta estructura, y una variable entere para almacenar el índice del primer elemento, una lista enlazada puede ser construida: integer listHead; Entry Records[1000];

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.

17

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. Aquí tenemos un ejemplo completo en C: #include <stdio.h> #include <stdlib.h>

/* for printf */ /* 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");

18

} 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 (primera) */ list_remove(&n->next); /* eliminar segundo nodo del final(0)*/ list_remove(&n); /* eliminar ultimo nodo (3) */ list_print(n);

el

1

.

***

return 0; }

Y ahora una posible especificación de Listas Enlazadas 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} concatenacion

ListaGen{X}

->

ListaGen{X}

[assoc

id:

crear

]

op invertir : ListaGen{X} -> ListaGen{X} . op resto

: ListaGenNV{X} -> ListaGen{X} .

*** selectores

19

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

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 s 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. 20

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.

Ejemplos de almacenamiento interno y externo Suponiendo que queremos crear una lista enlazada de familias y sus . 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 // de la lista de de la familia }

Para mostrar una lista completa de familias y sus 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. // coger cabeza de esta lista de de esta familia while aMember ≠ null { //bucle para recorrer la lista de print information about member aMember := aMember.next } aFamily := aFamily.next }

21

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 // cabeza de la lista de de esta familia }

Para mostrar una lista completa de familias y sus 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. // coger lista de de familia while memNode ≠ null { bucle de lista de aMember := (member) memNode.data // extraer miembro del nodo print information about member memNode := memNode.next } famNode := famNode.next }

Hay que fijarse en 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 , 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 22

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.

Referencias 1. ↑ Preiss, Bruno R. (1999), Data Structures and Algorithms with Object-Oriented Design Patterns in Java, Wiley, p. page 97, 165, ISBN 0471-34613-6, http://www.brpreiss.com/books/opus5/html/page97.html 2. ↑ If maintaining a link to the tail of the list, time is O(1); if the entire list must be searched to locate the tail link, O(n) National Institute of Standards and Technology (August 16, 2004). Definition of a linked list. Retrieved December 14, 2004. Antonakos, James L. and Mansfield, Kenneth C., Jr. Practical Data Structures Using C/C++ (1999). PrenticeHall. ISBN 0-13-280843-9, pp. 165–190 Collins, William J. Data Structures and the Java Collections Framework (2002,2005) New York, NY: McGraw Hill. ISBN 0-07-282379-8, pp. 239–303 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introductions to Algorithms (2003). MIT Press. ISBN 0-262-03293-7, pp. 205–213, 501–505 Green, Bert F. Jr. (1961). Computer Languages for Symbol Manipulation. IRE Transactions on Human Factors in Electronics. 2 pp. 3-8. 23

McCarthy, John (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM. [1] HTML DVI PDF PostScript Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sections 2.2.3–2.2.5, pp.254–298. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.2: Linked lists, pp.204– 209. Newell, Allen and Shaw, F. C. (1957). Programming the Logic Theory Machine. Proceedings of the Western t Computer Conference. pp. 230-240. Parlante, Nick (2001). Linked list basics. Stanford University. PDF Sedgewick, Robert Algorithms in C (1998). Addison Wesley. ISBN 0-201-31452-5, pp. 90–109 Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis (1998). NJ: Prentice Hall. ISBN 0-13-660911-2, pp. 77–102 Wilkes, Maurice Vincent (1964). An Experiment with a Self-compiling Compiler for a Simple List-Processing Language. Annual Review in Automatic Programming 4, 1. Published by Pergamon Press. Wilkes, Maurice Vincent (1964). Lists and Why They are Useful. Proceeds of the ACM National Conference, Philadelphia 1964 (ACM Publication P-64 page F1-1); Also Computer Journal 7, 278 (1965). Kulesh Shanmugasundaram (April 4, 2005). Linux Kernel Linked List Explained.

Skip list Una skip list o lista por saltos es una Estructura de datos, basada en Listas enlazadas paralelas con eficiencia comparable a la de un árbol binario (tiempo en orden O(log n) para la mayoría de las operaciones). Una lista por saltos se construye por capas. La capa del fondo es una sencilla lista enlazada. Cada capa subsiguiente es como una "vía rápida" para la lista de la capa anterior. Un elemento de la capa i aparece en la capa i+1 con una probabilidad fija p. En promedio, cada elemento aparece en 1/(1-p) listas, el elemento más alto (generalmente un elemento inicial colocado al principio de la lista por saltos) aparece en O(log(1/p) n) listas.

Para buscar un elemento, se inicia con el elemento inicial de la lista de la capa más alta hasta alcanzar el máximo elemento que es menor o igual al buscado, se pasa a la capa anterior y se continua la búsqueda. Se puede verificar que el número esperado de pasos en cada lista enlazada es 1/p. De manera que el costo total de búsqueda es O(log(1/p) n / p), que es lo mismo que O(log n) cuando p es una constante. Dependiendo del valor escogido para p, se puede favorecer el costo de búsqueda contra el costo de almacenamiento.

24

Las operaciones de inserción y borrado se implantan como las de sus correspondientes listas enlazadas, salvo que los elementos de las capas superiores deben ser insertados o borrados de más de una lista enlazada. A diferencia de los árboles de búsqueda balanceados, el peor caso para las operaciones de listas por saltos no está garantizado como logarítmico, dado que es posible aunque poco probable, que se produzca una estructura no balanceada. Sin embargo, las listas por saltos trabajan bien en la práctica y el esquema de balanceo es más sencillo de implementar que el de los árboles binarios balanceados. Las listas por saltos son útiles también para cómputo paralelo, dado que se pueden realizar inserciones en paralelo sobre segmentos diferentes sin tener luego que balancear la estructura.

Origen Las listas por saltos fueron creadas por William Pugh y publicadas en su artículo Skip lists: a probabilistic alternative to balanced trees in Communications of the ACM, June 1990, 33(6) 668-676. Véase también en [1]. El creador de la estructura de datos las describe así: Las listas por saltos son una estructura probabilística que podría remplazar los árboles balanceados como método de implementación preferido en muchas aplicaciones. Las operaciones de listas por saltos tienen el mismo comportamiento asintótico esperado que las de los árboles balanceados, son más rápidas y utilizan menos espacio.

Pila (informática) Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de 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 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 25

elemento, que es retirado de la pila permitiendo el 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.

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 , 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. 26

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 Python class 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))]

27

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

En C++ #ifndef PILA #define PILA // define la pila template class Pila { private: struct Nodo { T elemento; Nodo* siguiente; // coloca el nodo en la segunda posicion }* ultimo; unsigned int elementos; public: Pila() { elementos = 0; } ~Pila() { while (elementos != 0) pop(); } void push(const T& elem) {

28

Nodo* aux = new Nodo; aux->elemento = elem; aux->siguiente = ultimo; ultimo = aux; ++elementos; } void pop() { Nodo* aux = ultimo; ultimo = ultimo->siguiente; delete aux; --elementos; } T cima() const { return ultimo->elemento; } bool vacia() const { return elementos == 0; } unsigned int altura() const { return elementos; } }; #endif

En Pascal UNIT Pila; INTERFACE Uses Elemento; Type TPila=^TNodo; TNodo=RECORD info:TElemento; ant:TPila; END; PROCEDURE CrearPilaVacia (VAR p:Tpila); PROCEDURE InsertarEnPila (e:TElemento; VAR p:TPila); PROCEDURE Cima(p:TPila; VAR c:TElemento); FUNCTION EsPilaVacia(p.Tpila):boolean; PROCEDURE Desapilar (VAR p: TPila); IMPLEMENTATION PROCEDURE CrearPilaVacia (VAR p:Tpila); BEGIN Destruir(p); p:=NIL; END

29

PROCEDURE InsertarEnPila (e:TElemento; VAR p:TPila); VAR paux:TPila; BEGIN new(paux); paux^.info:=e; paux^.ant:=p; p:=paux; END; PROCEDURE Cima(p:TPila; VAR c:TElemento); BEGIN e:=p^.info; END; FUNCTION EsPilaVacia(p: TPila): Boolean; BEGIN EsPilaVacia := (p=NIL); END; PROCEDURE Desapilar (VAR p: TPila); VAR auxPNodo: TPila; BEGIN IF NOT EsPilaVacia(p) THEN BEGIN auxPNodo:=p; p:=p^.ant; dispose(auxPNodo); END; END; PROCEDURE Destruir (VAR p:TPila); BEGIN WHILE NOT EsPilaVacia(p) DO Desapilar(pila); END; END.

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.

30

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 Fresa Fresa

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

Fresa Manzana Manzana

31

Plátano

==rotar a la izquierda==>

Manzana

Fresa 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 Us 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 32

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 sintaxis 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 necesarios: 12+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 1 2 + 4 * 3 +

OPERACION Apilar operando Apilar operando Añadir Apilar operando Multiplicar Apilar operando Añadir

PILA 1 1, 2 3 3, 4 12 12, 3 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 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. 33

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 cierta 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 procedimiento y el link que permite retornar a su invocador. Esto 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 provocaríamos 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.

34

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.

Usos concretos de la cola [editar] 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 todas 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).

35

Información adicional Teóricamente, la característica de las colas es que tienen una capacidad específica. Por muchos elementos que contengan siempre se puede añadir un elemento más y 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. (Ver 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

36

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] . *** var var var var

variables CCNV : ColaNV{VColaInt} . CC : Cola{VColaInt} . CE : Cola{VInt} . E : Int .

*** ecuaciones eq 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 Cola { private: struct Nodo { T elemento; Nodo* siguiente; // coloca el nodo en la segunda posicion }* primero; Nodo* ultimo; unsigned int elementos; public: Cola() { elementos = 0; }

37

~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;

38

NodoFinal=null; }

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]; N = 4; Frente = -1; Final = -1;

// Arreglo lineal de 5

} 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(); } }

39

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)

40

{ 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.

Cola de prioridades (estructura de datos) Una cola de prioridades es una estructura de datos en la que 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.

Características generales Este tipo especial de colas tienen las mismas operaciones que las colas FIFO, pero con la condición de que los elementos se atienden en orden de prioridad. Ejemplos de la vida diaria serían la sala de urgencias de un hospital, ya que los enfermos se van atendiendo en función de la gravedad de su enfermedad. Entendiendo la prioridad como un valor numérico y asignando a altas prioridades valores pequeños, las colas de prioridad nos permiten añadir elementos en cualquier orden y recuperarlos de menor a mayor.

41

Implementación 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.

Tipos Colas de prioridades con ordenamiento ascendente: en ellas los elementos se insertan de forma arbitraria, pero a la hora de extraerlos, se extrae el elemento de menor prioridad. Colas de prioridades con ordenamiento descendente: son iguales que la colas de prioridad con ordenamiento ascendente, pero al extraer el elemento se extrae el de mayor prioridad.

Operaciones Las operaciones de las colas de prioridad son las mismas que las de las colas genéricas: Crear: se crea la cola vacía. Encolar: se añade un elemento a la cola, con su correspondiente prioridad. Desencolar: se elimina el elemento frontal de la cola. Frente: se devuelve el elemento frontal de la cola.

Implementación en Maude Para la implementación de las colas de prioridad el elemento a insertar tiene que ser de un tipo que soporte un orden total y eso lo conseguimos creando una teoría, que será la siguiente: ***( Vamos a manejar explicitamente las prioridades dentro de la cola, por lo que precisamos que el tipo base proporcione operaciones para acceder a la prioridad, y para compararlas. Se asume que p1 > p2, donde p1 y p2 son prioridades, significa que p1 es preferente frente a p2, esto es, un elemento con prioridad p1 es más prioritario que otro con prioeidad p2. ) fth ELEMENTO-PRIORIDAD is protecting BOOL . sorts Elt Prioridad . *** operaciones op prioridad : Elt -> Prioridad . op _>_ : Prioridad Prioridad -> Bool. endfth

42

Una vez que tenemos la teoría procedemos a la implementación de la cola de prioridad: fmod COLA-PRIORIDAD {X :: ELEMENTO-PRIORIDAD} is sorts Cola PrioNV{X} ColaPrio{X} . subsort Cola PrioNV{X} < ColaPrio{X} . *** operaciones op crear : -> Cola PrioNV{X} . op encolar : X$Elt Cola Prio{X} -> Cola PrioNV{X} [ctor] . *** constructores op desencolar : Cola Prio{X} -> Cola {X} . *** selectores op frente : Cola PrioNV{X} -> X$Elt . *** variables var C : Cola PrioNV{X} . var E : X$Elt . *** ecuaciones eq desencolar(crear) = crear . eq desencolar(encolar(E,crear)) = crear . eq desencolar(encolar(E,C)) = if prioridad(E) > prioridad(frente(C)) then C else encolar(E,desencolar(C)) fi . eq frente(encolar(E,crear)) = E . eq frente(encolar(E,C)) = if prioridad(E) > prioridad(frente(C)) then E else frente(C) fi . endfm

Posible instanciación ***( Usamos pares de naturales, en la que el primer valor es un dato, y el segundo su prioridad. Suponemos que un valor natural más pequeño indica mayor prioridad. ) fmod PAR-NAT is protecting NAT . sort ParNat . op <_:_> : Nat Nat -> ParNat . op info : ParNat -> Nat . op clave : ParNat -> Nat . vars E C : Nat . vars P1 P2 : ParNat . eq info(< E : C >) = E . eq clave(< E : C >) = C . endfm

43

*** Realizamos la vista correspondiente view VParNat from ELEMENTO-PRIORIDAD to PAR-NAT is sort Elt to ParNat . sort Prioridad to Nat . op prioridad to clave . op _>_ to _<_ . endv *** Procedemos a la instanciación fmod COLA-PAR-NAT is protecting COLA-PRIORIDAD{VParNat} . endfm

Ejemplo Cola Prioridad en Maude COLA-MEDIEVAL es un ejemplo de colas de prioridad en la que los elementos de la cola son plebeyos y nobles, en la cual la prioridad la tienen los nobles. fth MEDIEVAL is sort Elt . op esNoble?: Elt --> Bool . endfth fmod COLA-MEDIEVAL {x::MEDIEVAL} is protecting NAT, BOOL . sort colaM{x} . subsort colaMNV{x} < colaM{x} . op crear: --> colaM{x} [ctor] . op insertar: x$Elt colaM{x} --> colaMNV{x} [ctor] . op op op op

extraer: colaM{x} --> colaM{x} . frente: colaMNV{x} --> x$Elt . NNobles: colaM{x} --> Nat . NPlebleyos: colaM{x} --> Nat .

var C: colaMNV{x} . var E: x$Elt . eq extraer(crear) = crear . eq extraer(insertar(E,crear)) = crear . eq extraer(insertar(E,C)) = if NOT(esNoble?(frente(c))) AND esNoble?(E) then c else insertar(E,extraer(c)) fi . eq frente(insertar(E,crear)) = E . eq frente(insertar(E,C)) = if (esNoble?(E)) AND (esNoble?(frente(C))) then E else frente(C) fi .

44

eq NNobles(crear) = 0 . eq NNobles(insertar(E,C)) = if esNobles?(E) then 1 + NNobles(C) else NNobles(C) fi . eq NPlebleyos(crear) = 0 . eq NPlebleyos(insertar(E,C)) = if NOT(esNobles?(E)) then 1 + NPlebeyos(C) else NPlebeyos(C) fi . endfm

Implementación en JAVA Partimos a partir de la implementación en JAVA utilizando clases. package colaPrioridadSimpleEnlazada; import colaException.*; public class ColaPrioridad implements colaPrioridadInterface.ColaPrioridad { class Celda { Object elemento; int prioridad; Celda sig; } private Celda cola; public ColaPrioridad() { cola = new Celda(); cola.sig = null; } public boolean vacia() { return (cola.sig==null); } public Object primero() throws ColaVaciaException { if (vacia()) throw new ColaVaciaException(); return cola.sig.elemento; } public int primero_prioridad() throws ColaVaciaException { if (vacia()) throw new ColaVaciaException(); return cola.sig.prioridad; } public int primero_prioridad() throws ColaVaciaException { if (vacia()) throw new ColaVaciaException(); return cola.sig.prioridad; } public void inserta(Object elemento, int prioridad) { Celda p,q; boolean encontrado = false; p = cola; while((p.sig!=null)&&(!encontrado)) { if (p.sig.prioridad<prioridad)

45

encontrado = true; else p = p.sig; } q = p.sig; p.sig = new Celda(); p = p.sig; p.elemento = elemento; p.prioridad = prioridad; p.sig = q; } public void suprime() throws ColaVaciaException { if (vacia()) throw new ColaVaciaException(); cola = cola.sig; } } // fin clase ColaPrioridad

Árbol (informática) En ciencias de la informática, un árbol es una estructura jerárquica de datos 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.

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. 46

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). ESTA ES UNA FORMA MAS FACIL DE COMPRENDER EL TEMA

A+B SUFIJO +AB PREFIJO AB+ POSFIJO El arbol normal (a+b) * c * A+b

c +

Ab I pre orden d entre orden r pos orden idr posfijo rid Prefijo ird sufijo

Tipos de árboles

Ejemplo de árbol (binario). 47

Árboles Binarios Árbol de búsqueda binario auto-balanceable o Árboles Rojo-Negro o Árboles AVL Árboles B o Árbol-B+ o Árbol-B* Árboles Multicamino

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. Encontrar la primer raiz.

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 binario En 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 mas de dos hijos (de ahi el nombre "binario"). Si algun hijo tiene como referencia a null, es decir que no almacena ningun 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.

48

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 reusamos 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.

Especificación en Maude Definiremos en Maude un módulo, para ver como se especifica un Árbol Binario con sus operaciones más básicas: fmod ÁRBOL-BINARIO{X::TRIV} is sorts ArbolBNV{X}ArbolB{X}. subsort ArbolBNV{X}
49

op crear:- rel="nofollow">ArbolB{X}[ctor]. op arbolBinario:X$EltArbolB{X}ArbolB{X}-> ***constructores ops hijoIzq hijoDer:ArbolBNV{X}->ArbolB{X} ***selectores op raiz:ArbolBNV{X}->X$Elt. ***variables var R:X$Elt. vars I D:ArbolB{X}. ***ecuaciones eq raiz(arbolBinario(R,I,D))=R. eq hijoIzq(arbolBinario(R,I,D))=I. eq hijoDer(arbolBinario(R,I,D))=D. endfm

Aquí definiremos un nuevo módulo para incorporar operaciones útiles y básicas en un Árbol Binario: fmod ÁRBOL-BIN-OPS-1{X::TRIV}is protecting ÁRBOL-BINARIO{X}. protecting NAT. ***selectores ops numElemsaltura:ArbolB{X}->Nat. op igualForma:ArbolB{X}ArbolB{X}->Bool[comm]. ***variables vars N M:Nat. vars R R2 R3:X$Elt. vars I I2 D D2:ArbolB{X}. var A:ArbolBNV{X}. ***ecuaciones eq numElems(crear)=0. eq numElems(arbolBinario(R,I,D))=1+numElems(I)+numElems(D). eq altura(crear)=0. eq altura(arbolBinario(R,I,D))=1+max(altura(I),altura(D)). eq igualForma(crear,crear)=true. eq igualForma(crear,A)=false. eq igualForma(arbolBinario(R,I,D),arbolBinario(R2,I2,D2))= igualForma(I,I2)andigualForma(D,D2). endfm

Y aquí encontramos operaciones más avanzadas para comprobar ciertos estados del Árbol Binario: fmod ÁRBOL-BIN-OPS-3{X::TRIV} is protecting ÁRBOL-BINARIO{X}. protecting ÁRBOL-BIN-OPS-1{X}.

50

protecting INT. ***selectores ops esLleno? esCompleto?:ArbolB{X}->Bool. ops esEquilibrado? esTotEqui?:ArbolB{X}->Bool. ***variables vars R:X$Elt. vars ID:ArbolB{X}. ***ecuaciones eq esLleno?(crear)=true. eq esLleno?(arbolBinario(R,I,D))=altura(I)==altura(D)and esLleno?(I) and esLleno?(D). eq esCompleto?(crear)=true. eq esCompleto?(arbolBinario(R,I,D))=(altura(I)==altura(D) and esLleno?(I) and esCompleto?(D)) or (altura(I)==(altura(D)+1) and esCompleto?(I) and esLleno?(D)). eq esEquilibrado?(crear)=true. eq esEquilibrado?(arbolBinario(R,I,D))=sd(altura(I),altura(D))<=1and esEquilibrado?(I) and esEquilibrado?(D) eq esTotEqui?(crear)=true. eq esTotEqui?(arbolBinario(R,I,D))=sd(numElems(I),numElems(D))<=1and esTotEqui?(I) and esTotEqui?(D). endfm

Especificación en Java Funciones básicas de un árbol binario numérico, aparte de los hijos vamos a poner un dato para tener la información de descendencia: public class ArbolBinarioNumerico { private private private private

ArbolBinarioNumerico hijoDerecho; ArbolBinarioNumerico hijoIzquierdo; ArbolBinarioNumerico padre; int dato;

public ArbolBinarioNumerico(int t){ hijoDerecho=null; hijoIzquierdo=null; padre=null; dato=t; } public ArbolBinarioNumerico getHijoDerecho() { return hijoDerecho; } public void setHijoDerecho(ArbolBinarioNumerico hijo) { if(!(esta(hijo.getDato()))){ this.hijoDerecho = hijo; hijoDerecho.setPadre(this); }

51

} public void setHijoDerecho(int dato) { ArbolBinarioNumerico aux=new ArbolBinarioNumerico(dato); if(!(esta(aux.getDato()))){ this.hijoDerecho = aux; hijoDerecho.setPadre(this); } } public ArbolBinarioNumerico getHijoIzquierdo() { return hijoIzquierdo; } public void setHijoIzquierdo(ArbolBinarioNumerico hijo) { if(!(esta(hijo.getDato()))){ this.hijoIzquierdo = hijo; hijoIzquierdo.setPadre(this); } } public void setHijoIzquierdo(int dato) { ArbolBinarioNumerico aux=new ArbolBinarioNumerico(dato); if(!(esta(aux.getDato()))){ this.hijoIzquierdo = aux; hijoIzquierdo.setPadre(this); } } public int getDato() { return dato; } public void setDato(int dat) { dato = dat; } public boolean esHoja(){ if ((hijoDerecho==null)&&(hijoIzquierdo==null)){ return true; }else {return false; } } public int padre(){ ArbolBinarioNumerico aux=null; if (super.getClass()==ArbolBinarioNumerico.class){ try { aux = (ArbolBinarioNumerico) super.clone(); } catch (CloneNotedException ex) { Logger.getLogger(ArbolBinarioNumerico.class.getName()).log(Level.SEVERE, null, ex); } return aux.getDato(); } return -1; } public int altura(){ int iz=0;

52

int de=0; if(esHoja()){ return 1; }else{ if (getHijoIzquierdo()!=null) iz=getHijoIzquierdo().altura(); if (getHijoDerecho()!=null) de=getHijoDerecho().altura(); if((iz>=de)&&(getHijoIzquierdo()!=null)){ return (1+getHijoIzquierdo().altura()); }else{ if((de>=iz)&&(getHijoDerecho()!=null)){ return (1+getHijoDerecho().altura()); }else{ return 0; } } } } public int cantNodos(){ int aux1=0,aux2=0; if (esHoja()){ return 1; }else{ if(getHijoIzquierdo()!=null) aux1=getHijoIzquierdo().cantNodos(); if(getHijoDerecho()!=null) aux2=getHijoDerecho().cantNodos(); return(1+aux1+aux2); } } public void dispose(){ getHijoDerecho().dispose(); getHijoIzquierdo().dispose(); dispose(); } public ArbolBinarioNumerico getPadre(){ return padre; } public void setPadre(ArbolBinarioNumerico p){ padre=p; } public int profundidad(){ if (getPadre()!=null){ return 1+getPadre().profundidad(); }else{ return 0; } } public int aridad(){ int iz=0; int de=0; if (!this.esHoja()) { if(this.getHijoIzquierdo()!=null){ iz=getHijoIzquierdo().aridad(); } //System.out.println(dato); if(this.getHijoDerecho()!=null){ de=this.getHijoDerecho().aridad();

53

} }else{ return 1; } return iz+de; } public void caminos(ListaInt aux){ if(esHoja()){ aux.insert(getDato()); System.out.println("Camino"); aux.imprimirLista(); aux.delete(getDato()); }else{ aux.insert(getDato()); if(getHijoIzquierdo()!=null){ getHijoIzquierdo().caminos(aux); } if(getHijoDerecho()!=null){ getHijoDerecho().caminos(aux); } aux.delete(getDato()); } } public boolean camListaIgual(ListaInt lista){ if((lista==null)||(lista.esVacia())){ return false; }else{ if(getDato()==lista.first()){ if (esHoja()){ if(lista.size()==1){ return true; }else{ return false; } }else{ lista.delete(lista.first()); if ((getHijoIzquierdo()!=null)&&(getHijoDerecho()!=null)){ return getHijoIzquierdo().camListaIgual(lista)||getHijoDerecho().camListaIgual(lista); }else{ if (getHijoIzquierdo()==null){ return getHijoDerecho().camListaIgual(lista); }else{ return getHijoIzquierdo().camListaIgual(lista); } } } }else{ return false; } }

} public boolean esta(int valor){ if(getDato()==valor){ return true; }else{ if(esHoja()){

54

return false; }else{ if((getHijoIzquierdo()!=null)&&(getHijoDerecho()!=null)){ return getHijoIzquierdo().esta(valor)||getHijoDerecho().esta(valor); }else{ if(getHijoIzquierdo()!=null){ return getHijoIzquierdo().esta(valor); }else{ return getHijoDerecho().esta(valor); } } } }

}

Implementación en C Un árbol binario puede declararse de varias maneras. Algunas de ellas son: Estructura con manejo de memoria dinámica: typedef struct tArbol { int clave; struct tArbol *hIzquierdo, *hDerecho; } tArbol;

Estructura con arreglo indexado: typedef struct tArbol { int clave; int hIzquierdo, hDerecho; }; 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

55

Especificación en Maude de los recorridos preorden, inorden, postorden Especificaremos antes en Maude las operaciones de recorrido en preorden, inorden y postorden: fmod ÁRBOL-BIN-REC-PROF{X::TRIV} is protecting ÁRBOL-BINARIO{X}. protecting LISTA-GENERICA{X}. protecting INT. ***selectores ops preOrden inOrden posOrden:ArbolB{X}->ListaGen{X}. ***variables var R:X$Elt. vars ID:ArbolB{X}. ***ecuaciones eq preOrden(crear)=crear. eq preOrden(arbolBinario(R,I,D))=cons(R,preOrden(I))::preOrden(D). eq inOrden(crear)=crear. eq inOrden(arbolBinario(R,I,D))=inOrden(I)::cons(R,inOrden(D)). eq posOrden(crear)=crear. eq posOrden(arbolBinario(R,I,D))=posOrden(I)::posOrden(D)::cons(R,crear). endfm

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. 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); preorden(a->hIzquierdo); preorden(a->hDerecho); } }

//Realiza una operación en nodo

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ía push(s,raíz); //insertamos el nodo raíz MIENTRAS (s <> NULL) HACER p = pop(s); //sacamos un elemento de la pila tratar(p); //realizamos operaciones sobre el nodo p

56

SI (I(p) <> NULL) ENTONCES push(s,D(p)); FIN-SI SI (D(p) <> NULL) ENTONCES push(s,I(p)); FIN-SI FIN-MIENTRAS

//preguntamos si p tiene árbol derecho //preguntamos si p tiene árbol izquierdo

En Java: public void preOrden(){ if (!esHoja()){ System.out.println(dato); if(getHijoIzquierdo()!=null){ getHijoIzquierdo().preOrden(); } if (getHijoDerecho()!=null){ getHijoDerecho().postOrden(); } }else{ System.out.println(dato); } }

Recorrido en postorden En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. 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); } }


En Java: public void postOrden(){ if(!esHoja()){ if (getHijoIzquierdo()!=null){ getHijoIzquierdo().postOrden(); } if (getHijoDerecho()!=null){ getHijoDerecho().postOrden(); } System.out.println(dato); }else{ System.out.println(dato); } }

57

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. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4 y 9. Pseudocódigo: funcion inorden(nodo) inicio si(existe(nodo)) inicio inorden(hijo_izquierdo(nodo)); tratar(nodo); inorden(hijo_derecho(nodo)); fin; fin;


Implementación en C: void inorden(tArbol *a) { if (a != NULL) { inorden(a->hIzquierdo); tratar(a); inorden(a->hDerecho); } }


En Java: public void inorden(){ if (!this.esHoja()) { if(this.getHijoIzquierdo()!=null){ this.getHijoIzquierdo().inorden(); } System.out.print(dato); if(this.getHijoDerecho()!=null){ this.getHijoDerecho().inorden(); } }else{ System.out.print(dato); } }

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.

58

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. Pseudocódigo: encolar(raiz); mientras(cola_no_vacia()) inicio nodo=desencolar(); visitar(nodo); encolar_nodos_hijos(nodo); fin;

//Saca un nodo de la cola //Realiza una operación en nodo //Mete en la cola los hijos del nodo actual

Implementación en C: void amplitud(tArbol *a) { tCola cola; tArbol *aux; if (a != NULL) { crearCola(cola); encolar(cola, a); while (!colavacia(cola)) { desencolar(cola, aux); visitar(aux); operación en nodo if (aux->hIzquierdo != NULL) encolar(cola, aux->hIzquierdo ); if (aux->hDerecho!= NULL) encolar(cola, aux->hDerecho); } } }

//Realiza una

Implementación en Java: public void amplitud(NodoArbol a) { Cola cola, colaAux; NodoArbol aux;

//SE RECIBE LA RAÍZ DEL ÁRBOL

if (a != null) { cola=new Cola(); colaAux=new Cola(); cola.push(a); NODO EN LA COLA while (cola.colavacia()!=1) { colaAux.push(aux=cola.pop()); ASIGNADO

//SI EL ÁRBOL CONTIENE NODOS...

//DEFINICIÓN DE 2 VARIABLES DE TIPO COLA //DEFINICIÓN AUX DE TIPO NODOARBOL

//SE INSTANCIA EL OBJETO COLA //SE INSTANCIA EL OBJETO COLAAUX //SE INSERTA EL NODOARBOL "A" (RAÍZ) COMO PRIMER //MIENTRAS HAYAN ELEMENTOS EN LA COLA... /*EL ELEMENTO EXTRAÍDO DE LA COLA PRINCIPAL ES A

AUXILIAR*/ if (aux.izq != null) {

AUX

Y

A

SU

VEZ

INSERTADO

EN

LA

COLA

//SI EL HIJO IZQUIERDO DEL NODO ACTUAL EXISTE

59

cola.push(aux.izq); LA COLA } if (aux.der!= null) { cola.push(aux.der); LA COLA } } colaAux.print(); } }

//SE INSERTA ESE HIJO COMO ELEMENTO SIGUIENTE EN //SI EL HIJO DERECHO DEL NODO ACTUAL EXISTE //SE INSERTA ESE HIJO COMO ELEMENTO SIGUIENTE EN

//POR ÚLTIMO SE IMPRIME LA COLA AUXILIAR

NOTA: Para hacer un recorrido en anchura, la idea es ir guardando en una cola los hijos del nodo que se están visitando y el siguiente a visitar es el próximo nodo de la cola.

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 arreglos, 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

60

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/siguiente 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))

61

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 Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.

Descripción Un árbol binario de búsqueda (ABB) es un árbol binario definido de la siguiente forma: Todo árbol vacío es un árbol binario de búsqueda. Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si: • En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario de búsqueda. • En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario de búsqueda.

Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores. Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación este definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos. La altura h en el peor de los casos siempre el mismo tamaño que el número de elementos disponibles. Y en el mejor de los casos viene dada por la expresión h = ceil(log2(c + 1)), donde ceil indica redondeo por exceso.

Ejemplo de Árbol Binario de Búsqueda

62

El interés de los árboles binarios de búsqueda radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente. Dependiendo de las necesidades del que trate con una estructura de este tipo se podrá permitir la igualdad estricta en alguno, en ninguno o en ambos de los subárboles que penden de la raíz. Permitir el uso de la igualdad provoca la aparición de valores dobles y hace la búsqueda más compleja. Un árbol binario de búsqueda no deja de ser un caso particular de árbol binario, así usando la siguiente especificación de árbol binario en maude: fmod ARBOL-BINARIO {X :: TRIV}is sorts ArbolBinNV{X} ArbolBin{X} . subsort ArbolBinNV{X} < ArbolBin{X} . *** generadores op crear : -> ArbolBin{X} [ctor] . op arbolBin : X$Elt ArbolBin{X} ArbolBin{X} -> ArbolBinNV{X} [ctor] . endfm

Podemos hacer la siguiente definicion para un árbol binario de búsqueda (también en maude): fmod ARBOL-BINARIO-BUSQUEDA {X :: ORDEN} is protecting ARBOL-BINARIO{VOrden}{X} . sorts ABB{X} ABBNV{X} . subsort ABBNV{X} < ABB{X} . subsort ABB{X} < ArbolBin{VOrden}{X} . subsort ABBNV{X} < ArbolBinNV{VOrden}{X} . *** generadores op crear : -> ArbolBin{X} [ctor] . op arbolBin : X$Elt ArbolBin{X} ArbolBin{X} -> ArbolBinNV{X} [ctor] . endfm

Con la siguiente teoría de orden: fth ORDEN is protecting BOOL . sort Elt . *** operaciones op _<_ : Elt Elt -> Bool . endfth

Para que un árbol binario pertenezca al tipo árbol binario de búsqueda debe cumplir la condición de ordenación siguiente que iría junto al módulo ARBOL-BINARIO-BUSQUEDA: var R : X$Elt . vars INV DNV : ABBNV{X} . vars I D : ABB{X} . mb crear : ABB{X} . mb arbolBin(R, crear, crear) : ABBNV{X} . cmb arbolBin(R, INV, crear) : ABBNV{X} if R > max(INV) . cmb arbolBin(R, crear, DNV) : ABBNV{X} if R < min(DNV) . cmb arbolBin(R, INV, DNV) : ABBNV{X} if (R > max(INV)) and (R < min(DNV)) . ops min max : ABBNV{X} -> X$Elt .

63

eq eq eq eq

min(arbolBin(R, min(arbolBin(R, max(arbolBin(R, max(arbolBin(R,

crear, D)) INV, D)) = I, crear)) I, DNV)) =

= R . min(INV) . = R . max(DNV) .

Operaciones Todas las operaciones realizadas sobre árboles binarios de búsqueda están basadas en la comparación de los elementos o clave de los mismos, por lo que es necesaria una subrutina, que puede estar predefinida en el lenguaje de programacion, que los compare y pueda establecer una relación de orden entre ellos, es decir, que dados dos elementos sea capaz de reconocer cual es mayor y cual menor. Se habla de clave de un elemento porque en la mayoría de los casos el contenido de los nodos será otro tipo de estructura y es necesario que la comparación se haga sobre algún campo al que se denomina clave.

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. El número de comparaciones que necesitaríamos para saber si un elemento se encuentra en un árbol binario de búsqueda estaría entre [log2(N+1)] y N, siendo N el numero de nodos. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) 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); }

64

} 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; }

Otro ejemplo en Python: def search_binary_tree(node, key): if node is None: return None # not found if key < node.key: return search_binary_tree(node.left, key) else if key > node.key: return search_binary_tree(node.right, key) else: return node.value

En Pascal: Function busqueda(T:ABR, y: integer):ABR begin if (T=nil) or (^T.raiz=y) then busqueda:=T; else if (^T.raiz
Una especificación en maude para la operación de búsqueda quedaría de la siguiente forma: op esta? : X$Elt ABB{X} -> Bool . var R R1 R2 : X$Elt . vars I D : ABB{X} . eq esta?(R, crear) = false . eq esta?(R1, arbolBin(R2, I, D)) = if R1 == R2 then true else if R1 < R2 then esta?(R1, I) else

65

esta?(R1, D) fi fi .

Inserción La inserción es similar a la búsqueda y se puede dar una solución tanto iterativa como recursiva. Si tenemos inicialmente como parámetro un árbol vacío se crea un nuevo nodo como único contenido el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que la raíz del árbol inicial con lo que se inserta en el subárbol izquierdo y si es mayor se inserta en el subárbol derecho. De esta forma las inserciones se hacen en las hojas.

Evolución de la inserción del elemento "5" en un ABB

Como en el caso de la búsqueda puede haber varias variantes a la hora de implementar la inserción en el TAD (Tipo Abstracto de Datos), y es la decisión a tomar cuando el elemento (o clave del elemento) a insertar ya se encuentra en el árbol, puede que éste sea modificado o que sea ignorada la inserción. Es obvio que esta operación modifica el ABB perdiendo la versión anterior del mismo. A continuación se muestran las dos versiones del algoritmo en pseudolenguaje, iterativo y recursivo, respectivamente. PROC InsertarABB(árbol:TABB; dato:TElemento) VARIABLES nuevonodo,pav,pret:TABB clavenueva:Tclave ele:TElemento INICIO nuevonodo <- NUEVO(TNodoABB) nuevonodo^.izq <- NULO nuevonodo^.der <- NULO nuevonodo^.elem <- dato SI ABBVacío (árbol) ENTONCES árbol <- nuevonodo ENOTROCASO clavenueva <- dato.clave

66

pav <- árbol // Puntero Avanzado pret <- NULO // Puntero Retrasado MIENTRAS (pav <- NULO) HACER pret <- pav ele = pav^.elem SI (clavenueva < ele.clave ) ENTONCES pav <- pav^.izq EN OTRO CASO pav <- pav^.dch FINSI FINMIENTRAS ele = pret^.elem SI (clavenueva < ele.clave ) ENTONCES pret^.izq <- nuevonodo EN OTRO CASO pret^.dch <- nuevonodo FINSI FINSI FIN PROC InsertarABB(árbol:TABB; dato:TElemento) VARIABLES ele:TElemento INICIO SI (ABBVacío(árbol)) ENTONCES árbol <- NUEVO(TNodoABB) árbol^.izq <- NULO árbol^.der <- NULO árbol^.elem <- dato EN OTRO CASO ele = InfoABB(árbol) SI (dato.clave < ele.clave) ENTONCES InsertarABB(árbol^.izq, dato) EN OTRO CASO InsertarABB(árbol^.dch, dato) FINSI FINSI FIN

Se ha podido apreciar la simplicidad que ofrece la versión recursiva, este algoritmo es la traducción en C. El árbol es pasado por referencia para que los nuevos enlaces a los subárboles mantengan la coherencia. void insertar(tArbol **a, int elem) { if (*a == NULL) { *a = (tArbol *) malloc(sizeof(tArbol)); (*a)->clave = elem; (*a)->hIzquierdo = NULL; (*a)->hDerecho = NULL; } else if ((*a)->clave < elem) insertar(&(*a)->hDerecho, elem); else if ((*a)->clave > elem) insertar(&(*a)->hIzquierdo, elem); }

67

Ejemplo en Python: def binary_tree_insert(node, key, value): if node is None: return TreeNode(None, key, value, None) if key == node.key: return TreeNode(node.left, key, value, node.right) if key < node.key: return TreeNode(binary_tree_insert(node.left, key, node.value, node.right) else: return TreeNode(node.left, node.key, binary_tree_insert(node.right, key, value))

value),

node.key, node.value,

Otro ejemplo en Pascal: Procedure Insercion(var T:ABR, y:integer) var ultimo:ABR; actual:ABR; nuevo:ABR; begin ultimo:=nil; actual:=T; while (actual<>nil) do begin ultimo:=actual; if (âctual.raiz
Véase también un ejemplo de algoritmo recursivo de inserción en un ABB en el lenguaje de programación Maude: op insertar : X$Elt ABB{X} -> ABBNV{X} . var R R1 R2 : X$Elt . vars I D : ABB{X} . eq insertar(R, crear) = arbolBin(R, crear, crear) . eq insertar(R1, arbolBin(R2, I, D)) = if R1 < R2 then arbolBin(R2, insertar(R1, I), D) else arbolBin(R2, I, insertar(R1, D)) fi .

68

La operación de inserción requiere, en el peor de los casos, un tiempo proporcional a la altura del árbol.

Borrado La operación de borrado no es tan sencilla como las de búsqueda e inserción. Existen varios casos a tener en consideración: Borrar un nodo sin hijos ó nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.

Nodo a eliminar 74 Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.

Nodo a eliminar 70 Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos:

Nodo a eliminar 59

El siguiente algoritmo en C realiza el borrado en un ABB. El procedimiento reemplazar busca la mayor clave del subárbol izquierdo y la asigna al nodo a eliminar. void borrar(tArbol **a, int elem)

69

{ void reemplazar(tArbol **a, tArbol **aux); tArbol *aux; if (*a == NULL) return; if ((*a)->clave < elem) borrar(&(*a)->hDerecho, elem); else if ((*a)->clave > elem) borrar(&(*a)->hIzquierdo, elem); else if ((*a)->clave == elem) { aux = *a; if ((*a)->hIzquierdo == NULL) *a = (*a)->hDerecho; else if ((*a)->hDerecho == NULL) *a = (*a)->hIzquierdo; else reemplazar(&(*a)->hIzquierdo, &aux); free(aux); } } void reemplazar(tArbol **a, tArbol **aux) { if ((*a)->hDerecho == NULL) { (*aux)->clave = (*a)->clave; *aux = *a; *a = (*a)->hIzquierdo; } else reemplazar(&(*a)->hDerecho, aux); }

Otro ejemplo en Pascal. Procedure Borrar(var T:ABR, x:ABR) var aBorrar:ABR; anterior:ABR; actual:ABR; hijo:ABR; begin if (^x.izq=nil) or (^x.dch=nil) then aBorrar:=x; else aBorrar:=sucesor(T,x); actual:=T; anterior:=nil; while (actual<>aBorrar) do begin anterior:=actual; if (âctual.raiz<âBorrar.raiz) then

70

actual:=âctual.dch; else actual:=âctual.izq; end; if (âctual.izq=nil) then hijo:=âctual.dch; else hijo:=âctual.izq; if (anterior=nil) then T:=hijo; else if (ânterior.raiz<âctual.raiz) then ânterior.dch:=hijo; else ânterior.izq:=hijo; if (aBorrar<>x) then ^x.raiz:=âBorrar.raiz; free(aBorrar); end;

Véase también un ejemplo de algoritmo recursivo de borrado en un ABB en el lenguaje de programación Maude, considerando los generadores crear y arbolBin. Esta especificación hace uso de la componente clave a partir de la cual se ordena el árbol. op eliminar : X$Elt ABB{X} -> ABB{X} . varS R M : X$Elt . vars I D : ABB{X} . vars INV DNV : ABBNV{X} . ops max min : ArbolBin{X} -> X$Elt . eq min(arbolBin(R, crear, D)) = R . eq max(arbolBin(R, I, crear)) = R . eq min(arbolBin(R, INV, D)) = min(INV) . eq max(arbolBin(R, I, DNV )) = max(DNV) . eq eliminar(M, crear) = crear . ceq eliminar(M, arbolBin(R, crear, D)) = D if M == clave(R) . ceq eliminar(M, arbolBin(R, I, crear)) = I if M == clave(R) . ceq eliminar(M, arbolBin(R, INV, DNV)) = arbolBin(max(INV), eliminar(clave(max(INV)), INV), DNV) if M == clave(R) . ceq eliminar(M, arbolBin(R, I, D)) = arbolBin(R, eliminar(M, I), D) if M < clave(R) . ceq eliminar(M, arbolBin(R, I, D)) = arbolBin(R, I, eliminar(M, D)) if clave(R) < M .

Otras Operaciones Otra opereción sería por ejemplo comprobar que un árbol binario es un árbol binario de búsqueda. Su implementación en maude es la siguiente: op esABB? : ABB{X} -> Bool . var R : X$Elt . vars I D : ABB{X} . eq esABB?(crear) = true . eq esABB?(arbolbBin(R, I, D)) = (Max(I) < R) and (Min(D) > R) and (esABB?(I)) and (esABB?(D)) .

71

Recorridos Se puede hacer un recorrido de un árbol en profundidad o en anchura. Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno de los hijos. El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inorden, preorden y postorden. Una propiedad de los ABB es que al hacer un recorrido en profundidad inorden obtenemos los elementos ordenados de forma ascendente.

Ejemplo árbol binario de búsqueda

Resultado de hacer el recorrido en: Inorden = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72]. Preorden = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72]. Postorden =[6, 13, 14, 9, 17, 26, 72, 64, 20, 15].

Tipos de árboles binarios de búsqueda Hay varios tipos de árboles binarios de búsqueda. Los árboles AVL, árbol rojo-negro, son árboles autobalanceables. Los árboles biselados son árboles también autobalanceables con la propiedad de que los elementos accedidos recientemente se accederán más rápido en posteriores s. En el montículo como en todos los árboles binarios de búsqueda cada nodo padre tiene un valor mayor q sus hijos y además es completo, esto es cuando todos los niveles están llenos con excepción del último que puede no estarlo. Hay muchos tipos de árboles binarios de búsqueda. Los árboles AVL y los árboles rojo y negro son ambos formas de árboles binarios de búsqueda autobalanceables. Un árbol biselado es un árbol binario de búsqueda que automáticamente mueve los elementos a los que se accede frecuentemente cerca de la raíz. En los monticulos, cada nodo también mantiene una prioridad y un nodo padre tiene mayor prioridad que su hijo. Otras dos maneras de configurar un árbol binario de búsqueda podría ser como un árbol completo o degenerado. Un árbol completo es un árbol con "n" niveles, donde cada nivel d <= n-1; el número de nodos existentes en el nivel "d" es igual que 2d. Esto significa que todos los posibles nodos existen en esos niveles, no hay ningún hueco. Un requirimiento adicional para un árbol binario completo es que para el 72

nivel "n", los nodos deben estar ocupados de izquierda a derecha, no pudiendo haber un hueco a la izquierda de un nodo ocupado. Un árbol degenerativo es un árbol que, para cada nodo padre, sólo hay asociado un nodo hijo. Por lo que se comporta como una lista enlazada.

Comparación de rendimiento D. A. Heger (2004) realiza una comparación entre los diferentes tipos de árboles binarios de búsqueda para encontrar que tipo nos daría el mejor rendimiento para cada caso. Los montículos se encuentran como el tipo de árbol binario de búsqueda que mejor resultado promedio da, mientras que los árboles rojo y negro los que menor rendimiento medio nos aporta.

Buscando el Árbol binario de búsqueda óptimo Si nosotros no tenemos en mente planificar un árbol binario de busqueda, y sabemos exactamente como de frecuente serán visitados cada elemento podemos construir un árbol binario de búsqueda óptimo con lo que conseguiremos que la media de gasto generado a la hora de buscar un elemento sea minimizado. Asumiendo que conocemos los elementos y en qué nivel está cada uno, también conocemos la proporción de futuras búsquedas que se harán para encontrar dicho elemento. Si es así, podemos usar una solución basada en la programación dinámica. En cambio, a veces sólo tenemos la estimación de los costes de búsqueda, como pasa con los sitemas que nos muestra el tiempo que ha necesitado para realizar una búsqueda. Un ejemplo, si tenemos un ABB de palabras usado en un corrector ortográfico, deberíamos balancear el árbol basado en la frecuencia que tiene una palabra en el Corpus lingüístico, desplazando palabras como "de" cerca de la raíz y palabras como "vesánico" cerca de las hojas. Un árbol como tal podría ser comparado con los árboles Huffman que tratan de encontrar elementos que son accedidos frecuentemente cerca de la raiz para producir una densa información; de todas maneras, los árboles Huffman sólo puede guardar elementos que contienen datos en las hojas y estos elementos no necesitan ser ordenados. En cambio, si no sabemos la secuencia en la que los elementos del árbol van a ser accedidos, podemos usar árboles biselados que son tan buenos como cualquier árbol de búsqueda que podemos construir para cualquier secuencia en particular de operaciones de búsqueda. Árboles alfabéticos son árboles Huffman con una restricción de orden adicional, o lo que es lo mismo, árboles de búsqueda con modificación tal que todos los elementos son almacenados en las hojas.

Á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 73

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 rojo-negro Un á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.

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 y 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) 74

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 y 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. 2. 3. 4. 5.

Todo nodo es o bien rojo o bien negro. La raíz es negra. Todas las hojas son negras (las hojas son los hijos nulos). Los hijos de todo nodo rojo son negros (también llamada "Propiedad del rojo"). 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 rojonegro 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 75

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 y negro en este paradigma, pero cambian algunas de las propiedades y se complican los algoritmos. Por esta razón, este artículo utiliza ―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 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 y 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 rojonegro requiere un espacio O(log n) para cada inserción o borrado, además del tiempo. Los árboles rojo y negro son isométricos a los árboles 2-3-4. En otras palabras, para cada árbol 23-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 rojonegro. Esto los hace ser una herramienta útil para la comprensión del funcionamiento de los árboles rojonegro 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.

76

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.

void rotar_izda(struct node *p) { struct node *aux; aux = p; p = p->dcho; aux-> dcho = p->izdo; p->izdo = aux; }

77

void rotar_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; }

78

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. 79

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; else return 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í: void insercion_caso1(struct node *n) { if (n->padre == NULL) n->color = NEGRO; else insercion_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. */ else insercion_caso3(n); }

80

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: void insercion_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.

81

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: void insercion_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: void insercion_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)) {

82

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 *

83

hermano(struct node *n) { if (n == n->padre->izdo) return n->padre->dcho; else return 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). void elimina_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; else eliminar_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: 84

void eliminar_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: void eliminar_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); }

85

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: void eliminar_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); } else eliminar_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: void eliminar_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; } else eliminar_caso5(n); }

86

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: void eliminar_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 87

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 más. 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: void eliminar_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: 88

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 rojonegro), 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).

Referencias Hernández, Zenón; Rodríguez, J.Carlos; González, J.Daniel; Díaz, Margarita; Pérez, José; Rodríguez, Gustavo. (2005). Fundamentos de Estructuras de Datos. Soluciones en Ada, Java y C++.. Madrid: Thomson Editores Spain. 84-9732-358-0. Mathworld: Red-Black Tree. San Diego State University: CS 660: Red-Black tree notes, by Roger Whitney. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 . Chapter 13: Red-Black Trees, pp.273–301. Pfaff, Ben (June de 2004). «Performance Analysis of BSTs in System Software» (PDF). Stanford_university.. Okasaki, Chris. «Red-Black Trees in a Functional Setting» (PS).. 89

Árbol AVL Árbol AVL es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.

Descripción

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

Un ejemplo de árbol binario equilibrado (sí es AVL)

El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Adelson-Velskii y Landis. 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. 90

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 Arboles balanceados o equilibrados: · Un árbol binario de búsqueda es k-equilibrado si cada nodo lo es. · Un nodo es k-equilibrado si las alturas de sus subárboles izquierdo y derecho difieren en no más de k. Arboles AVL (Adel‘son, Vel‘skii, Landis) · Un árbol binario de búsqueda 1-equilibrado se llama árbol AVL. Cabe destacar que un árbol AVL no es un Tipo de dato abstracto (TDA) sino una estructura de datos.

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". Todo tipo de operaciones del árbol es una sinergidad de la solumniscensia del pivote.

91

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.

92

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.

93

ROTACIÓN DOBLE A LA IZQUIERDA.

94

Inserción [editar] 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

95

96

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

97

arbolBin(R2, I, D) elseif (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. 98

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) then if esVacio(I) then D elseif esVacio(D) then

99

I else if (altura(I) - altura(eliminar(min(D),D)) < 2) then arbolBin(min(D), I, eliminar(min(D), D)) ***tenemos que reequilibrar elseif (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 Las búsquedas se realizan de la misma manera que en los ABB, pero al estar el árbol equilibrado la complejidad de la búsqueda nunca excederá de O (log n). En un AVL se consigue que las búsquedas sean siempre de complejidad logarítmica, oscilando entre log N en el mejor caso y 1,44 log N en el peor caso.

Árbol biselado Un Árbol biselado o Árbol Splay es un Árbol binario de búsqueda auto-balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en s posteriores. Realiza operaciones básicas como pueden ser la inserción, la búsqueda y el borrado en un tiempo del orden de O(log n). Para muchas secuencias no uniformes de operaciones, el árbol biselado se comporta mejor que otros árboles de búsqueda, incluso cuando el patrón específico de la secuencia es desconocido. Esta estructura de datos fue inventada por Robert Tarjan y Daniel Sleator. Todas las operaciones normales de un árbol binario de búsqueda son combinadas con una operación básica, llamada biselación. Esta operación consiste en reorganizar el árbol para un cierto elemento, colocando éste en la raíz. Una manera de hacerlo es realizando primero una búsqueda binaria en el árbol para encontrar el elemento en cuestión y, a continuación, usar rotaciones de árboles de una manera específica para traer el elemento a la cima. Alternativamente, un algoritmo "de arriba a abajo" puede combinar la búsqueda y la reorganización del árbol en una sola fase.

Ventajas e inconvenientes El buen rendimiento de un árbol biselado depende del hecho de que es auto-balanceado, y además se optimiza automáticamente. Los nodos accedidos con más frecuencia se moverán cerca de la raíz donde podrán ser accedidos más rápidamente. Esto es una ventaja para casi todas las aplicaciones, y es particularmente útil para implementar cachés y algoritmos de recolección de basura; sin embargo, es importante apuntar que para un uniforme, el rendimiento de un árbol biselado será considerablemente peor que un árbol de búsqueda binaria balanceado simple. Los árboles biselados también tienen la ventaja de ser consideradamente más simples de implementar que otros árboles binarios de búsqueda auto-balanceados, como pueden ser los árboles RojoNegro o los árboles AVL, mientras que su rendimiento en el caso promedio es igual de eficiente. Además, los árboles biselados no necesitan almacenar ninguna otra información adicional a parte de los propios datos, minimizando de este modo los requerimientos de memoria. Sin embargo, estas estructuras de datos adicionales proporcionan garantías para el peor caso, y pueden ser más eficientes en la práctica para el uniforme. 100

Uno de los peores casos para el algoritmo básico del árbol biselado es el secuencial a todos los elementos del árbol de forma ordenada. Esto deja el árbol completamente des balanceado (son necesarios n s, cada uno de los cuales del orden de O(log n) operaciones). Volviendo a acceder al primer elemento se dispara una operación que toma del orden de O(n) operaciones para volver a balancear el árbol antes de devolver este primer elemento. Esto es un retraso significativo para esa operación final, aunque el rendimiento se amortiza si tenemos en cuenta la secuencia completa, que es del orden de O(log n). Sin embargo, investigaciones recientes muestran que si aleatoriamente volvemos a balancear el árbol podemos evitar este efecto de desbalance y dar un rendimiento similar a otros algoritmos de autobalanceo. Al contrario que otros tipos de árboles auto balanceados, los árboles biselados trabajan bien con nodos que contienen claves idénticas. Incluso con claves idénticas, el rendimiento permanece amortizado del orden de O(log n). Todas las operaciones del árbol preservan el orden de los nodos idénticos dentro del árbol, lo cual es una propiedad similar a la estabilidad de los algoritmos de ordenación. Un operación de búsqueda cuidadosamente diseñada puede devolver el nodo más a la izquierda o más a la derecha de una clave dada.

Operaciones Búsqueda La búsqueda de un valor de clave en un árbol biselado tiene la característica particular de que modifica la estructura del árbol. El descenso se efectúa de la misma manera que un árbol binario de búsqueda, pero si se encuentra un nodo cuyo valor de clave coincide con el buscado, se realiza una biselación de ese nodo. Si no se encuentra, el nodo biselado será aquel que visitamos por último antes de descartar la búsqueda. Así, la raíz contendrá un sucesor o predecesor del nodo buscado.

Inserción Es igual que en el árbol binario de búsqueda con la salvedad de que se realiza una biselación sobre el nodo insertado. Además, si el valor de clave a insertar ya existe en el árbol, se bisela el nodo que lo contiene.

Extracción Esta operación requiere dos biselaciones. Primero se busca el nodo que contiene el valor de clave que se debe extraer. Si no se encuentra, el árbol es biselado en el último nodo examinado y no se realiza ninguna acción adicional. Si se encuentra, el nodo se bisela y se elimina. Con esto el árbol se queda separado en dos mitades, por lo que hay que seleccionar un nodo que haga las veces de raíz. Al ser un árbol binario de búsqueda y estar todos los valores de clave ordenados, podemos elegir como raíz el mayor valor del subárbol izquierdo o el menor valor de clave del derecho.

Operación de Biselación Esta operación traslada un nodo x, que es el nodo al que se accede, a la raíz . Para realizar esta operación debemos rotar el árbol de forma que en cada rotación el nodo x está más cerca de la raíz. Cada biselación realizada sobre el nodo de interés mantiene el árbol parcialmente equilibrado y además los 101

nodos recientemente accedidos se encuentran en las inmediaciones de la raíz. De esta forma amortizamos el tiempo empleado para realizar la biselación. Podríamos distinguir 3 casos generales: Caso 1: x es hijo izquierdo o derecho de la raíz, p. Caso 2: x es hijo izquierdo de p y este a su vez hijo izquierdo de q o bien ambos son hijos derechos. Caso 3: x es hijo izquierdo de p y este a su vez hijo derecho de q o viceversa. CASO 1:

Si x es hijo izquierdo de p entonces realizaremos una rotación simple derecha. En caso de que x sea el derecho la rotación que deberemos realizar es simple izquierda.

CASO 2:

Si x es hijo y nieto izquierdo de p y q, respectivamente. Entonces debemos realizar rotación doble a la derecha, en caso de que x sea hijo y nieto derecho de p y q la rotación será doble izquierda.

102

CASO 3:

En caso de que x sea hijo izquierdo de p y nieto derecho de q realizaremos una rotación simple derecha en el borde entre x y p y otra simple izquierda entre x y q. En caso contrario, x sea hijo derecho y nieto izquierdo de q, la rotaciones simples será izquierda y después derecha.

103

Teoremas de rendimiento Hay muchos teoremas y conjeturas con respecto al peor caso en tiempo de ejecución para realizar una secuencia S de m s en un árbol biselado con n elementos.

Teorema del balance El coste de realizar la secuencia de s S es del orden de O(m(logn + 1) + nlogn). En otras palabras, los árboles biselados se comportan tan bien como los árboles de búsqueda binaria con balanceo estático en secuencias de al menos n s.

Teorema de optimalidad estática Sea qi el número de veces que se accede al elemento i en S. El coste de realizar la secuencia de s S es del orden de . En otras palabras, los árboles biselados se comportan tan bien como los árboles binarios de búsqueda estáticos óptimos en las secuencias de al menos n s.

Teorema "Static Finger" Sea ij el elemento visitado en el j-ésimo de S, y sea f un elemento fijo ("finger"). El coste de

realizar la secuencia de s S es del orden de

104

Teorema "Working Set" Sea t(j) el numero de elementos distintos accedidos desde la última vez que se accedió a j antes del instante i. El coste de realizar la secuencia de s S es del orden de

.

Teorema "Dynamic Finger" El

coste

de

realizar

la

secuencia

de

s

S

es

del

orden

de

.

Teorema "Scanning" También conocido como Teorema de Secuencial. El a los n elementos de un árbol biselado en orden simétrico es de orden exácto Θ(n), independientemente de la estructura inicial del árbol. El límite superior más ajustado demostrado hasta ahora es 4,5n

Conjetura de optimalidad dinámica Además del las garantías probadas del rendimiento de los árboles biselados, en el documento original de Sleator y Tarjan hay una conjetura no probada de gran interés. Esta conjetura se conoce como la conjetura de optimalidad dinámica, y básicamente sostiene que los árboles biselados se comportan tan bien como cualquier otro algoritmo de búsqueda en árboles binarios hasta un factor constante. Conjetura de optimalidad dinámica: Sea A cualquier algoritmo de búsqueda binaria en árboles que accede a un elemento x atravesando el camino desde la raíz hasta x, a un coste de d(x) + 1, y que entre los s puede hacer cualquier rotación en el árbol a un coste de 1 por rotación. Sea A(S) el coste para que A realice la secuencia S de s. Entonces el coste de realizar los mismos s para un árbol biselado es del orden O(n + A (S)).

Existen varios corolarios de la conjetura de optimalidad dinámica que permanecen sin probar: Conjetura Transversal: Sean T1 y T2 dos árboles biselados que contienen los mismos elementos. Sea S la secuencia obtenida tras visitar los elementos de T2 en preorden. El coste total para realizar la secuencia S de s en T1 es del orden de O(n). Conjetura Deque: Sea S una secuencia de m operaciones de cola doblemente terminada (push, pop, inject, eject). Entonces el coste para la realización de esta secuencia de operaciones S en un árbol biselado es del orden de O(m + n). Conjetura Split: Sea S cualquier permutación de los elementos del árbol biselado. Entonces el coste de la eliminación de los elementos en el orden S es del orden de O(n).

105

Código de ejemplo /* * SplayTreeApplet: * * The applet demonstrates the Splay Tree. It takes textual commands in a TextArea * and when the clicks on the Execute button, it processes the commands, updating * the display as it goes. * * @author Hyung-Joon Kim. CSE373, University of Washington. * * Copyrights Note: * This applet is extended from FullHuffmanApplet created by Prof. Steve Tanimoto, * Department of Computer Science and Engineering, University of Washington. * The setup of applet s and the tree display methods are apprecicatively reused. * */ import import import import

javax.swing.*; java.awt.*; java.awt.event.*; java.util.*;

public class SplayTreeApplet extends JApplet implements ActionListener, Runnable { Scrolled vis; //Donde se pinta el árbol MyScrollPane msp; Button executeButton; Button historyButton; TextArea InputText; TextArea history; JFrame historyFrame; JTextField statusLine; // La Estructura de datos (árboles biselados) de la clase SplayTree. SplayTree theSplayTree; Font headingFont, treeFont; int topMargin = 40; // Space above top of the tree. int leftMargin = 20; // x value for left side of array. int rightMargin = leftMargin; int yTreeTops = topMargin + 10; // y coord of top of trees. int bottomMargin = 10; // Minimum space betw. bot. of vis and bot. of lowest cell. int leftOffset = 5; // space between left side of cell and contents string. int delay = 1500; // default is to wait 1500 ms between updates. Thread displayThread = null; // For SplayTree display: int nodeHeight = 25; // Para dibujar los nodos int nodeWidth = 25; // How wide to plot pink rectangles int nodeVGap = 10; // vertical space between successive nodes int nodeHGap = 10; // horizontal space between successive nodes

106

int nodeHorizSpacing = nodeWidth + nodeHGap; int nodeVertSpacing = nodeHeight + nodeVGap; int interTreeGap = 15; // horizontal space between trees. int ycentering = 3; Color treeColor = new Color(255,255,215); static int m; // variable used when computing columns for tree layouts. public void init() { setSize(700,500); // default size of applet. vis = new Scrolled(); vis.setPreferredSize(new Dimension(400,400)); msp = new MyScrollPane(vis); msp.setPreferredSize(new Dimension(400,200)); Container c = getContentPane(); c.setLayout(new BorderLayout()); c.add(msp, BorderLayout.CENTER); J buttons = new J(); buttons.setLayout(new FlowLayout()); J controls = new J(); controls.setLayout(new BorderLayout()); executeButton = new Button("Execute"); executeButton.addActionListener(this); buttons.add(executeButton); historyButton = new Button("History"); historyButton.addActionListener(this); buttons.add(historyButton); InputText = new TextArea("\n"); statusLine = new JTextField(); statusLine.setBackground(Color.lightGray); controls.add(buttons, BorderLayout.WEST); controls.add(InputText, BorderLayout.CENTER); controls.add(statusLine, BorderLayout.SOUTH); controls.setPreferredSize(new Dimension(400,100)); c.add(controls, BorderLayout.SOUTH); c.validate(); theSplayTree = new SplayTree(); // Se crea una instancia de SplayTree headingFont = new Font("Helvetica", Font.PLAIN, 20); treeFont = new Font("Arial", Font.BOLD, 13); history = new TextArea("SplayTreeApplet history:\n", 20, 40); } class Scrolled extends J { public void paintComponent(Graphics g) { super.paintComponent(g); paintTrees(g); } } class MyScrollPane extends JScrollPane { MyScrollPane(J p) { super(p, JScrollPane.VERTICAL_SCROLLBAR_ALWAYS, JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS); }

107

} public void actionPerformed(ActionEvent e) { if (e.getActionCommand().equals("Execute")) { displayThread = new Thread(this); displayThread.start(); return; } if (e.getActionCommand().equals("History")) { if (historyFrame == null) { historyFrame = new JFrame("History of the SplayTreeApplet"); history.setFont(new Font("Courier", Font.PLAIN, 12)); historyFrame.getContentPane().add(history); historyFrame.setSize(new Dimension(500,500)); } historyFrame.show(); } } // The following is executed by a separate thread for the display. public void run() { String commands = InputText.getText(); String line = ""; StringTokenizer lines; for (lines = new StringTokenizer(commands, "\n\r\f"); lines.hasMoreTokens();) { line = lines.nextToken(); process(line, lines); } InputText.setText(""); // Erase all the processed input. } // Helper function called by the run method above: void process(String command, StringTokenizer lines) { String arg1 = ""; String arg2 = ""; StringTokenizer st = new StringTokenizer(command); if (! st.hasMoreTokens()) { return; } String firstToken = st.nextToken(); if (firstToken.startsWith(";")) { return; } history.appendText(command + "\n"); statusLine.setText(command); if (firstToken.equals("RESET")) { theSplayTree = new SplayTree(); updateDisplay(); return; } if (firstToken.equals("DELAY")) { if (st.hasMoreTokens()) { arg1 = st.nextToken(); try { delay =(new Integer(arg1)).intValue(); } catch(NumberFormatException e) { delay = 0; } statusLine.setText("delay = " + delay); } history.appendText("; delay is now " + delay + "\n");

108

return; } if (firstToken.equals("INSERT")) { arg1 = "UNDEFINED ELEMENT"; if (st.hasMoreTokens()) { arg1 = st.nextToken(); } int data = (new Integer(arg1)).intValue(); if (data < 1 || data > 99) { String msg = "Input NOT valid. Should be between 1-99 integer number."; report(msg); return; } theSplayTree.insert(data); // insert an element checkScrolledSize(); updateDisplay(); if (theSplayTree.statMode) { OldFamilySplayTree fam = theSplayTree.getRoot().oldFam; if (fam != null) { double currentDepth = fam.getFamilyDepth() / (double)fam.numFam; String msg2 = "Current(improved) average depth of old family: " + currentDepth; report(msg2); } } theSplayTree.getRoot().oldFam = null; // reset the old family of the root return; } if (firstToken.equals("FIND")) { arg1 = "UNDEFINED ELEMENT"; if (st.hasMoreTokens()) { arg1 = st.nextToken(); } int data = (new Integer(arg1)).intValue(); String msg = ""; // Check if data is already in the SplayTree and display the result. SplayTree node = theSplayTree.find(data); if ( node == null) { msg = "NOT FOUND: " + data + " is NOT in the Splay Tree"; } else { msg = "FOUND: " + node.element + " is in the Splay Tree."; } report(msg); checkScrolledSize(); updateDisplay(); if (theSplayTree.statMode) { OldFamilySplayTree theSplayTree.getRoot().oldFam; if (fam != null) { double currentDepth (double)fam.numFam;

fam =

fam.getFamilyDepth()

= /

109

String msg2 = "Current(improved) average depth of old family: " + currentDepth; report(msg2); } } theSplayTree.getRoot().oldFam = null; // reset the old family of the root return; } if (firstToken.equals("DELETE")) { arg1 = "UNDEFINED ELEMENT"; if (st.hasMoreTokens()) { arg1 = st.nextToken(); } int data = (new Integer(arg1)).intValue(); theSplayTree.delete(data); // delete an element checkScrolledSize(); updateDisplay(); if (theSplayTree.statMode) { OldFamilySplayTree fam = theSplayTree.getRoot().oldFam; if (fam != null) { double currentDepth = fam.getFamilyDepth() / (double)fam.numFam; String msg2 = "Current(improved) average depth of old family: " + currentDepth; report(msg2); } } theSplayTree.getRoot().oldFam = null; // reset the old family of the root return; } if (firstToken.equals("FIND-MIN")) { SplayTree node = theSplayTree.findMin(theSplayTree.getRoot()); theSplayTree.splay(node); // after find min, splay at the node checkScrolledSize(); updateDisplay(); if (theSplayTree.statMode) { OldFamilySplayTree fam = theSplayTree.getRoot().oldFam; if (fam != null) { double currentDepth = fam.getFamilyDepth() / (double)fam.numFam; String msg2 = "Current(improved) average depth of old family: " + currentDepth; report(msg2); } } theSplayTree.getRoot().oldFam = null; // reset the old family of the root return; } if (firstToken.equals("FIND-MAX")) { SplayTree node = theSplayTree.findMax(theSplayTree.getRoot()); theSplayTree.splay(node); // after find max, splay at the node

110

checkScrolledSize(); updateDisplay(); if (theSplayTree.statMode) { OldFamilySplayTree fam = theSplayTree.getRoot().oldFam; if (fam != null) { double currentDepth = fam.getFamilyDepth() / (double)fam.numFam; String msg2 = "Current(improved) average depth of old family: " + currentDepth; report(msg2); } } theSplayTree.getRoot().oldFam = null; // reset the old family of the root return; } if (firstToken.equals("STAT-MODE")) { if(delay < 2000) { delay = 2000; } theSplayTree.statMode = true; updateDisplay(); return; } history.appendText("[Unknown Splay Tree command]\n"); statusLine.setText("Unknown Spaly Tree command: " + command); } // Here is a "middleman" method that updates the display waiting with // the current time delay after each repaint request. void updateDisplay() { vis.repaint(); if (delay > 0) { try { Thread.sleep(delay); } catch(InterruptedException e) {} } } int getInt(String s) { int n = 1; try { Integer I = new Integer(s); n = I.intValue(); } catch(Exception e) { n = 1; } return n; }

/* The following computes the height of the display area needed by the current * heap, and if it won't fit in the scrolled , it enlarges the scrolled . */ void checkScrolledSize() { // Compute width needed for trees: int treesWidthNeeded = leftMargin + rightMargin;

111

int treesHeightNeeded = 0; Dimension d = vis.getPreferredSize(); int currentHeight = (int) d.getHeight(); int currentWidth = (int) d.getWidth(); treesWidthNeeded += theSplayTree.getRoot().getDisplayWidth(); treesHeightNeeded += Math.max(treesHeightNeeded, theSplayTree.getDisplayHeight() + 2*topMargin); // Enlarge scrolled if necessary: int widthNeeded = treesWidthNeeded; int heightNeeded = treesHeightNeeded; if ((heightNeeded > currentHeight) || (widthNeeded > currentWidth)) { vis.setPreferredSize(new Dimension( Math.max(currentWidth,widthNeeded), Math.max(currentHeight,heightNeeded))); vis.revalidate(); // Adjust the vertical scroll bar. } }

/** * Splay Tree Class: * * This inner class is a data structure to be demostrated. Integer numbers are assigned * to the data field of Splay Tree, and each node of Splay Tree has left child, right child, * and parent. When a data is accessed by any operations such as FIND, INSERT, etc, Splay Tree * performs a sequence of self-reconstructing processes, so called 'splay', in order to bring * the most-recently-accessed node to the root of the tree. As a result, the nodes near the most* recently-accessed node become available for a fast accesss in futre. * * @author Hyung-Joon Kim, CSE373, University of Washington. * */ public class SplayTree { // data for Splay trees : SplayTree root, leftSubtree, rightSubtree, parentTree; int element = 0; // comparable data member (valid between 1-99); OldFamilySplayTree oldFam; String splayStat = ""; // for stat report when splaying is performed int rotateCount = 0; boolean statMode = false; // The following are used in display layout: int depth; // relative y position of this node in the display int column; // relative x position in display, in units of nodes int maxdepth; // height of tree whose root is this node. int xcenter; // position of center of root relative to left side of tree. int ycenter;

/** 112

* Constructor por Defecto: */ SplayTree() { } // no hace nada

/** * Constructor: Crea un único nodo con los datos asignados. * @param x comparable data(integer number) */ SplayTree(int x) { element = x; }

/** * Comprueba si un nodo del árbol es externo - es decir, el nodo no tiene subarboles, es decir que sea una hoja. * @return true si el nodo es externo, sino false. */ boolean isExternal() { return ((leftSubtree == null) && (rightSubtree == null)); }

/** * Comprueba si un nodo es la raíz del árbol Splay * @return true si el nodo es la raíz, sino falso. */ boolean isRoot() { return (parentTree == null); }

/** * Asigna un nodo nuevo a la raíz del árbol Splay. * @param root toma el valor de node, que es la nueva raiz. */ void setRoot(SplayTree node) { root = node; }

/** * Accede a la raíz del árbol Splay. * @return la raíz del árbol Splay. */ SplayTree getRoot() { return root; }

/** * Comprueba si un nodo es el hijo izquierdo de su padre. * @return true si el nodo es el hijo izquierdo de su padre, sino false. */ boolean isLeftSubtree() { return ((parentTree != null) && (parentTree.leftSubtree == this)); }

/** * Comprueba si un nodo es el hijo derecho de su padre. * @return true si el nodo es el hijo derechoo de su padre, sino false. 113

*/ boolean isRightSubtree() { return ((parentTree != null) && (parentTree.rightSubtree == this)); }

/** * Encuentra el valor mínimo de los datos guardados en el Árbol Splay * @param T el nodo que funciona como raíz del árboles (o cualquier subarbol del Árbol Splay). * El valor se busca en el subárbol izquierdo debido a la filosofía de un AB.B * @return un nodo cuyo dato es el valor mínimo en el Árbol Splay. */ SplayTree findMin(SplayTree T) { if (T == null) { return null; } else if (T.leftSubtree == null) { return T; //T es el nodo cuyo elemento es el valor mínimo return findMin(T.leftSubtree); // Encuentra recursivamente en subárbol izquierdo el valor mínimo. }

el

/** *Buscar el máximo valor de los datos Árbol Splay. *@param T el nodo que funciona como raíz del árboles (o cualquier subarbol del Árbol Splay). * El valor se busca en el subárbol derecho debido a la filosofía de un AB.B * @return un nodo cuyo dato es el valor máximo en el Árbol Splay. */ SplayTree findMax(SplayTree T) { if (T == null) { return null; } else if (T.rightSubtree == null) { return T; // T es el nodo cuyo elemento es el valor máximo } return findMax(T.rightSubtree); // Encuentra recursivamente en el subárbol derecho el valor mínimo. }

/** * Encuentra un valor buscado en el árbol secuencialmente. * Si lo encuentra llama al método splay() para ajustar el árbol de tal manera que el nodo visitado quede más cerca de la raíz. * @param element valor a buscar en el Árbol Splay. * @return el nodo, si fue encontrado, en la que se realiza splaying. nulo si no se encuentra. */ SplayTree find(int element) { SplayTree T = root; //Encuentra el valor buscado hasta que el árbol no tenga más subárboles, utilizando las propiedas de un AB.B while (T != null) { if (T.element == element) { // Encontrado

114

break; } else if (T.element > element) { T = T.leftSubtree; } else { T = T.rightSubtree; } } if (T == null) { // No se encontró return null; } else { splay(T); // Se bisela el nodo encontrado return T; } }

/** * Inserta un nodo en el árbol Splay. Después de la inserción, el Árbol Splay realiza secuencial * Insert a node into the Splay Tree. After insertion, the Splay Tree performs sequential * self-reconstructing processes, so called splay, in order to bring the inserted node * up to the root of the tree. * @param element comparable data which will be inserted into the Splay Tree. */ void insert(int element) { // Crea un nuevo nodo con el elemento a insertar. SplayTree node = new SplayTree(element); //Si el árbol Splay está vacío, es decir, no tiene raíz, // entonces asigna el nuevo nodo a la raíz del árbol. if (root == null) { root = node; return; // En este caso no se necesita biselar el nodo. } SplayTree parent = null; SplayTree T = root; // Busca la ubicación adecuada para insertar el nodo, utilizando las propiedades de un AB,B. while (T != null) { parent = T; if (T.element == node.element) { // El elemento ya estaba en el Árbol Splay break; } else if (T.element > node.element) { T = T.leftSubtree; } else { T = T.rightSubtree; } }

115

if (node.element == parent.element) { String msg = parent.element + " is already in the Splay Tree."; report(msg); splay(parent); // Se bisela el nodo padre en caso de que sea el nodo que se iba a insertar. return; } //Inserta el nodo en el árbol Splay el la posición que se obtuvo en el while anterior. if (parent.element > node.element) { parent.leftSubtree = node; if (node != null) { node.parentTree = parent; } } else { parent.rightSubtree = node; if (node != null) { node.parentTree = parent; } } splay(node); // Despues de la inserción, se biselado el nodo. }

/** * This is a helper method for Delete method. It replaces a node with a new node so that * the new node is connected to the parent of the previous node. Note that it should take * care of the pointers of both direction (parent <-> child). * @param T a node to be replaced. * @param newT a node to replace T. */ void replace(SplayTree T, SplayTree newT) { if (T.isRoot()) { // Update the root of the Splay Tree root = newT; if (newT != null) { newT.parentTree = null; } } else { if (T.isLeftSubtree()) { // Make newT be a new left child of the parent of the previous node, T T.parentTree.leftSubtree = newT; if (newT != null) { // Make newT have the parent of the previous node as a new parent newT.parentTree = T.parentTree; } } else { T.parentTree.rightSubtree = newT; if (newT != null) {

116

newT.parentTree = T.parentTree; } } } }

/** * Delete a node from the Splay Tree. When a node is deleted, its subtrees should * be reconnected to the Splay Tree somehow without violating the properties of BST. * If a node with two children is deleted, a node with the minimum-valued element * in the right subtrees replaces the deleted node. It does NOT guarantee the balance * of the Splay Tree. * @param x an element to be deleted from the Splay Tree. */ void delete(int x) { boolean wasRoot = false; SplayTree node = root; // Find the element to be deleted while (node != null) { if (node.element == x) { // Found break; } else if (node.element > x) { node = node.leftSubtree; } else { node = node.rightSubtree; } } if (node == null) { String msg = x + " is NOT in the Splay Tree."; report(msg); } else { wasRoot = node.isRoot(); // whether the node is the root or not // The node has no subtrees, so just replace with null if (node.isExternal()) { replace(node, null); } // The node has at least one child, also the node might be the root else if (node.leftSubtree == null) { // the node has only right child replace(node, node.rightSubtree); } else if (node.rightSubtree == null) { // the node has only left child replace(node, node.leftSubtree); } else { // The node has two children // Get a successive node to replace the node that will be deleted SplayTree newNode = findMin(node.rightSubtree);

117

// Special case: the successive node is actually right child of the node to be deleted // The successive node will carry its own right child when it replace the node. if (newNode == node.rightSubtree) { replace(node, newNode); newNode.leftSubtree = node.leftSubtree; } else { // Now the succesive node should be replaced before it is used // Ensured that it has no left child since it's the minimum of subtrees if (newNode.rightSubtree == null) { replace(newNode, null); } else { // The succesive node has right child to take care of replace(newNode, newNode.rightSubtree); } // Replace the node with the succesive node, updating subtrees as well replace(node, newNode); newNode.leftSubtree = node.leftSubtree; newNode.rightSubtree = node.rightSubtree; } } String msg = x + " is succesively deleted from the Splay Tree."; report(msg); // Finally, splaying

at

the

parent

of

the

deleted

node. if (!wasRoot) { splay(node.parentTree); } else { splay(root); } // Delete the node completely node.leftSubtree = null; node.rightSubtree = null; node.parentTree = null; } }

/** * Splay a node until it reaches up to the root of the Splay Tree. Depending on the location * of a target node, parent, and grandparent, splaying applies one of Zig, Zig-Zig, or Zig-Zag * rotation at each stage. This method is called when a data is accessed by any operations. 118

* @param T a target node at which splaying is performed. */ void splay(SplayTree T) { // total depth of T's family before splaying // Family consists of parent, sibling, children, but not including T itself // This is to see how the data near the splayed data are improved for faster // accesss in future, after spalying T.oldFam = new OldFamilySplayTree(T); double oldFamDepth = T.oldFam.getFamilyDepth() /(double)T.oldFam.numFam; // Keep splaying until T reaches the root of the Splay Tree while (!T.isRoot()) { SplayTree p = T.parentTree; SplayTree gp = p.parentTree; // T has a parent, but no grandparent if (gp == null) { splayStat = splayStat + "Zig "; if (T.isLeftSubtree()) { splayStat = splayStat + "from Left. "; } else { splayStat = splayStat + "from Right. "; } rotation(T); // Zig rotation rotateCount++; } else { // T has both parent and grandparent if (T.isLeftSubtree() == p.isLeftSubtree()) { // T and its parent are in the same direction: Zig-Zig rotation splayStat = splayStat + "Zig-Zig " ; if (T.isLeftSubtree()) { splayStat

=

splayStat + "from Left, "; } else { splayStat = splayStat + "from Right, "; } rotation(p); rotation(T); rotateCount++; } else { // T and its parent are NOT in the same direction: Zig-Zag rotation splayStat = splayStat + "Zig-Zag "; if (T.isRightSubtree()) { splayStat = splayStat + "from Left, "; } else { splayStat = splayStat + "from Right, "; } rotation(T); rotation(T); rotateCount++; } } }

119

// Report additional statistics of rotations if (statMode) { String stat = "Sequence of rotations: " + splayStat + "\n" + "; Total number of rotations: " + rotateCount + "\n" + "; Average depth of old family: " + oldFamDepth; report(stat); } splayStat reporting), reset the variables }

=

"";

rotateCount

=

0;

//

after

splaying(and

/** * Rotate subtrees of the Splay Tree. It updates subtrees of a grandparent, if exists, for * doulbe rotations, and performs single rotation depending on whether a node is left * child or right child. * @param T a node at which single rotation should be performed. */ void rotation(SplayTree T) { SplayTree p = T.parentTree; SplayTree gp = null; if (p != null) { gp = p.parentTree; } if (!T.isRoot()) { // whether T is originally

left

child

or

right child final boolean wasLeft = T.isLeftSubtree(); // T has grandparent if (gp != null) { // Replace subtree of grandparent with T for Double rotations if (gp.leftSubtree == p) { gp.leftSubtree = T; T.parentTree = gp; } else { gp.rightSubtree = T; T.parentTree = gp; } } else { // T has no grandparent, set T to the new root. root = T; T.parentTree = null; } // Rotate from left if (wasLeft) { // Attach T's right child to its parent's left child p.leftSubtree = T.rightSubtree; if (T.rightSubtree != null) { T.rightSubtree.parentTree

=

p;

//

update the parent of T's subtree } // Now rotate T, so T's parent becomes T's right child T.rightSubtree = p;

120

if (p != null) { p.parentTree = T; } } else { // Rotate from right // Attach T's left child to its parent's right child p.rightSubtree = T.leftSubtree; if (T.leftSubtree != null) { T.leftSubtree.parentTree = p; // update the parent of T's subtree } // Now rotate T, so T's parent becomes T's left child T.leftSubtree = p; if (p != null) { p.parentTree = T; } } } }

/** * Self painting method. * @param g graphic object * @param xpos x-cordinate of a node in cartesian plane * @param ypos y-cordinate of a node in cartesian plane */ void paint(Graphics g, int xpos, int ypos) { treeColumns(); paintHelper(g, xpos, ypos); }

/** * Actually paint the tree by drawing line, node(circle), and data(integer) * @param g graphic object * @param xpos x-cordinate of a node in cartesian plane * @param ypos y-cordinate of a node in cartesian plane */ void paintHelper(Graphics g, int xpos, int ypos) { String space = ""; if (element < 10) { space = " "; } if (! isExternal()) { g.setColor(Color.blue); if (leftSubtree != null) { g.drawLine(xcenter + xpos - 10, ycenter + ypos, leftSubtree.xcenter + xpos, leftSubtree.ycenter

+

ypos - 10); } if (rightSubtree != null) { g.drawLine(xcenter + xpos + 10, ycenter + ypos, rightSubtree.xcenter + xpos,

121

rightSubtree.ycenter

+

ypos - 10); } g.setColor(new Color(102,0,204)); g.fillOval(xpos + column*nodeHorizSpacing -1, ypos + depth*nodeVertSpacing -1, nodeWidth+2, nodeHeight+2); g.setColor(treeColor); g.fillOval(xpos + column*nodeHorizSpacing,

ypos

+

depth*nodeVertSpacing, nodeWidth, nodeHeight); g.setColor(Color.black); } if (isExternal()) { g.setColor(new Color(102,0,204)); g.fillOval(xpos + column*nodeHorizSpacing -1, ypos + depth*nodeVertSpacing -1, nodeWidth+2, nodeHeight+2); g.setColor(treeColor); g.fillOval(xpos + column*nodeHorizSpacing, ypos + depth*nodeVertSpacing, nodeWidth, nodeHeight); g.setColor(Color.black); g.drawString( space + element, xpos

+

column*nodeHorizSpacing + leftOffset, ypos + depth*nodeVertSpacing + nodeHeight - 8 ); } else { g.drawString(space + element, xpos + column*nodeHorizSpacing + leftOffset, ypos + depth*nodeVertSpacing + nodeHeight - 8); // recursive call to paint subtrees if (leftSubtree != null) { leftSubtree.paintHelper(g, xpos, ypos); } if (rightSubtree != null) { rightSubtree.paintHelper(g, xpos, ypos); } } }

/** * Inorder traversal, filling in the depth and the column index of each node * for display purposes. It should also deal with the case where a node has * only one child. * @param currentDepth the current depth of a node * @return the column index of the rightmost node. */ int traverse(int currentDepth) { depth = currentDepth; if (isExternal()) { column = m; m++;

122

maxdepth = depth; } if (leftSubtree == null && rightSubtree != null) { column = m; m++; } if (leftSubtree != null){ leftSubtree.traverse(depth + 1); column = m; m++; } xcenter = column*nodeHorizSpacing + (nodeWidth / 2); ycenter = depth*nodeVertSpacing + nodeHeight - ycentering; if (rightSubtree != null) { int rm = rightSubtree.traverse(depth + 1); if (leftSubtree == null) { maxdepth = rightSubtree.maxdepth; } else { maxdepth = Math.max(leftSubtree.maxdepth, rightSubtree.maxdepth); } return rm; } else { return column; } }

/** * Determine total column index of each node, filling a column index of * each node for display purpose. * @return total column index of the Splay Tree */ int treeColumns() { m = 0; return traverse(0) + 1; }

/** * Determine the height of the Splay Tree * @param T a node that roots the Splay Tree * @return the height of the Splay Tree at the node */ int treeHeight(SplayTree T) { if (T == null) { return -1; } return (1 + Math.max( treeHeight(T.rightSubtree))); }

treeHeight(T.leftSubtree),

/** * Get the width needed to display the tree * @return the width of the entire Splay Tree */ int getDisplayWidth() {

123

int hGap = nodeHorizSpacing - nodeWidth; int val = treeColumns() * (nodeHorizSpacing) - hGap; return val; }

/** * Get the height needed to display the tree * @return the height of the entire Splay Tree */ int getDisplayHeight() { int maxHeight = treeHeight(root); int val = (maxHeight+1)* nodeVertSpacing - nodeVGap; return val; } } //////////////////// End of SplayTree class /////////////////////

/** * OldFamilySplayTree Class: * * This inner class is to store old family of a splayed node. * Therefore, after splaying, we can track the old family of the new root * and calculate the relative improvement in of depth. After splaying, * the most-recently-accessed data becomes available for O(1) access in the * next time. In addition, all family also improve the access time * in future. This is a simple way to compare the cost of access to those * family me before splaying and after splaying. * * @author Hyung-Joon Kim * */ public class OldFamilySplayTree { // Family of a node which will be splayed SplayTree oldParent, oldSibling, oldLeftChild, oldRightChild; int numFam; // Numbers of family

/** * Default Constructor: * @param T a node which will be splayed and needs to create old family of it */ OldFamilySplayTree(SplayTree T) { if (T.parentTree != null) { oldParent = T.parentTree; numFam++; } if (T.leftSubtree != null) { oldLeftChild = T.leftSubtree; numFam++; } if (T.rightSubtree != null) { oldRightChild = T.rightSubtree; numFam++; } if (T.isLeftSubtree()) {

124

if (T.parentTree != null && T.parentTree.rightSubtree != null) { oldSibling = T.parentTree.rightSubtree; numFam++; } } else { if (T.parentTree != null && T.parentTree.leftSubtree != null) { oldSibling = T.parentTree.leftSubtree; numFam++; } } }

/** * Calculate the average depth of all family member nodes. * This method can calculate the depth before splaying by being called * in the SPLAY method, and the depth after splaying by being called * after repaiting the tree since the depth will is updated in the * PAINT method. * @return the average depth of all family member nodes. */ double getFamilyDepth() { double famDepth = 0.0; if (oldParent != null) { famDepth = famDepth + (double)oldParent.depth; } if (oldSibling != null) { famDepth = famDepth + (double)oldSibling.depth; } if (oldLeftChild != null) { famDepth = famDepth + (double)oldLeftChild.depth; } if (oldRightChild != null) { famDepth = famDepth + (double)oldRightChild.depth; } return famDepth; } } //////////////////// End of OldFamilySplayTree class ///////////////////// // Paint the Splay tree in a left-to-right sequence of trees. void paintTrees(Graphics g) { g.setFont(treeFont); int ystart = yTreeTops; int ypos = ystart; int xpos = leftMargin; g.setFont(headingFont); g.drawString("Splay Tree Demonstration :", xpos, yTreeTops - 20); if (theSplayTree.getRoot() != null) { g.setFont(treeFont); theSplayTree.getRoot().paint(g,xpos,ypos);

125

xpos += interTreeGap; xpos += theSplayTree.getRoot().getDisplayWidth(); } }

/* A handy function that reports a message to both the * status line of the applet and the history window. * Multiline messages are not fully visible in the status line. */ void report(String message) { statusLine.setText(message); history.appendText("; " + message + "\n"); } } // Recuerden que es un applet

Árbol multicamino Los árboles multicamino o árboles multirrama son estructuras de datos de tipo árbol usadas en computació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-1 Enlacei, 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.

126

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 s 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.

Árbol-B

Ejemplo de árbol B. En las ciencias de la computación, los árboles-B ó B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.

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.

127

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 a los nodos excede al tiempo de 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 breve 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 arbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un arbol que satisface las siguientes propiedades: 1. 2. 3. 4. 5. 6.

Cada nodo tiene como máximo M hijos. Cada nodo (excepto raiz y hojas) tiene como mínimo M/2 hijos. La raiz tiene al menos 2 hijos si no es un nodo hoja. Todos los nodos hoja aparecen al mismo nivel,y no tienen hijos. Un nodo no hoja con k hijos contiene k-1 elementos almacenados. 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 mayor que rm .

Altura: El mejor y el peor caso En el mejor de los casos,la altura de un arbol-B es:

logMn En el peor de los casos,la altura de un arbol-B es:

Donde M es el número máximo de hijos que puede tener un nodo. 128

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 #include <stdlib.h> #define TAMANO 1000 struct stclave { int valor; long registro; }; class bnodo { public: bnodo (int nClaves); // Constructor ~bnodo (); // Destructor private:

129

int clavesUsadas; stclave *clave; bnodo **puntero; bnodo *padre;

// // // //

Claves usadas en el nodo Matriz de claves del nodo Matriz de punteros a bnodo Puntero al nodo 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

130

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 iesimo. 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 ite una sola pasada por el árbol desde la raiz,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 definicion 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. 131

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 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 Archivo:Eliminarnodohoja-b.jpg teliminar clave 65 del 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 132

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 hemano 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 hemanos 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 133

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: 5 10 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 134

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.

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 concurrente por múltiples s. Un dato a ser considerado en las bases de datos, por ejemplo y/o otro árbol basado en ISAM (Métodos Indexados de Secuencial) métodos de almacenamiento.

Árbol-B+

135

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 Informatica 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.

Conjunto (programación) Un Conjunto es una Estructura de datos que consiste en una colección de elementos cuyo orden o cantidad de repeticiones no es observado. Es decir, { 1 2 3 } { 1 3 2 } { 1 2 1 2 3 } son el mismo conjunto.

136

Para describir un conjunto se utilizan dos operaciones: una que indica si está vacío y otra, si un determinado elemento pertenece a él. Por otro lado, para construirlo, se necesita una operación que genere un conjunto vacío y otra para agregar un elemento a uno preexistente.

OPERACIONES AVANZADAS SOBRE CONJUNTOS SET[G]Une el conjunto dado con el conjunto S. union: SET[G] X SET[G] SET[G]Intersecta el conjunto dado con el intersection: SET[G] X SET[G] S. SET[G]Halla la diferencia entre el conjunto difference: SET[G] X SET[G] dado y el S. boolean Determina si el conjunto dado es igual al equals: SET[G] X SET[G] conjunto S. SET[G]Devuelve una copia del conjunto original. clone: SET[G]

CONJUNTOS DISJUNTOS Los conjuntos disjuntos sirven para objetivos específicos y presentan operaciones diferentes a las ya conocidas. La estructura de conjuntos disjuntos no es más que una manera computacional de representar relaciones de equivalencia (particiones) que cambian dinámicamente mediante la unión de clases de equivalencia. NECESIDAD: Algunas aplicaciones requieren agrupar n elementos distintos en una colección de conjuntos disjuntos, formando una partición del conjunto original (de n elementos). Dos operaciones esenciales sobre Conjuntos Disjuntos: - encontrar en cual de los conjuntos esta un elemento dado - unir (mezclar) dos conjuntos en uno.

Teoría de grafos

Diagrama de un grafo con 6 vértices y 7 aristas.

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (arcs en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

137

Historia

Puentes de Königsberg.

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología. En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos. En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

Estructuras de datos en la representación de grafos Artículo principal: Grafo (estructura de datos)

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen rápido, pero pueden consumir grandes cantidades de memoria.

Estructura de lista lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se 138

representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.

Ejemplo de lista de adyacencia

Estructuras matriciales Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado) Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño n2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento mx,y es 1, de lo contrario, es 0.

Definiciones

Vértice Artículo principal: Vértice (teoría de grafos)

Los vértices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices. Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos. 139

Grafo Artículo principal: Grafo

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que . Para simplificar, notaremos la arista (a,b) como ab. En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro. Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.

Subgrafo Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación). El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G. Definición: Sea G=(V, A). G‘=(V‘,A‘) se dice subgrafo de G si: 1- V‘ V 2- A' A 3- (V‘,A‘) es un grafo Si G’=(V’,A’) es subgrafo de G, para todo v G se cumple gr (G’,v)≤ gr (G, v)

G2 es un subgrafo de G.

140

Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente: Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido). En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas. Aquí V = { a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }. Se considera la característica de "grado" (positivo o negativo) de un vértice v (y se indica como (v)), como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas incidentes a este vértice. Por ejemplo, el grado positivo (salidas) de d es 3, mientras que el grado negativo (llegadas) de d es 0. Según la terminología seguida en algunos problemas clásicos de Investigación Operativa (p.ej.: el Problema del flujo máximo), a un vértice del que sólo salen aristas se le denomina fuente (en el ejemplo anterior, el vértice d); tiene grado negativo 0. Por el contrario, a aquellos en los que sólo entran aristas se les denomina pozo o sumidero (en el caso anterior, el vértice e); tiene grado positivo 0. A continuación se presentan las implementaciones en maude de grafos no dirigidos y de grafos dirigidos.En los dos casos, las especificaciones incluyen, además de las operaciones generadoras, otras operaciones auxiliares.

Ciclos y caminos hamiltonianos Artículo principal: Ciclo hamiltoniano

Ejemplo de un ciclo hamiltoniano. 141

Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega). Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas). Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro. Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos. Existen, sin embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños. El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NPcompletos.

Caracterización de grafos

Grafos simples Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple.

Grafos conexos Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo. Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS). En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas

142

cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Grafos completos Artículo principal: Grafo completo

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente de n vértices. Un Kn, es decir, grafo completo de n vértices tiene exactamente

, siendo

el grafo completo

aristas.

La representación gráfica de los Kn como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos Artículo principal: Grafo bipartito

Un grafo G es bipartito si puede expresarse como son la unión de dos grupos de vértices), bajo las siguientes condiciones:

(es decir, sus vértices

V1 y V2 son disjuntos y no vacíos. Cada arista de A une un vértice de V1 con uno de V2. No existen aristas uniendo dos elementos de V1; análogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

143

Operaciones en Grafos

Subdivisión elemental de una arista se convierte en Se reemplaza la arista

por dos aristas

y un vértice w.

Después de realizar esta operación, el grafo queda con un vértice y una arista más.

Eliminación débil de un vértice Si y g(v) = 2 (Sea v un vértice del grafo y de grado dos) eliminarlo débilmente significa reemplazarlo por una arista que une los vértices adyacentes a v. se convierte en Entonces e' y e'' desaparecen y aparece

Homeomorfismo de grafos Artículo principal: Homeomorfismo de grafos

Dos grafos G1 y G2 son homeomorfos si ambos pueden obtenerse a partir del mismo grafo con una sucesión de subdivisiones elementales de aristas.

Árboles Artículo principal: Árbol (teoría de grafos)

Ejemplo de árbol.

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay nn-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas. Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas. 144

Grafos ponderados o etiquetados En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado. Formalmente, es un grafo con una función v: A → R+. Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas. Y, de momento, no se conocen métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.

Teorema de los cuatro colores Artículo principal: Teorema de los cuatro colores

En 1852 Francis Guthrie planteó el problema de los cuatro colores.

Otro problema famoso relativo a los grafos: ¿Cuántos colores son necesarios para dibujar un mapa político, con la condición obvia que dos países adyacentes no puedan tener el mismo color? Se supone que los países son de un solo pedazo, y que el mundo es esférico o plano. En un mundo en forma de toro; el teorema siguiente no es válido: Cuatro colores son siempre suficientes para colorear un mapa. El mapa siguiente muestra que tres colores no bastan: Si se empieza por el país central a y se esfuerza uno en utilizar el menor número de colores, entonces en la corona alrededor de a alternan dos colores. Llegando al país h se tiene que introducir un cuarto color. Lo mismo sucede en i si se emplea el mismo método. La forma precisa de cada país no importa; lo único relevante es saber qué país toca a qué otro. Estos datos están incluidos en el grafo donde los vértices son los países y las aristas conectan los que justamente son adyacentes. Entonces la cuestión equivale a atribuir a cada vértice un color distinto del de sus vecinos. Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fácil. Pero el teorema de los cuatro colores no es nada obvio. Prueba de ello es que se han tenido 145

que emplear ordenadores para acabar la demostración (se ha hecho un programa que permitió verificar una multitud de casos, lo que ahorró muchísimo tiempo a los matemáticos). Fue la primera vez que la comunidad matemática aceptó una demostración asistida por ordenador, lo que ha creado una fuerte polémica dentro de la comunidad matemática, llegando en algunos casos a plantearse la cuestión de que esta demostración y su aceptación es uno de los momentos que han generado una de las más terribles crisis en el mundo matemático.

Coloración de grafos Artículo principal: Coloreo de grafos

Colores en los vértices.

Definición: Si G=(V, E) es un grafo no dirigido, una coloración propia de G, ocurre cuando coloreamos los vértices de G de modo que si {a, b} es una arista en G entonces a y b tienen diferentes colores. (Por lo tanto, los vértices adyacentes tienen colores diferentes). El número mínimo de colores necesarios para una coloración propia de G es el número cromático de G y se escribe como C (G). Sea G un grafo no dirigido sea λ el número de colores disponibles para la coloración propia de los vértices de G. Nuestro objetivo es encontrar una función polinomial P (G,λ), en la variable λ, llamada polinomio cromático de G , que nos indique el número de coloraciones propias diferentes de los vértices de G, usando un máximo de λ colores. Descomposición de polinomios cromáticos. Si G=(V, E) es un grafo conexo y e pertenece a Ε , entonces: P (Ge,λ)=P (G,λ)+P (Ge,λ) Para cualquier grafo G, el término constante en P (G,λ) es 0 Sea G=(V, E) con |E|>0 entonces, la suma de los coeficientes de P (G,λ) es 0. Sea G=(V, E), con a, b pertenecientes al conjunto de vértices V pero {a, b}=e, no perteneciente a al conjunto de aristas E. Escribimos G+e para el grafo que se obtiene de G al añadir la arista e={a, b}. Al identificar los vértices a y b en G, obtenemos el subgrafo G++e de G.

146

Grafos planos Artículo principal: Grafo plano

Un grafo es plano si se puede dibujar sin cruces de aristas.

Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano. Un juego muy conocido es el siguiente: Se dibujan tres casas y tres pozos. Todos los vecinos de las casas tienen el derecho de utilizar los tres pozos. Como no se llevan bien en absoluto, no quieren cruzarse jamás. ¿Es posible trazar los nueve caminos que juntan las tres casas con los tres pozos sin que haya cruces? Cualquier disposición de las casas, los pozos y los caminos implica la presencia de al menos un cruce. Sea Kn el grafo completo con n vértices, Kn, p es el grafo bipartito de n y p vértices. El juego anterior equivale a descubrir si el grafo bipartito completo K3,3 es plano, es decir, si se puede dibujar en un plano sin que haya cruces, siendo la respuesta que no. En general, puede determinarse que un grafo no es plano, si en su diseño puede encontrase una estructura análoga (conocida como menor) a K5 o a K3,3. Establecer qué grafos son planos no es obvio, y es un problema tiene que ver con topología.

Diámetro

En la figura se nota que K4 es plano (desviando la arista ab al exterior del cuadrado), que K5 no lo es, y que K3,2 lo es también (desvíos en gris).

En un grafo, la distancia entre dos vértices es el menor número de aristas de un recorrido entre ellos. El diámetro, en una figura como en un grafo, es la menor distancia entre dos puntos de la misma. 147

El diámetro de los Kn es 1, y el de los Kn,p es 2. Un diámetro infinito puede significar que el grafo tiene una infinidad de vértices o simplemente que no es conexo. También se puede considerar el diámetro promedio, como el promedio de las distancias entre dos vértices. El mundo de Internet ha puesto de moda esa idea del diámetro: Si descartamos los sitios que no tienen enlaces, y escogemos dos páginas web al azar: ¿En cuántos clics se puede pasar de la primera a la segunda? El resultado es el diámetro de la Red, vista como un grafo cuyos vértices son los sitios, y cuyas aristas son lógicamente los enlaces. En el mundo real hay una analogía: tomando al azar dos seres humanos del mundo, ¿En cuántos saltos se puede pasar de uno a otro, con la condición de sólo saltar de una persona a otra cuando ellas se conocen personalmente? Con esta definición, se estima que el diámetro de la humanidad es de... ¡ocho solamente! Este concepto refleja mejor la complejidad de una red que el número de sus elementos. Véase también: Glosario en teoría de grafos

Algoritmos importantes Algoritmo de búsqueda en anchura (BFS) Algoritmo de búsqueda en profundidad (DFS) Algoritmo de búsqueda A* Algoritmo del vecino más cercano Ordenación topológica de un grafo Algoritmo de cálculo de los componentes fuertemente conexos de un grafo Algoritmo de Dijkstra Algoritmo de Bellman-Ford Algoritmo de Prim Algoritmo de Ford-Fulkerson Algoritmo de Kruskal Algoritmo de Floyd-Warshall

Aplicaciones Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes areas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería. Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd. Para la istración de proyectos, utilizamos técnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos. La teoría de grafos también ha servido de inspiración para las ciencias sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y 148

verifica la posición, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse gráficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vínculos (aristas), su dirección e intensidad y da idea de la manera en que el poder se transmite y a quiénes.

Tabla hash Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado.

Ejemplo de tabla hash.

Las tablas hash se suelen implementar sobre arrays de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante de búsqueda promedio O,1 sin importar el número de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, en función del número de elementos. Comparada con otras estructuras de arrays asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información. Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el ordenado a su contenido es bastante lento. Otras estructuras como árboles binarios auto-balanceables son más lentos en promedio (tiempo de búsqueda O(log n)) pero la información está ordenada en todo momento.

Funcionamiento Las operaciones básicas implementadas en las tablas hash son: inserción(llave, valor) búsqueda(llave) que devuelve valor

149

La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer funciones como iteración en la tabla, crecimiento y vaciado. Algunas tablas hash permiten almacenar múltiples valores bajo la misma clave. Para usar una tabla hash se necesita: Una estructura de directo (normalmente un array). Una estructura de datos con una clave Una función resumen (hash) cuyo dominio sea el espacio de claves y su imagen (o rango) los números naturales.

Inserción 1. Para almacenar un elemento en la tabla hash se ha de convertir su clave a un número. Esto se consigue aplicando la función resumen a la clave del elemento. 2. El resultado de la función resumen ha de mapearse al espacio de direcciones del array que se emplea como soporte, lo cual se consigue con la función módulo. Tras este paso se obtiene un índice válido para la tabla. 3. El elemento se almacena en la posición de la tabla obtenido en el paso anterior. 1. Si en la posición de la tabla ya había otro elemento, se ha producido una colisión. Este problema se puede solucionar asociando una lista a cada posición de la tabla, aplicando otra función o buscando el siguiente elemento libre. Estas posibilidades han de considerarse a la hora de recuperar los datos.

Búsqueda 1. Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la función resumen. 2. El valor obtenido se mapea al espacio de direcciones de la tabla. 3. Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.

Prácticas recomendadas para las funciones hash Una buena función hash es esencial para el buen rendimiento de una tabla hash. Las colisiones son generalmente resueltas por algún tipo de búsqueda lineal, así que si la función tiende a generar valores similares, las búsquedas resultantes se vuelven lentas. En una función hash ideal, el cambio de un simple bit en la llave (incluyendo el hacer la llave más larga o más corta) debería cambiar la mitad de los bits del hash, y este cambio debería ser independiente de los cambios provocados por otros bits de la llave. Como una función hash puede ser difícil de diseñar, o computacionalmente cara de ejecución, se han invertido muchos esfuerzos en el desarrollo de estrategias para la resolución de colisiones que mitiguen el mal rendimiento del hasheo. Sin embargo, ninguna de estas estrategias es tan efectiva como el desarrollo de una buena función hash de principio.

150

Es deseable utilizar la misma función hash para arrays de cualquier tamaño concebible. Para esto, el índice de su ubicación en el array de la tabla hash se calcula generalmente en dos pasos: 1. Un valor hash genérico es calculado, llenando un entero natural de máquina 2. Este valor es reducido a un índice válido en el arreglo encontrando su módulo con respecto al tamaño del array.

El tamaño del arreglo de las tablas hash es con frecuencia un número primo. Esto se hace con el objetivo de evitar la tendencia de que los hash de enteros grandes tengan divisores comunes con el tamaño de la tabla hash, lo que provocaría colisiones tras el cálculo del módulo. Sin embargo, el uso de una tabla de tamaño primo no es un sustituto a una buena función hash. Un problema bastante común que ocurre con las funciones hash es el aglomeramiento. El aglomeramiento ocurre cuando la estructura de la función hash provoca que llaves usadas comúnmente tiendan a caer muy cerca unas de otras o incluso consecutivamente en la tabla hash. Esto puede degradar el rendimiento de manera significativa, cuando la tabla se llena usando ciertas estrategias de resolución de colisiones, como el sondeo lineal. Cuando se depura el manejo de las colisiones en una tabla hash, suele ser útil usar una función hash que devuelva siempre un valor constante, como 1, que cause colisión en cada inserción. Funciones Hash más usadas: 1. Hash de División:

Dado un diccionario D, se fija un número m >= |D| (m mayor o igual al tamaño del diccionario) y que sea primo no cercano a potencia de 2 o de 10. Siendo k la clave a buscar y h(k) la función hash, se tiene h(k)=k%m (Resto de la división k/m). 2. Hash de Multiplicación

Si por alguna razón, se necesita una tabla hash con tantos elementos o punteros como una potencia de 2 o de 10, será mejor usar una función hash de multiplicación, independiente del tamaño de la tabla. Se escoge un tamaño de tabla m >= |D| (m mayor o igual al tamaño del diccionario) y un cierto número irracional φ (normalmente se usa 1+5^(1/2)/2 o 1-5^(1/2)/2). De este modo se define h(k)= Suelo(m*Parte fraccionaria(k*φ))

Resolución de colisiones Si dos llaves generan un hash apuntando al mismo índice, los registros correspondientes no pueden ser almacenados en la misma posición. En estos casos, cuando una casilla ya está ocupada, debemos encontrar otra ubicación donde almacenar el nuevo registro, y hacerlo de tal manera que podamos encontrarlo cuando se requiera. Para dar una idea de la importancia de una buena estrategia de resolución de colisiones, considerese el siguiente resultado, derivado de la paradoja de las fechas de nacimiento. Aun cuando supongamos que el resultado de nuestra función hash genera índices aleatorios distribuidos 151

uniformemente en todo el arreglo, e incluso para arreglos de 1 millón de entradas, hay un 95% de posibilidades de que al menos una colisión ocurra antes de alcanzar los 2500 registros. Hay varias técnicas de resolución de colisiones, pero las más populares son encadenamiento y direccionamiento abierto.

Encadenamiento En la técnica más simple de encadenamiento, cada casilla en el array referencia una lista de los registros insertados que colisionan en la misma casilla. La inserción consiste en encontrar la casilla correcta y agregar al final de la lista correspondiente. El borrado consiste en buscar y quitar de la lista.

Ejemplo de encadenamiento.

La técnica de encadenamiento tiene ventajas sobre direccionamiento abierto. Primero el borrado es simple y segundo el crecimiento de la tabla puede ser pospuesto durante mucho más tiempo dado que el rendimiento disminuye mucho más lentamente incluso cuando todas las casillas ya están ocupadas. De hecho, muchas tablas hash encadenadas pueden no requerir crecimiento nunca, dado que la degradación de rendimiento es lineal en la medida que se va llenando la tabla. Por ejemplo, una tabla hash encadenada con dos veces el número de elementos recomendados, será dos veces más lenta en promedio que la misma tabla a su capacidad recomendada. Las tablas hash encadenadas heredan las desventajas de las listas ligadas. Cuando se almacenan cantidades de información pequeñas, el gasto extra de las listas ligadas puede ser significativo. También los viajes a través de las listas tienen un rendimiento de caché muy pobre. Otras estructuras de datos pueden ser utilizadas para el encadenamiento en lugar de las listas ligadas. Al usar árboles auto-balanceables, por ejemplo, el tiempo teórico del peor de los casos disminuye de O(n) a O(log n). Sin embargo, dado que se supone que cada lista debe ser pequeña, esta estrategia es normalmente ineficiente a menos que la tabla hash sea diseñada para correr a máxima capacidad o existan índices de colisión particularmente grandes. También se pueden utilizar arreglos dinámicos para disminuir el espacio extra requerido y mejorar el rendimiento del caché cuando los registros son pequeños.

152

Direccionamiento abierto Las tablas hash de direccionamiento abierto pueden almacenar los registros directamente en el arreglo. Las colisiones se resuelven mediante un sondeo del array, en el que se buscan diferentes localidades del array (secuencia de sondeo) hasta que el registro es encontrado o se llega a una casilla vacía, indicando que no existe esa llave en la tabla.

Ejemplo de direccionamiento abierto.

Las secuencias de sondeo más socorridas incluyen: sondeo lineal en el que el intervalo entre cada intento es constante--frecuentemente 1. sondeo cuadrático en el que el intervalo entre los intentos aumenta linealmente (por lo que los índices son descritos por una función cuadrática), y doble hasheo en el que el intervalo entre intentos es constante para cada registro pero es calculado por otra función hash.

El sondeo lineal ofrece el mejor rendimiento del caché, pero es más sensible al aglomeramiento, en tanto que el doble hasheo tiene pobre rendimiento en el caché pero elimina el problema de aglomeramiento. El sondeo cuadrático se sitúa en medio. El doble hasheo también puede requerir más cálculos que las otras formas de sondeo. Una influencia crítica en el rendimiento de una tabla hash de direccionamiento abierto es el porcentaje de casillas usadas en el array. Conforme el array se acerca al 100% de su capacidad, el número de saltos requeridos por el sondeo puede aumentar considerablemente. Una vez que se llena la tabla, los algoritmos de sondeo pueden incluso caer en un círculo sin fin. Incluso utilizando buenas funciones hash, el límite aceptable de capacidad es normalmente 80%. Con funciones hash pobremente diseñadas el rendimiento puede degradarse incluso con poca información, al provocar aglomeramiento significativo. No se sabe a ciencia cierta qué provoca que las funciones hash generen aglomeramiento, y es muy fácil escribir una función hash que, sin querer, provoque un nivel muy elevado de aglomeramiento.

153

Ventajas e inconvenientes de las tablas hash [editar] Una tabla hash tiene como principal ventaja que el a los datos suele ser muy rápido si se cumplen las siguientes condiciones: Una razón de ocupación no muy elevada (a partir del 75% de ocupación se producen demasiadas colisiones y la tabla se vuelve ineficiente). Una función resumen que distribuya uniformemente las claves. Si la función está mal diseñada, se producirán muchas colisiones.

Los inconvenientes de las tablas hash son: Necesidad de ampliar el espacio de la tabla si el volumen de datos almacenados crece. Se trata de una operación costosa. Dificultad para recorrer todos los elementos. Se suelen emplear listas para procesar la totalidad de los elementos. Desaprovechamiento de la memoria. Si se reserva espacio para todos los posibles elementos, se consume más memoria de la necesaria; se suele resolver reservando espacio únicamente para punteros a los elementos.

Implementación en pseudocódigo El pseudocódigo que sigue es una implementación de una tabla hash de direccionamiento abierto con sondeo lineal para resolución de colisiones y progresión sencilla, una solución común que funciona correctamente si la función hash es apropiada. registro par { llave, valor } var arreglo de pares casilla[0..numcasillas-1] function buscacasilla(llave) { i := hash(llave) módulo de numcasillas loop { if casilla[i] esta libre or casilla[i].llave = llave return i i := (i + 1) módulo de numcasillas } } function busqueda(llave) i := buscacasilla(llave) if casilla[i] está ocupada // llave en la tabla return casilla[i].valor else // llave es está en la tabla return no encontrada function asignar(llave, valor) { i := buscacasilla(llave) if casilla[i] está ocupada casilla[i].valor := valor else { if tabla casi llena {

154

hacer tabla más grande (nota 1) i := buscacasilla(llave) } casilla[i].llave := llave casilla[i].valor := valor } }

Nota 1. ↑ La reconstrucción de la tabla requiere la creación de un array más grande y el uso posterior de la función asignar para insertar todos los elementos del viejo array en el nuevo array más grande. Es común aumentar el tamaño del array exponencialmente, por ejemplo duplicando el tamaño del array.

Montículo (informática) Este artículo discute la estructura de datos montículo. Para consultar sobre el lugar de donde se asigna memoria dinámica véase Asignación dinámica de memoria.

Descripción

Ejemplo de Montículo

En computación, un montículo (heap en inglés) es una estructura de Árbol con información perteneciente a un conjunto ordenado. Los montículos tienen la característica de que cada nodo padre tiene un valor mayor que el de todos sus nodos hijos. Un árbol cumple la condición de montículo si satisface dicha condición y además es un árbol binario completo.Un árbol binario es completo cuando todos los niveles están llenos, con la excepción del último que puede quedar exento de dicho cumplimiento.

155

Ésta es la única restricción en los montículos. Ella implica que el mayor elemento (o el menor, dependiendo de la relación de orden escogida) está siempre en el nodo raíz. Debido a esto, los montículos se utilizan para implementar colas de prioridad, por la razón de que en una cola siempre se consulta el elemento de mayor valor, y esto conlleva la ventaja de que en los montículos dicho elemento está en la raíz. Otra ventaja que poseen los montículos es que su implementación usando arrays es muy eficaz, por la sencillez de su codificación y liberación de memoria, ya que no hace falta utilizar punteros.No sólo existen montículos ordenados con el elemento de la raíz mayor que el de sus hijos, sino también en caso contrario que la raíz sea menor que sus progenitores. Todo depende de la ordenación con la que nos interese programar el montículo, que debe ser parámetro de los algoritmos de construcción y de manipulación de dicho montículo. La eficiencia de las operaciones en los montículos es crucial en diversos algoritmos de recorrido de grafos y de ordenamiento (Heapsort).

Operaciones Las operaciones más importantes o básicas en un montículo son la de insercción y la de eliminación de uno o varios elementos.Dichas operaciones serán especificadas más adelante.

Insertar

Cómo se inserta un elemento en un montículo

Esta operación parte de un elemento y lo inserta en un montículo aplicando su criterio de ordenación.Si suponemos que el monticulo está estructurado de forma que la raíz es mayor que sus hijos, comparamos el elemento a insertar (incluido en la primera posición libre) con su padre.Si el hijo es menor que el padre,entonces el elemento es insertado correctamente, si ocurre lo contrario sustituimos el hijo por el padre. ¿Y si la nueva raíz sigue siendo más grande que su nuevo padre?. Volvemos a hacer otra vez dicho paso hasta que el montículo quede totalmente ordenado. En la imagen adjunta vemos el ejemplo de cómo realmente se inserta un elemento en un montículo. Aplicamos la condición de que cada padre sea mayor que sus hijos, y siguiendo dicha regla el elemento a insertar es el 12. Es mayor que su padre, siguiendo el 156

método de ordenación, sustituimos el elemento por su padre que es 9 y así quedaría el montículo ordenado. Ahora veremos la implementación en varios lenguajes de programación del algoritmo de insercción de un elemento en un montículo. En Maude el insertar se realiza a través de un constructor: op insertarHeap : X$Elt Heap{X} -> HeapNV{X} eq insertarHeap(R, crear) = arbolBin(R, crear, crear) . eq insertarHeap(R1, arbolBin(R2, I, D)) = if ((altura(I) > altura(D)) and not estaLleno?(I)) or (((altura(I) == altura(D)) and estaLleno?(D)) then arbolBin(max(R1, R2),insertarHeap(min(R1, R2), I), D) else arbolBin(max(R1, R2), I,insertarHeap(min(R1, R2), D)) fi .

En Pseudolenguaje quedaría: PROC Flotar ( M, i ) MIENTRAS (i>1) ^ (M.Vector_montículo[i div 2] < M.Vector montículo[i] HACER intercambiar M.Vector montículo[i div 2] ^ M.Vector_montículo[i] i = i div 2 FIN MIENTRAS FIN PROC PROC Insertar ( x, M ) SI M.Tamaño_montículo = Tamaño_máximo ENTONCES error Montículo lleno SINO M.Tamaño_montículo = M.Tamaño_montículo + 1 M.Vector_montículo[M.Tamaño montículo] = x Flotar ( M, M.Tamaño_montículo ) FIN PROC

En Java el código sería el siguiente: public void insertItem(Object k, Object e) throws InvalidKeyException { if(!comp.isComparable(k)) throw new InvalidKeyException("Invalid Key");

157

Position z = T.add(new Item(k, e)); Position u; while(!T.isRoot(z)) { // bubbling-up u = T.parent(z); if(comp.isLessThanOrEqualTo(key(u),key(z))) break; T.swapElements(u, z); z = u; } }

Eliminar En este caso eliminaremos el elemento máximo de un montículo.La forma más eficiente de realizarlo sería buscar el elemento a borrar,colocarlo en la raíz e intercambiarlo por el máximo valor de sus hijos satisfaciendo así la propiedad de montículos de máximos. En el ejemplo representado vemos como 19 que es el elemento máximo es el sujeto a eliminar. Archivo:Eliminarmaxmonticulo.gif Como se elimina un elemento en un montículo

Se puede observar que ya está colocado en la raiz al ser un montículo de máximos, los pasos a seguir son: 1. Eliminar el elemento máximo (colocado en la raíz) 2. Hemos de subir el elemento que se debe eliminar, para cumplir la condición de montículo a la raíz, que ha quedado vacía. 3. Una vez hecho esto queda el último paso el cual es ver si la raíz tiene hijos mayores que ella si es así, aplicamos la condición y sustituimos el padre por el mayor de sus progenitores.

A continuación veremos la especificación de eliminar en distintos lenguajes de programación. En Maude el código será el siguiente: eq eliminarHeap(crear) = crear . eq eliminarHeap(HNV) = hundir(arbolBin(ultimo(HNV), hijoIzq(eliminarUltimo(HNV)), hijoDer(eliminarUltimo(HNV)) )

Donde hundir es una operación auxiliar que coloca el nodo en su sitio correspondiente. En código Java: public Object removeMin() throws PriorityQueueEmptyException { if(isEmpty()) throw new PriorityQueueEmptyException("Priority Queue Empty!"); Object min = element(T.root()); if(size() == 1) T.remove();

158

else { T.replaceElement(T.root(), T.remove()); Position r = T.root(); while(T.isInternal(T.leftChild(r))) { Position s; if(T.isExternal(T.rightChild(r)) comp.isLessThanOrEqualTo(key(T.leftChild(r)),key(T.rightChild(r)))) s = T.leftChild(r); else s = T.rightChild(r); if(comp.isLessThan(key(s), key(r))) { T.swapElements(r, s); r = s; } else break; } } }

||

Tras haber especificado ambas operaciones y definir lo que es un montículo sólo nos queda por añadir que una de las utilizaciones más usuales del tipo heap (montículo) es en el algoritmo de ordenación de heapsort.También puede ser utilizado como montículo de prioridades donde la raíz es la de mayor prioridad.

Montículo binario Los Montículos binarios (binary heaps en inglés) son un caso particular y sencillo de la estructura de datos Montículo que está basada en un árbol binario balanceado, que puede verse como un árbol binario con dos restricciones adicionales: Propiedad de montículo Cada nodo contiene un valor superior al de sus hijos (para un montículo por máximos) o más pequeño que el de sus hijos (para un montículo por mínimos). Árbol semicompleto El árbol está balanceado y en un mismo nivel las inserciones se realizan de izquierda a derecha.

Los montículos por máximos se utilizan frecuentemente para representar colas de prioridad. A continuación se muestran dos montículos uno por mínimos y otro por máximos que representan el mismo conjunto de valores. 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / \ 8 9 10 11

11 / \ 9 10 / \ / \ 5 6 7 8 / \ / \ 1 2 3 4 159

El orden de los nodos hermanos en un montículo no está especificado en la propiedad de montículo, de manera que los subárboles de un nodo son intercambiables.

Operaciones sobre montículos

Inserción de un elemento La inserción de un elemento se realiza agregando el elemento en la posición que respeta la restricción de árbol semicompleto pero posiblemente invalidando la propiedad de montículo, para luego remontar hacia la raíz restaurando la propiedad de montículo por intercambio del valor de la posición desordenada por el valor de su padre. Esta reorganización se realiza en tiempo O(log n).

Ejemplo En el siguiente montículo por máximos la posición donde se puede insertar está marcada con una letra X. 11 / \ 5 8 / \ / 3 4 X Para insertar el valor 15 en este montículo, se inserta el valor en la posición marcada con lo cual se invalida la propiedad de montículo dado que 15 es mayor que 8. Para restaurar la propiedad de montículo se intercambia primero el 15 con el 8, obteniéndose el siguiente árbol: 11 / \ 5 15 / \ / 3 4 8 Sin embargo, la propiedad de montículo todavía no se cumple, dado que 15 es mayor que 11, de manera que hay que realizar un nuevo intercambio: 15 / \ 5 11 / \ / 3 4 8 El resultado si es un montículo por máximos.

160

Eliminación del elemento máximo Para borrar el elemento máximo del montículo, de la manera más eficiente se puede tomar el elemento de la posición que debe quedar vacía, colocándolo en la raíz (así cumpliendo la propiedad de árbol completo), y luego intercambiar ese valor con el máximo de sus hijos hasta satisfacer la propiedad de montículo (si es de máximos), o intercambiarlo con el mínimo de sus hijos (si es de mínimos). Esta reorganización se puede realizar también en tiempo O(log n). Partiendo del mismo montículo que antes: 11 / \ 5 8 / \ 3 4 Al eliminarse el 11, éste se remplaza por 4 (el valor del nodo que se debe eliminar): 4 / 5 / 3

\ 8

En este árbol no se cumple la propiedad de montículo dado que 8 es mayor que 4. Al intercambiarse estos dos valores se obtiene un montículo: 8 / 5 / 3

\ 4

Representación de montículos Si bien se puede utilizar un árbol binario para representar un montículo, la condición de árbol completo permite representar fácilmente un montículo en un vector colocando los elementos por niveles y en cada nivel, los elementos de izquierda a derecha.

Un árbol binario completo guardado como arrreglo

161

Dado que el árbol es completo, no es necesario almacenar apuntadores en el árbol. Siempre se puede calcular la posición de los hijos o la del padre a partir de la posición de un nodo en el arreglo (contando las posiciones del arreglo a partir de cero): El nodo raíz se almacena en la posición 0 del arreglo. Los hijos de un nodo almacenado en la posición k se almacenan en las posiciones 2k y 2k+1 respectivamente.

Se deduce que el padre de un nodo que está en la posición k (k>0) está almacenado en la posición ((k+1) div 2).

Montículo de Fibonacci En Informática, un Montículo de Fibonacci (o Heap de Fibonacci) es una estructura de datos subconjunto de los montículos, que a su vez, son un subconjunto especial dentro de los bosques de árboles. Resulta similar a un montículo binomial, pero dispone de una mejor relación entre el coste y su amortización. Los montículos de Fibonacci fueron desarrollados en 1984 por Michael L. Fredman y Robert E. Tarjan y publicados por primera vez en una revista científica en 1987. El nombre de montículos de Fibonacci viene de la sucesión de Fibonacci, que se usa en pruebas comparativas de tiempo (Benchmarking). En particular, las operaciones Insertar, Encontrar el mínimo, Decrementar la clave, y la Unión trabajan con tiempo constante amortizado. Las operaciones Borrar y Borrar el mínimo tienen un coste O(log n) como coste amortizado. Esto significa que, empezando con una estructura de datos vacía, cualquier secuencia de a operaciones del primer grupo y b operaciones del segundo grupo tardarían O(a + b log n). En un montículo binomial cualquier secuencia de operaciones tardarían O((a + b)log (n)). Un montículo de Fibonacci es mejor que un montículo binomial cuando b es asintóticamente más pequeño que a. El montículo de Fibonacci puede ser utilizado para mejorar el tiempo de ejecución asintótico del algoritmo de Dijkstra para calcular el camino más corto en un grafo y el algoritmo de Prim para calcular el árbol mínimo de un grafo.

Estructura de un Montículo de Fibonacci

Figura 1. Ejemplo de un montículo de Fibonacci. Tiene tres árboles de grados 0, 1 y 3. Tres vértices están marcados (mostrados en azul). Por lo tanto, el potencial de la pila es de 9. 162

Un Heap de Fibonacci es una colección de árboles que satisfacen la propiedad del orden mínimo del montículo (que para abreviar se suele utilizar el anglicismo "Min-Heap"), es decir, a grandes rasgos, la clave de un hijo es siempre mayor o igual que la de su padre. Esto implica que la clave mínima está siempre en la raíz. Comparado con los montículos binomiales, la estructura de un montículo de Fibonacci es más flexible. Los árboles no tienen una forma predefinida y en un caso extremo el heap puede tener cada elemento en un árbol separado o en un único árbol de profundidad n. Esta flexibilidad permite que algunas operaciones puedan ser ejecutadas de una manera "perezosa", posponiendo el trabajo para operaciones posteriores. Por ejemplo, la unión de dos montículos se hace simplemente concatenando las dos listas de árboles, y la operación Decrementar Clave a veces corta un nodo de su padre y forma un nuevo árbol. Sin embargo, se debe introducir algún orden para conseguir el tiempo de ejecución deseado. En concreto, el grado de los nodos(el número de hijos) se tiene que mantener bajo: cada nodo tiene un grado máximo de O(log n) y la talla de un subárbol cuya raíz tiene grado k es por lo menos Fk + 2 , donde Fk es un número de Fibonacci. Esto se consigue con la regla de que podemos cortar como mucho un hijo de cada nodo no raíz. Cuando es cortado un segundo hijo, el nodo también necesita ser cortado de su padre y se convierte en la raíz de un nuevo árbol. El número de árboles se decrementa en la operación Borrar mínimo, donde los árboles están unidos entre sí. Como resultado de esta estructura, algunas operaciones pueden llevar mucho tiempo mientras que otras se hacen muy deprisa. En el análisis del coste de ejecución amortizado pretendemos que las operaciones muy rápidas tarden un poco más de lo que tardan. Este tiempo extra se resta después al tiempo de ejecución de operaciones más lentas. La cantidad de tiempo ahorrada para un uso posterior es medida por una función potencial. Esta función es: Potencial = t + 2m

Donde t es el número de árboles en el montículo de Fibonacci, y m es el número de nodos marcados. Un nodo está marcado si al menos uno de sus hijos se cortó desde que el nodo se fue hecho hijo de otro nodo (todas las raíces están desmarcadas). Además, la raíz de cada árbol en un montículo tiene una unidad de tiempo almacenada. Esta unidad de tiempo puede ser usada más tarde para unir este árbol a otro con coste amortizado 0. Cada nodo marcado también tiene dos unidades de tiempo almacenadas. Una puede ser usada para cortar el nodo de su padre. Si esto sucede, el nodo se convierte en una raíz y la segunda unidad de tiempo se mantendrá almacenada como en cualquier otra raíz.

Implementación de operaciones Para permitir un Borrado y Concatenado rápido, las raíces de todos los árboles están unidas una lista de tipo circular doblemente enlazada. Los hijos de cada nodo también están unidos usando una lista. Para cada nodo, guardamos el número de hijos y si está marcado. Además guardamos un puntero a la raíz que contiene la clave mínima. La operación Encontrar Mínimo es trivial porque guardamos el puntero al nodo que lo contiene. Esto no cambia el Potencial del Montículo, ya que el coste actual y amortizado es constante. Tal como se 163

indica arriba, la Unión se implementa simplemente concatenando las listas de raíces de árboles de los dos Heaps. Esto se puede hacer en tiempo constante y no cambia su Potencia, resultando otra vez un tiempo constante amortizado. La operación Insertar trabaja creando un nuevo montículo con un elemento y haciendo la Unión. Esto se hace en tiempo constante, y el Potencial se incrementa en 1, ya que el número de árboles aumenta. El tiempo amortizado es constante igualmente.

El montículo de Fibonacci de la figura 1 después de la primera fase de extracción mínima. El nodo con clave 1 (el mínimo) se ha eliminado y sus hijos han formado árboles por separado.

La operación Extraer Mínimo (lo mismo que Borrar Mínimo) opera en tres fases. Primero cogemos la raíz con el elemento mínimo y la borramos. Sus hijos se convertirán en raíces de nuevos árboles. Si el número de hijos era d, lleva un tiempo O(d) procesar todas las nuevas raíces y el Potencial se incrementa en d-1. El tiempo de ejecución amortizado en esta fase es O(d) = O(log n).

El montículo de Fibonacci de la figura 1 después de extraer el mínimo. En primer lugar, los nodos 3 y 6 están unidos entre sí. Entonces el resultado se vincula con árboles arraigados en el nodo 2. Por último, el nuevo mínimo se encuentra.

Sin embargo, para completar la extracción del mínimo, necesitamos actualizar el puntero a la raíz con la clave mínima. El problema es que hay n raíces que comprobar. En la segunda fase decrementamos el número de raíces agrupando sucesivamente las raíces del mismo grado. Cuando dos raíces u y v tienen el mismo grado, hacemos que una de ellas sea hija de la otra de manera que la que tenga la clave menor siga siendo la raíz. Su grado se incrementará en uno. Esto se repite hasta que todas las raíces tienen un grado diferente. Para encontrar árboles del mismo grado eficientemente usamos un vector de longitud O(log n) en el que guardamos un puntero a una raíz de cada grado. Cuando una segunda raíz con el mismo grado es encontrada, las dos se unen y se actualiza el vector. El tiempo de ejecución actual es O(log n + m) donde m es el número de raíces al principio de la segunda fase. Al final tendremos como mucho O(log n) raíces (porque cada una tiene grado diferente). Así pues el Potencial se decrementa al menos m - O(log n) y el tiempo de ejecución amortizado es O(log n).

164

En la tercera fase, comprobamos cada una de las raíces restantes y encontramos el mínimo. Esto cuesta O(log n) y el potencial no cambia. El tiempo medio de ejecución amortizado para extraer el mínimo es por consiguiente O(log n).

El montículo de Fibonacci de la figura 1 después de la disminución de los principales nodos de 9 a 0. Este nodo, así como sus dos antecesores marcados se cortan del árbol enraizado en el 1 y se colocan como nuevas raíces.

La operación Decrementar Clave cogerá el nodo, decrementará la clave y se viola la propiedad del montículo(la nueva clave es más pequeña que la clave del padre), el nodo se corta de su padre. Si el padre no es una raíz, se marca. Si ya estaba marcado, se corta también y su padre se marca. Continuamos subiendo hasta que, o bien alcanzamos la raíz o un vértice no marcado. En el proceso creamos creamos un número k de nuevos árboles. El Potencial se reduce en al menos k − 2. El tiempo para realizar el corte es O(k) y el tiempo de ejecución amortizado es constante. Por último, la operación Borrar puede ser implementada simplemente decrementando la clave del elemento a borrar a menos infinito, convirtiéndolo en el mínimo de todo el montículo, entonces llamamos a Extraer Mínimo para borrarlo. El tiempo de ejecución amortizado de esta operación es O(log n).

Peor Caso Aunque el tiempo total de ejecución de una secuencia de operaciones que empiezan por una estructura vacía viene determinado por lo explicado anteriormente, algunas, aunque muy pocas, operaciones de la secuencia pueden llevar mucho tiempo(en particular Decrementar Clave, Borrar y Borrar Mínimo tienen tiempo de ejecución lineal en el peor caso). Por este motivo los montículos de Fibonacci y otras estructuras con costes amortizados pueden no ser apropiadas para sistemas de tiempo real.

Sumario de Tiempos de Ejecución

Insertar

Lista Enlazada Árbol Binario Min-Heap

Montículo de Fibonacci Lista Brodal [1]

O(1)

O(log n)

O(log n)

O(1)

O(1)

Mínimo O(n)

O(1)

O(1)

O(1)

O(1)

Borrar mínimo O(n)

O(log n)

O(log n)

O(log n)*

O(log n)

Disminuir Clave O(1)

O(log n)

O(log n)

O(1)*

O(1)

Borrar

O(n)

O(n)

O(log n)

O(log n)*

O(log n)

Unión

O(1)

O(m log(n+m)) O(m log(n+m)) O(1)

O(1)

(*)Tiempo Amortizado 165

Referencias 1. Fredman M. L. & Tarjan R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596-615. 2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 20: Fibonacci Heaps, pp.476–497. 3. Brodal, G. S. 1996. Worst-case efficient priority queues. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, Georgia, United States, January 28 - 30, 1996). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 52-58.

Montículo suave En computación, un montículo suave (soft heap en inglés) es una variante de la estructura de datos montículo. Fue concebida por Bernard Chazelle en el año 2000. Al corromper (aumentar) cuidadosamente las claves de a lo sumo un cierto porcentaje fijo de valores en el montículo, logra obtener en tiempo constante amortizado para sus cuatro operaciones: create(S): Create un nuevo montículo suave insert(S, x): Inserta un elemento en un montículo suave meld(S, S' ): Combina el contenido de dos montículo suaves en uno. Ambos parámetros son destruidos en el proceso delete(S, x): Borra un elemento de un montículo suave findmin(S): Obtiene el elemento de clave mínima en el montículo suave

Otros montículos como el montículo de Fibonacci logran este tipo de cota para algunas operaciones sin necesidad de corromper las claves, sin embargo, no logran acotar de forma constante la crítica operación delete. El porcentaje de valores que son modificados puede ser escogido libremente, pero mientras más bajo sea, más tiempo requieren las inserciones (O(log 1/ε) para una tasa de ε). Las corrupciones bajan efectivamente la entropía de información.

Aplicaciones Soprendentemente, los montículos suaves son útiles en el diseño de algoritmos deterministas, a pesar de su naturaleza impredecible. Fueron clave en la creación del mejor algoritmo conocido para calcular el Árbol de expansión mínima. También son utilizados para construir fácilmente un algoritmo de selección óptima, así como algoritmos de casi-ordenamiento que son algoritmos que colocan todo elemento cerca de su posición final, una situación que hace que el algoritmo de ordenamiento por inserción sea muy rápido. Uno de los ejemplos más sencillo es el algoritmo de selección. Supóngase que se desea encontrar el k-ésimo más grande de un grupo de n números. Primero se escoge una tasa de error de 1/4; es decir, a lo sumo 25% de las claves pueden estar corruptas. Se insertan todos los n elementos en el montículo suave — en este punto, a lo sumo n/4 claves están corruptas. A continuación se borra el elemento mínimo del montículo n/2 veces. Dado que de esta forma se disminuye el tamaño del montículo suave, el total de elementos con clave corrupta sólo puede disminuir. Como resultado se mantiene que a lo sumo n/4 claves 166

están corruptas. Sin embargo, hay también n/4 de las claves que no están corruptas, y deben ser más grandes que todo elemento que de eliminó. Más aún, dado que las claves sólo se aumentan al corromperlas, el último y más grande elemento L que se eliminó debe exceder las claves originales de n/4 de los otros elementos que fueron eliminados. Dicho de otra forma, L divide los elementos en algún lugar entre 25%/75% y 75%/25%. Se particiona el conjunto utilizando L como pivote (paso de partición del algoritmo Quicksort) y se aplica el mismo algoritmo nuevamente a alguno de los dos conjuntos resultantes, cada uno con a lo sumo (3/4)n elementos. Dado que cada inserción y borrado se realiza en tiempo O(1) amortizado, el tiempo total determinista está acotado por un múltiplo de: T(n) = (5/4)n + (5/4)(3/4)n + (5/4)(3/4)²n + ... = 5n. El algoritmo final (en wikicode) tiene la siguiente apariencia: function softHeapSelect(a[1..n], k) if k = 1 then return minimum(a[1..n]) create(S) for i from 1 to n insert(S, a[i]) for i from 1 to n/4 x := findmin(S) delete(S, x) xIndex := partition(a, x) if k < xIndex softHeapSelect(a[1..xIndex-1], k) else softHeapSelect(a[xIndex..n], k-xIndex+1)

167

Estructura De Datos Wikipedia) 2m6y3m

Overview 26281t

More details 6y5l6z

Related Documents 3h463d

Estructura De Datos Wikipedia) 2m6y3m

Practica Estructura De Datos 1zh3c

Estructura De Datos Antologia 1n4850

Estructura De Datos 376b3d

Estructura De Datos 1 101m6w

Estructura De Datos 376b3d

More Documents from "Genaro Alberto Gómez Chi" 5h273x

4p345f

Texto Paralelo De Impacto Ambiental.docx 1j4r1s

4p345f

Cs411 Finalterm Subjective Solved By Arslan Arshad(zain Nasar) 2k633x

Confirmation Transcription- Tommy Flanagan 262k25

ing Microsoft Case 5g6p1w