PDF de programación - Otras estructuras de datos - Programación de Sistemas de Telecomunicación Informática

Otras estructuras de datos

Programación de Sistemas de Telecomunicación

Informática II

GSyC

Universidad Rey Juan Carlos

Noviembre 2017

GSyC - 2017

Otras estructuras de datos

1

c2017 Grupo de Sistemas y Comunicaciones.
Algunos derechos reservados.
Este trabajo se distribuye bajo la licencia
Creative Commons Attribution Share-Alike
disponible en http://creativecommons.org/licenses/by-sa/3.0/es

GSyC - 2017

Otras estructuras de datos

2

Contenidos

1 Árboles autoequilibrados

2 Pilas y Colas

3 Tabla Hash

4 Listas doblemente enlazadas, Listas enlazadas circulares

5 Biblioteca predefinida de contenedores de Ada 2005

6 Bibliografía

GSyC - 2017

Otras estructuras de datos

3

Árboles autoequilibrados

Contenidos

1 Árboles autoequilibrados

2 Pilas y Colas

3 Tabla Hash

4 Listas doblemente enlazadas, Listas enlazadas circulares

5 Biblioteca predefinida de contenedores de Ada 2005

6 Bibliografía

GSyC - 2017

Otras estructuras de datos

4

Rendimiento de la búsqueda en un ABB (I)

Árboles autoequilibrados

El rendimiento de las búsquedas (para insertar/extraer) en un
árbol de búsqueda binaria (ABB) depende de cuán equilibrada sea
su estructura
Y el equilibrio depende del orden de inserción de nuevos nodos y
del orden en el que se han ido produciendo las extracciones

Ejemplo:

, "66.209.92.150");
, "63.251.52.110");
, "213.238.60.19");
, "12.155.29.35 ");
, "206.220.43.92");
, "169.232.55.22");
, "66.77.124.26");
, "66.249.92.104");

Insertar("zappos.com"
Insertar("yelp.com"
Insertar("xing.com"
Insertar("wings.com"
Insertar("viacom.com"
Insertar("ucla.edu"
Insertar("nbc.com"
Insertar("google.com"
Insertar("facebook.com", "69.63.181.12");
Insertar("edi.com"
Insertar("cbs.com"
Insertar("bbva.es"

, "192.86.2.98");
, "198.99.118.37");
, "195.76.187.83");

GSyC - 2017

Otras estructuras de datos

5

Rendimiento de la búsqueda en un ABB (II)

Árboles autoequilibrados

Peor caso: árbol completamente desequilibrado

En el peor caso cada nodo tiene exactamente un enlace no
nulo, salvo un único nodo que tiene sus dos enlaces nulos
(nodo hoja).
En este caso el árbol tiene la estructura de una lista enlazada
y por tanto no se beneficia de la búsqueda binaria.

Ocurre cuando p.ej. insertamos los nodos siguiendo el orden
de la clave.

También los borrados pueden ocasionar desequilibrios en el
árbol.

GSyC - 2017

Otras estructuras de datos

6

Rendimiento de la búsqueda en un ABB (IV)

Árboles autoequilibrados

Mejor caso: árbol perfectamente equilibrado

Árbol perfectamente equilibrado de N nodos:

Todos los nodos hoja están a la misma distancia de la raíz:
log2N. Hay log2N nodos entre el nodo raíz y un nodo hoja
Todo nodo del árbol, o tiene dos hijos no nulos (nodo hoja), o
sus dos hijos son nulos

El coste de una búsqueda de un elemento no existente (para
extraer o insertar) es = log2N

Medimos el coste como el número de nodos del árbol que hay
que consultar

El coste de una búsqueda de un elemento que está en el árbol
(para extraer o insertar) es ≤ log2N

GSyC - 2017

Otras estructuras de datos

7

Rendimiento de la búsqueda en un ABB (III)

Árboles autoequilibrados

Caso promedio:

Si se insertan/borran elementos en un ABB de manera
aleatoria de forma que el orden de inserción/borrado NO se
corresponda con el orden de las claves, el árbol tiende a
permanecer en equilibrio.
El coste de una inserción o una extracción aleatorias en un
ABB en el que todas las inserciones y extracciones se han
realizado de manera aleatoria es O(2log2N)

O(2log2N) = aproximadamente 2log2N para N grandes

GSyC - 2017

Otras estructuras de datos

8

Árboles binarios autoequilibrados (I)

Árboles autoequilibrados

Los árboles binarios autoequilibrados son árboles de búsqueda
binaria que evitan el peor caso, manteniendo el árbol casi
perfectamente equilibrado.

La inserción y el borrado en los árboles autoequilibrados se
realiza de manera tal que no sólo se mantenga el orden de las
claves, sino también el equilibrio.

Lo hacen con independientemente del orden de
inserción/extracción, garantizando un tiempo de búsqueda
logarítmico.

GSyC - 2017

Otras estructuras de datos

9

Árboles binarios autoequilibrados (II)

Árboles autoequilibrados

Los árboles 2-3, los árboles rojo-negros y los árboles AVL son
árboles binarios autoequilibrados
Un árbol 2-3:

o está vacío
o es un 2-nodo, con una clave y dos enlaces a un subárbol 2-3
izquierdo con claves menores y a un subárbol 2-3 derecho con
claves mayores
o es un 3-nodo, con 2 claves y tres enlaces: a un subárbol 2-3
izquierdo con claves menores a las 2 del nodo, a un subárbol
2-3 central con claves entre las 2 del nodo y a un subárbol 2-3
derecho con claves mayores a las 2 del nodo

Los árboles rojo-negros son equivalentes a los árboles 2-3 pero
permiten una implementación más eficiente que éstos

Los árboles AVL fueron los primeros árboles binarios
autoequilibrados que se inventaron.

GSyC - 2017

Otras estructuras de datos

10

Pilas y Colas

Contenidos

1 Árboles autoequilibrados

2 Pilas y Colas

3 Tabla Hash

4 Listas doblemente enlazadas, Listas enlazadas circulares

5 Biblioteca predefinida de contenedores de Ada 2005

6 Bibliografía

GSyC - 2017

Otras estructuras de datos

11

Introducción

Pilas y Colas

La pila (stack) y la cola (queue) son estructuras de datos que
sirven para almacenar colecciones de elementos

Los elementos NO tienen una clave, como si ocurre en las
tablas de símbolos

En pilas y colas se pueden realizar dos operaciones básicas:

Insertar un elemento en la pila/cola
Extraer un elemento de la pila/cola

Pila y cola se diferencian en cómo se elige el elemento a
extraer.

En la tabla de símbolos se busca por clave el elemento a
insertar/extraer. En las pilas y colas NO

GSyC - 2017

Otras estructuras de datos

12

Pila (stack)

Pilas y Colas

Una pila es una colección en la que se pueden insertar y extraer
elementos.

2 operaciones básicas: Push, Pop

Push inserta un nuevo elemento en la pila
Pop extrae el último elemento que se insertó en la pila
La extracción sigue el orden LIFO (Last-In First-Out)

GSyC - 2017

Otras estructuras de datos

13

Casos de uso de las pilas

Pilas y Colas

Cada vez que un usuario selecciona un enlace en una página
Web que está mostrando el navegador, la página se inserta en
una pila de páginas Web visitadas.

Cada vez que pulsa el botón de volver atrás en el navegador
Web se extrae de la pila de páginas Web visitadas la última
que se insertó

Las llamadas a subprogramas también utilizan una pila:

para ir insertando la información local (parámetros, variables
locales) cada vez que se produce una nueva llamada a un
subprograma
para extraer la información local a cada subprograma cada vez
que retorna de una llamada

GSyC - 2017

Otras estructuras de datos

14

Implementación de la pila

Pilas y Colas

Implementación con Array

Problema: el Array tiene un tamaño máximo fijado de
antemano
Solución: cuando el Array se llena se copia a otro un poco más
grande.

Implementación con Lista enlazada

De manera muy similar a como implementamos la tabla de
símbolos con una lista enlazada:

No hay clave
Push Put de la tabla de símbolos (recuerda, insertaba por el
principio)
Pop: devuelve First y actualiza First a First.Next.

GSyC - 2017

Otras estructuras de datos

15

Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

16

My_Stack“facebook.com" Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

17

My_Stack“facebook.com"Stacks.Push (My_Stack, ASU.To_Unbounded_String (“google.com")); 1 Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

18

My_Stack“google.com"“facebook.com"Stacks.Push (My_Stack, ASU.To_Unbounded_String (“google.com")); 1P_Aux Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

19

My_Stack“google.com"“facebook.com"Stacks.Push (My_Stack, ASU.To_Unbounded_String (“google.com")); 1P_Aux Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

20

My_Stack“google.com"“facebook.com"P_AuxStacks.Push (My_Stack, ASU.To_Unbounded_String (“google.com")); 1 Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

21

My_Stack“google.com"“facebook.com"Stacks.Push (My_Stack, ASU.To_Unbounded_String (“www.urjc.es"));2 Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

22

My_Stack“www.urjc.es"“google.com"“facebook.com"Stacks.Push (My_Stack, ASU.To_Unbounded_String (“www.urjc.es"));2P_Aux Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

23

My_Stack“www.urjc.es"“google.com"“facebook.com"Stacks.Push (My_Stack, ASU.To_Unbounded_String (“www.urjc.es"));2P_Aux Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

24

My_Stack“www.urjc.es"“google.com"“facebook.com"Stacks.Push (My_Stack, ASU.To_Unbounded_String (“www.urjc.es"));2P_Aux Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

25

My_Stack“www.urjc.es"“google.com"“facebook.com"URL := Stacks.Pop (My_Stack);3URL? Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

26

My_Stack“www.urjc.es"“google.com"“facebook.com"URL := Stacks.Pop (My_Stack);3“www.urjc.es"URL Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

27

My_Stack“www.urjc.es"“google.com"“facebook.com"URL := Stacks.Pop (My_Stack);3URL“www.urjc.es"P_Aux Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

28

My_Stack“www.urjc.es"“google.com"“facebook.com"URL := Stacks.Pop (My_Stack);3URL“www.urjc.es"P_Aux Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

29

My_Stack“google.com"“facebook.com"URL := Stacks.Pop (My_Stack);3URL“www.urjc.es"P_Aux Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

30

My_Stack“google.com"“facebook.com"URL?URL := Stacks.Pop (My_Stack);4 Ejemplo

Pilas y Colas

GSyC - 2017

Otras estructuras de datos

31

My_Stack“google.com"“facebook.com"URL := Stacks.Pop (My_Stack);4URL“google.com