Algoritmos y Estructuras de Datos
Algoritmos y Estructuras de Datos
www: [Link]
Facultad de Ingenierı́a y Ciencias Hı́dricas
Universidad Nacional del Litoral [Link]
Centro de Investigación de Métodos Computacionales
[Link]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 2
Indice
3
INDICE / INDICE
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 4
INDICE / INDICE
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 5
INDICE / INDICE
3. Arboles 151
3.1. Nomenclatura básica de árboles . . . . . . . . . . . . . . . . 151
[Link].1. Altura de un nodo. . . . . . . . . . . 154
[Link].2. Profundidad de un nodo. Nivel. . . . . 154
[Link].3. Nodos hermanos . . . . . . . . . . . 154
3.2. Orden de los nodos . . . . . . . . . . . . . . . . . . . . . . . 154
3.2.1. Particionamiento del conjunto de nodos . . . . . . . . . 156
3.2.2. Listado de los nodos de un árbol . . . . . . . . . . . . 157
[Link]. Orden previo . . . . . . . . . . . . . . . . . . 157
[Link]. Orden posterior . . . . . . . . . . . . . . . . . 158
[Link]. Orden posterior y la notación polaca invertida 159
3.2.3. Notación Lisp para árboles . . . . . . . . . . . . . . . . 160
3.2.4. Reconstrucción del árbol a partir de sus órdenes . . . . 161
3.3. Operaciones con árboles . . . . . . . . . . . . . . . . . . . . 164
3.3.1. Algoritmos para listar nodos . . . . . . . . . . . . . . . 164
3.3.2. Inserción en árboles . . . . . . . . . . . . . . . . . . . 165
[Link]. Algoritmo para copiar árboles . . . . . . . . . 166
3.3.3. Supresión en árboles . . . . . . . . . . . . . . . . . . 169
3.3.4. Operaciones básicas sobre el tipo árbol . . . . . . . . . 170
3.4. Interfaz básica para árboles . . . . . . . . . . . . . . . . . . . 170
3.4.1. Listados en orden previo y posterior y notación Lisp . . 174
3.4.2. Funciones auxiliares para recursión y sobrecarga de
funciones . . . . . . . . . . . . . . . . . . . . . . . . . 175
3.4.3. Algoritmos de copia . . . . . . . . . . . . . . . . . . . 176
3.4.4. Algoritmo de poda . . . . . . . . . . . . . . . . . . . . 176
3.5. Implementación de la interfaz básica por punteros . . . . . . . 176
3.5.1. El tipo iterator . . . . . . . . . . . . . . . . . . . . . . 177
3.5.2. Las clases cell e iterator t . . . . . . . . . . . . . . . . 179
3.5.3. La clase tree . . . . . . . . . . . . . . . . . . . . . . . 183
3.6. Interfaz avanzada . . . . . . . . . . . . . . . . . . . . . . . . 186
3.6.1. Ejemplo de uso de la interfaz avanzada . . . . . . . . . 191
3.7. Tiempos de ejecución . . . . . . . . . . . . . . . . . . . . . . 194
3.8. Arboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . 195
3.8.1. Listados en orden simétrico . . . . . . . . . . . . . . . 195
3.8.2. Notación Lisp . . . . . . . . . . . . . . . . . . . . . . . 195
3.8.3. Árbol binario lleno . . . . . . . . . . . . . . . . . . . . 196
3.8.4. Operaciones básicas sobre árboles binarios . . . . . . 197
3.8.5. Interfaces e implementaciones . . . . . . . . . . . . . . 198
[Link]. Interfaz básica . . . . . . . . . . . . . . . . . 198
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 6
INDICE / INDICE
4. Conjuntos 249
4.1. Introducción a los conjuntos . . . . . . . . . . . . . . . . . . . 249
4.1.1. Notación de conjuntos . . . . . . . . . . . . . . . . . . 249
4.1.2. Interfaz básica para conjuntos . . . . . . . . . . . . . . 250
4.1.3. Análisis de flujo de datos . . . . . . . . . . . . . . . . . 252
4.2. Implementación por vectores de bits . . . . . . . . . . . . . . 259
4.2.1. Conjuntos universales que no son rangos contiguos de
enteros . . . . . . . . . . . . . . . . . . . . . . . . . . 260
4.2.2. Descripción del código . . . . . . . . . . . . . . . . . . 261
4.3. Implementación con listas . . . . . . . . . . . . . . . . . . . . 264
[Link]. Similaridad entre los TAD conjunto y corre-
spondencia . . . . . . . . . . . . . . . . . . . 264
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 7
INDICE / INDICE
5. Ordenamiento 315
5.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
5.1.1. Relaciones de orden débiles . . . . . . . . . . . . . . . 315
5.1.2. Signatura de las relaciones de orden. Predicados bina-
rios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 8
INDICE / INDICE
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 9
INDICE / INDICE
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 10
Sobre este libro:
Utilitarios usados: Todo este libro ha sido escrito con utilitarios de soft-
ware libre, de acuerdo a los lineamientos de la Free Software Founda-
tion/GNU Project ([Link] La mayorı́a de los utilitarios cor-
responden a un sistema Fedora release 27 (Twenty Seven) Kernel
4.14.16-300.fc27.x86 64.
11
INDICE / INDICE
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 12
Capı́tulo 1
Diseño y análisis de
algoritmos
13
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
T0 modifica O0 , O1 y O3 .
T1 modifica O4 y O5 .
T2 modifica O4 .
T3 modifica O2 y O6
T4 modifica O1 y O4 .
T5 modifica O4 y O7 .
T6 modifica O0 , O2 , O3 y O6 .
T7 modifica O1 , O7 , O8 .
T8 modifica O5 , O7 y O9 .
T9 modifica O3 .
T10 modifica O6 , O8 y O9 .
T11 modifica O9 .
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 14
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
Cada tarea debe estar en una y sólo una etapa. (De lo contrario la
tarea no se realizarı́a o se realizarı́a más de una vez, lo cual es re-
dundante. En el lenguaje de la teorı́a de conjuntos, estamos diciendo
que debemos particionar el conjunto de etapas en un cierto número
de subconjuntos “disjuntos”.)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 15
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
a b c d e f
a b a 0 1 1 1 1 0
b 1 0 0 1 0 0
c 1 0 0 1 1 1
f
c d 1 1 1 0 1 1
e 1 0 1 1 0 0
e
d f 0 0 1 1 0 0
G = {{a, b}, {a, c}, {a, d}, {a, e}, {b, d}, {c, d}, {c, e}, {c, f }, {d, e}, {d, f }, }
(1.1)
Para este ejemplo usaremos “grafos no orientados”, es decir que si el
vértice i está conectado con el j entonces el j está conectado con el i.
También existen “grafos orientados” donde las aristas se representan por
flechas.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 16
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
T T T
0 1 2
T T T
3 4 5
T T T
6 7 8
T T T
9 10 11
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 17
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
C4 C8
C3
C5
C7
C2
C10
C1 C9
C6
C4
C8
C3
C5
C7
C2
C10
C1 C9
C6
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 18
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
a b a b a b a b
coloracion= C0 C1 C2 C3
Para nc = 1 es trivial, hay una sola coloración donde todos los vértices
tienen el mismo color, es decir N (nc = 1, m) = 1 para cualquier m.
Consideremos ahora las coloraciones de nc = 2 colores, digamos rojo y
verde. Si hay un sólo vértice en el grafo, entonces hay sólo dos coloraciones
posibles: que el vértice sea rojo o verde. Si hay dos vértices, entonces pode-
mos tener 4 coloraciones rojo-rojo, rojo-verde, verde-rojo y verde-verde, es
decir N (2, 2) = 4 (ver figura 1.5. Nota: Para que los gráficos con colores
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 19
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
m =3
N=8
nc =2
a b c
m =2
N=4
nc =2 a b c
+ c a b c
a b
a b c
a b
a b + c
a b c
a b
a b c
a b c
a b c
N (nc , m) = nc N (nc , m − 1)
= n2c N (nc , m − 2)
.. (1.3)
.
= nm−1
c N (nc , 1)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 20
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
de manera que
N (nc , m) = nm
c (1.4)
Esto cierra con la última pregunta, ya que vemos que el número de pasos
para cada uno de los colores es finito, y hay a lo sumo m colores de manera
que el número total de posibles coloraciones a verificar es finito. Notar de
paso que esta forma de contar las coloraciones es también “constructiva”,
da un procedimiento para generar todas las coloraciones, si uno estuviera
decidido a implementar la estrategia de búsqueda exhaustiva.
a b c
a b c
a b c
a b c =
un solo color = =
a b c
a b c
a b c
a b c
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 21
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 22
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
a b c a b c a b c a b c a b c
a b c a b c a b c a b c a b c
a b c a b c a b c a b c
a b c
a b c a b c a b c a b c
a b c a b c a b c a b c
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 23
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
23 2 + = 6
Número de Número de
Número de
coloraciones
coloraciones
(1.7)
coloraciones
= con + con
con nc = 2 o
exactamente exactamente
menos
nc = 1 nc = 2
23 = 2 . 1 + 2 . 3
2! 2! (1.9)
23 = . Nd (1, 3) + . Nd (2, 3)
1! 0!
1!
15 = Nd (1, 5)
0!
2! 2!
25 = Nd (1, 5) + Nd (2, 5)
1! 0!
3! 3! 3!
35 = Nd (1, 5) + Nd (2, 5) + Nd (3, 5)
2! 1! 0!
4! 4! 4! 4!
45 = Nd (1, 5) + Nd (2, 5) + Nd (3, 5) + Nd (4, 5)
3! 2! 1! 0!
(1.10)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 24
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
o sea
1 = Nd (1, v)
32 = 2 Nd (1, 5) + 2 Nd (2, 5)
243 = 3 Nd (1, 5) + 6 Nd (2, 5) + 6 Nd (3, 5)
1024 = 4 Nd (1, 5) + 12 Nd (2, 5) + 24 Nd (3, 5) + 24 Nd (4, 5)
(1.11)
Notemos que de la segunda ecuación puede despejarse fácilmente Nd (2, 5)
que resulta ser 15. De la tercera se puede despejar Nd (3, 5) ya que conoce-
mos Nd (1, 5) y Nd (2, 5) y resulta ser Nd (3, 5) = 25 y ası́ siguiendo resulta
ser
Nd (1, 5) = 1
Nd (2, 5) = 15
Nd (3, 5) = 25 (1.12)
Nd (4, 5) = 10
Nd (5, 5) = 1
de manera que el número total de coloraciones esencialmente diferentes es
Es muy fácil escribir un programa (en C++, por ejemplo) para encontrar el
número total de coloraciones esencialmente diferentes para un dado número
de vértices, obteniéndose una tabla como la 1.1
coloraciones
m coloraciones
diferentes
1 1 1
2 4 2
3 27 5
4 256 15
5 3125 52
6 46656 203
7 823543 877
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 25
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
Sin embargo, si bien esto significa una gran mejora con respecto a mm , el
tiempo para colorear un grafo de 20 vértices se reduce del tiempo calculado
en (1.6) a sólo 99 dı́as. Está claro que todavı́a resulta ser excesivo para un
uso práctico.
Una implementación en C++ del algoritmo de búsqueda exhaustiva
puede encontrarse en el código que se distribuye con este apunte en
aedsrc/[Link]. La coloración óptima del grafo se encuentra después
de hacer 1.429.561 evaluaciones en 0.4 secs. Notar que el número de eval-
uaciones baja notablemente con respecto a la estimación mm+2 ≈ 9×1012
ya que se encuentra una coloración admisible para nc = 4 con lo cual no es
necesario llegar hasta nc = m. De todas formas incluso si tomáramos como
cota inferior para evaluar los tiempos de ejecución el caso en que debierámos
evaluar al menos todas las coloraciones de 2 colores, entonces tendrı́amos
al menos un tiempo de ejecución que crece como 2m evaluaciones. Incluso
con este “piso” para el número de evaluaciones, el tiempo de cálculo serı́a
de una hora para m = 33.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 26
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
a e b
d
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 27
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
c c
a e b a e b
d d
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 28
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
T T T
0 1 2
T T4 T
3 5
T T T
6 7 8
T T T
9 10 11
Una vez que tenemos una versión abstracta (matemática) del modelo o
algoritmo podemos empezar a implementarlo para llegar a un programa re-
al que resuelve el problema. Este proceso puede llevarse a cabo en varias
etapas empezando por una descripción muy general en forma de senten-
cias vagas, llamado “seudo-código”, como “elegir un vértice no coloreado”.
A veces es común incluir este seudo-código en forma de comentarios segui-
dos por puntos suspensivos que indican que falta completar esa parte del
programa.
Lo ideal es que estas sentencias sean suficientemente claras como para
no dejar dudas de cual es la tarea a realizar, pero también lo suficientemente
generales como para no tener que entrar en detalles y poder diseñar rápi-
damente una versión básica del código. Luego en un paso de “refinamien-
to” posterior estas sentencias en seudo-código son refinadas en tareas más
pequeñas, las cuales pueden ser descriptas parte en lı́neas de seudo-códi-
go ellas mismas y parte en sentencias válidas del lenguaje, hasta que final-
mente terminamos con un código que puede ser compilado y linkeditado en
un programa.
Tomemos como ejemplo el algoritmo heurı́stico descripto previamente
en §1.1.8. La rutina greedyc mostrada en el código 1.1 (archivo [Link])
toma como argumentos un grafo G, el conjunto de vértices no coloreados
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 29
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 30
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
todos toma el valor no_col.end(), con lo cual finaliza al lazo. Dentro del lazo
faltan implementar 3 porciones de código. La condición del if de las lı́neas
10-11, el código para marcar al vértice como coloreado en la lı́nea 13 y para
agregarlo a nuevo_color en la lı́nea 15.
Vamos ahora a refinar el algoritmo anterior, expandiendo ahora más aún
la expresión condicional del if. Para verificar si *q es adyacente a algún
vértice de nuevo_color debemos recorrer todos los nodos de nuevo_color
y verificar si hay alguna arista entre los mismos y *q. Para esto hace-
mos un lazo, definiendo una variable adyacente (ver código 1.2, archivo
[Link]). Al llegar al comienzo del condicional en la lı́nea 10 la vari-
able adyacente tiene el valor apropiado. Notar que si se detecta que uno de
los vértices de nuevo_color es adyacente a *q , entonces no es necesario
seguir con el lazo, por eso el break de la lı́nea 15. Además hemos imple-
mentado las lı́neas 13 y lı́neas 15 del código 1.1, resultando en las lı́neas
lı́neas 20 y lı́neas 22 del código 1.2. La lı́nea 20 simplemente registra el nue-
vo color asignado a la tabla tabla_color y la lı́nea 22 inserta el vértice que
se termina de colorear *q al conjunto nuevo_color. Notar que deberı́amos
eliminar los vértices que coloreamos de no_col pero esto no lo podemos
hacer dentro del lazo de las lı́neas 9-24 del código 1.2, ya que dentro del
mismo se itera sobre no_col. Modificar no_col convertirı́a en inválido el it-
erador q y por lo tanto después no se podrı́a aplicar el operador ++ a q en la
lı́nea 9.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 31
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
[Link](j,k) = 1;
if () {
// no estan conectados
// ...
}
1. class graph {
2. private:
3. const int nv;
4. vector<int> g;
5. public:
6. // Constructor a partir del numero de vertices
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 32
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 33
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
Ahora falta definir el código exterior que iterará los colores, llamando a
greedyc. Un primer esbozo puede observarse en el código 1.5. La rutina
greedy toma como argumentos de entrada el grafo a colorear G, el número
de vértices nv y devuelve la coloración en tabla_color. Internamente ini-
cializa el conjunto de vértices no coloreados insertando todos los vértices
del grafo en la lı́nea 8. A continuación entra en un lazo infinito, del cual sólo
saldrá cuando todos los vértices estén coloreados, y por lo tanto no_col sea
vacı́o, lo cual todavı́a debemos implementar en la lı́nea 19. (Notemos que es
válido utilizar un lazo infinito ya que hemos garantizado que el algoritmo se
ejecuta a lo sumo un número finito de veces, más precisamente a lo sumo
m veces. ) Dentro del lazo, se determina el conjunto de vértices al cual se
asignará el nuevo color llamando a greedyc(...) (lı́nea 13). Luego debe-
mos sacar los vértices asignados al nuevo color de no_col y, después de
verificar la condición de fin del algoritmo, incrementar el número de color.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 34
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 35
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.1. Conceptos básicos de algoritmos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 36
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.2. Tipos abstractos de datos
Se separan dos capas de código bien diferentes, por una parte el al-
goritmo que escribe el programador, y por otro las rutinas de acceso a
las diferentes estructuras.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 37
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.2. Tipos abstractos de datos
operaciones abstractas
del TAD
abstracción
interfase
implementación
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 38
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.2. Tipos abstractos de datos
1. template<class T>
2. class set {
3. public:
4. class iterator { /* . . . */ };
5. void insert(T x);
6. void erase(iterator p);
7. void erase(T x);
8. iterator find(T x);
9. iterator begin();
10. iterator end();
11. };
if([Link](x)==[Link]()) {
// `x' no esta en `s'
// ...
}
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 39
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.2. Tipos abstractos de datos
set A,B,C;
// Pone elementos en A y B
// ...
[Link]([Link](),[Link]());
[Link]([Link](),[Link]());
Tı́picamente:
• C =A∪B
set_union([Link](),[Link](),[Link](),[Link](),
inserter(c,[Link]()));
• C =A−B
set_difference([Link](),[Link](),[Link](),[Link](),
inserter(c,[Link]()));
• C =A∩B
set_intersection([Link](),[Link](),[Link](),[Link](),
inserter(c,[Link]()));
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 40
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 41
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
En este libro nos concentraremos en los dos últimos puntos de esta lista.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 42
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
la zona media del arreglo, de manera que una ecuación como la (1.16) será
válida (en promedio). Cuando sea necesario llamaremos Tprom (n) al prome-
dio de los tiempos de ejecución de un dado algoritmo sobre un “ensamble”
de posibles entradas y por Tpeor (n) el peor de todos sobre el ensamble.
Entonces, para el caso de buscar la numeración de un arreglo tenemos
T (n) = cj
Tpeor (n) = cn (1.17)
n
Tprom (n) = c
2
En estas expresiones c puede tomarse como el tiempo necesario para eje-
cutar una vez el cuerpo del lazo en la rutina search(...). Notar que esta
constante c, si la medimos en segundos, puede depender fuertemente de los
ı́tems considerados en los dos primeros puntos de la lista anterior. Por eso,
preferimos dejar la constante sin especificar en forma absoluta, es decir que
de alguna forma estamos evaluando el tiempo de ejecución en términos de
“unidades de trabajo”, donde una unidad de trabajo c es el tiempo necesario
para ejecutar una vez el lazo.
En general, determinar analı́ticamente el tiempo de ejecución de un al-
goritmo puede ser una tarea intelectual ardua. Muchas veces, encontrar el
Tpeor (n) es una tarea relativamente más fácil. Determinar el Tprom (n) puede
a veces ser más fácil y otras veces más difı́cil.
n ≥ 3, (1.19)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 43
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
entonces
n − 1 ≥ 2,
(n − 1)2 ≥ 4,
n2 − 2n + 1 ≥ 4, (1.20)
2
n ≥ 3 + 2n,
3 + 2n + n2 ≤ 2n2 .
Pero
3 + 2n + n2 = (n + 1)2 + 2, (1.21)
y por lo tanto
(n + 1)2 ≤ (n + 1)2 + 2 ≤ 2n2 , (1.22)
200
180
T(n) 160
140
2
120 2n
c
100
80 n 2
0 (n+1)
60
40
20
0
1 2 3 4 5 6 7 8 9 n 10
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 44
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
entonces vemos que T1 (n) coincide con la función T (n) = (n + 1)2 estu-
diada en el ejemplo 1.1. Por lo tanto, como sólo difieren en un número finito
de puntos (los valores de n < 10) las dos son equivalentes y por lo tanto
T1 (n) = O(n2 ) también.
Demostración: Esto puede verse ya que si T (n) < 2n2 para n ≥ 3 (como
se vio en el ejemplo citado), entonces T1 (n) < 2n2 para n > n00 = 10.
1.3.4. Transitividad
La propiedad O( ) es transitiva, es decir si T (n) = O(f (n)) y f (n) =
O(g(n)) entonces T (n) = O(g(n)).
Demostración: si T (n) ≤ cf (n) para n ≥ n0 y f (n) ≤ c0 g(n) para n ≥ n00 ,
entonces T (n) ≤ c00 g(n) para n ≥ n000 , donde c00 = cc0 y n000 = max(n0 , n00 ).
En cierta forma, O(...) representa una relación de orden entre las funciones
(como “<” entre los números reales).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 45
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
si T (n) = 2n3 + 3n5 , entonces puede verse fácilmente que n3 = O(n5 ) por
lo tanto, T (n) = O(n5 ).
Demostración: Si f (n) ≤ cg(n) para n ≥ n0 entonces a f (n) + b g(n) ≤
c0 g(n) para n ≥ n0 con c0 = ac + b.
Nota: Pero la regla de la suma debe aplicarse un número constante de veces,
si no, por ejemplo, consideremos una expresión como
Los logaritmos en diferente base son equivalentes entre sı́ por la bien
conocida relación
logb n = logb a loga n, (1.28)
de manera que en muchas expresiones con logaritmos no es impor-
tante la base utilizada. En computación cientı́fica es muy común que
aparezcan expresiones con logaritmos en base 2.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 46
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
Las potencias nα (con α > 0) se comparan entre sı́ según sus expo-
nentes, es decir nα = O(nβ ) si α ≤ β . Por ejemplo, n2 = O(n3 ),
1 2
n /2 = O(n /3 ).
T(n)
Figura 1.14: Decir que T (n) = O(f1 (n)) es “más fuerte” que T (n) =
O(f2 (n)) o T (n) = O(f3 (n))
Ejemplo 1.3: Para T (n) = (n + 1)2 entonces también podemos decir que
T (n) = O(n3 ) ya que, como vimos antes T (n) = O(n2 ) y n2 = O(n3 ) de
manera que por la transitividad (ver §1.3.4) T (n) = O(n3 ), pero decir que
T (n) = O(n2 ) es una aseveración “más fuerte” del tiempo de ejecución ya
que n2 < n3 . En general (ver figura 1.14) si podemos tomar varias funciones
f1 (n), f2 (n), f3 (n) entonces debemos tomar la “menor” de todas. Ası́, si
bien podemos decir que T (n) = O(nα ) para cualquier α ≥ 2 la más fuerte
de todas es para T (n) = O(n2 ). Por otra parte puede verse que T (n) 6=
O(nα ) para α < 2. Razonemos por el absurdo. Si, por ejemplo, fuera cierto
que T (n) = O(n) entonces deberı́an existir c, n0 > 0 tales que T (n) =
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 47
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
(n + 1)2
→ ∞, para n → ∞. (1.30)
n
Esta demostración puede extenderse fácilmente para cualquier α < 2.
1.3.8. Equivalencia
Si dos funciones f y g satisfacen que f (n) = O(g(n)) y g(n) = O(f (n))
entonces decimos que “sus tasas de crecimiento son equivalentes” lo cual
denotamos por
f ∼g (1.31)
Ası́, en el ejemplo anterior 1.3 se puede demostrar ver que n2 = O((n+1)2 )
por lo que
T (n) = (n + 1)2 ∼ n2 (1.32)
n! = O(nn ) (1.34)
y
an = O(n!), (1.35)
lo cual justifica la ubicación del factorial en la tabla (1.3.7).
Demostración: La primera relación (1.34) se desprende fácilmente de
1
aplicar la aproximación de Stirling y del hecho que n /2 e−n → 0 para n → ∞.
La segunda relación (1.35) se deduce de
n n
1 1
nn+ /2 e−n = an n /2 (1.36)
ae
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 48
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
con lo cual
1 1/
nn+ /2 e−n ≥ n02 an (1.39)
y por lo tanto
−1/2 n+1/2 −n
an ≤ n0 n e (1.40)
entonces
1
an = O(nn+ /2 e−n ) = O(n!) (1.41)
−1/
con c = n0 2 .
Ejemplo 1.4: Una de las ventajas de la notación asintótica es la gran sim-
plificación que se obtiene en las expresiones para los tiempos de ejecución
de los programas. Por ejemplo, si
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 49
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
n T (n) [segundos]
300 0.2
600 1.2
1000 4.8
1500 14.5
3000 104.0
1000
~n4 ~n3
~n2
100
10
T(n) ~n
0.1
100 1000 10000
300 600 1500 3000
n
Figura 1.15: Determinación experimental del tiempo de ejecución del algorit-
mo ávido de coloración de la sección §1.1.8
Graficando los valores en ejes logarı́tmicos (es decir, graficar log T (n)
en función de log n) obtenemos un gráfico como el de la figura 1.15. La util-
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 50
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
idad de tales ejes es que las funciones de tipo potencia ∝ nα resultan ser
rectas cuya pendiente es proporcional a α. Además curvas que difieren en
una constante multiplicativa resultan ser simplemente desplazadas según la
dirección vertical. Pero entonces si un programa tiene un comportamiento
T (n) = O(nα ) pero no conocemos α, basta con graficar su tiempo de eje-
cución en ejes logarı́tmicos junto con varias funciones nα y buscar cuál de
ellas es paralela a la de T (n). En el ejemplo de la figura vemos que T (n)
resulta ser perfectamente paralela a n3 confirmando nuestra estimación de
la sección §1.1.10.
En casos donde el tiempo de ejecución es exponencial, es decir ∼ an
pueden ser preferibles ejes semi-logarı́tmicos, es decir, graficar log T (n) en
función de n (y no en función de log n como en los logarı́tmicos) ya que en
estos gráficos las exponenciales son rectas, con pendiente log a.
Si no tenemos idea de que tipo de tasa de crecimiento puede tener un
programa, podemos proceder en forma incremental. Primero probar con un
gráfico logarı́tmico, si la curva resulta ser una recta, entonces es una poten-
cia y determinando la pendiente de la recta determinamos completamente
la tasa de crecimiento. Si la función no aparece como una recta y tiende a
acelerarse cada vez más, de manera que crece más que cualquier potencia,
entonces podemos probar con las exponenciales, determinando eventual-
mente la pendiente correspondiente. Finalmente, si crece todavı́a más que
las exponenciales, entonces puede ser del tipo n! o nn . En este caso pueden
intentarse una serie de procedimientos para refinar la estimación, pero debe-
mos notar que en muchos casos basta con notar que la tasa de crecimiento
es mayor que cualquier exponencial para calificar al algoritmo.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 51
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
1.3.13. Problemas P y NP
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 52
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.3. Tiempo de ejecución de un programa
poner los objetos en un vector y ordenarlo, ya que una vez ordenado basta
con tomar el elemento de la posición media. De manera que si tenemos un
cierto algoritmo con una complejidad algorı́tmica para el ordenamiento, au-
tomáticamente tenemos una cota superior para el problema de la mediana.
Se dice que un problema es “NP-completo” (NPC) si cualquier problema de
NP se puede reducir a ese problema. Esto quiere decir, que los problemas
de NPC son los candidatos a tener la más alta complejidad algorı́timica de
NP. Se ha demostrado que varios problemas pertenecen a NPC, entre el-
los el Problema del Agente Viajero (1.1). Si se puede demostrar que algún
problema de NPC tiene complejidad algorı́tmica no-polinomial (y por lo tan-
to todos los problemas de NPC) entonces P 6= N P . Por otra parte, si se
encuentra algún algoritmo de tiempo polinomial para un problema de NPC
entonces todos los problemas de NPC (y por lo tanto de NP) serán P, es de-
cir P = N P . De aquı́ la famosa forma de poner la pregunta del millón que
es: ¿“Es P=NP”?.
ne
s= (1.46)
m(m − 1)/2
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 53
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
1.4.1. Bloques if
if(<cond>) {
<body>
}
Notar que Tcond no está afectado por P ya que la condición se evalúa siem-
pre. En el caso de que tenga un bloque else, entonces
if(<cond>) {
<body-true>
} else {
<body-false>
}
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 54
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
podemos considerar,
Las dos cotas para Tpeor son válidas, la que usa “max” es más precisa.
1.4.2. Lazos
El caso más simple es cuando el lazo se ejecuta un número fijo de veces,
y el cuerpo del lazo tiene un tiempo de ejecución constante,
donde
N
X −1
T = Tini + (Tbody,i + Tinc + Tstop ). (1.51)
i=0
Algunas veces es difı́cil calcular una expresión analı́tica para tales sumas. Si
podemos determinar una cierta tasa de crecimiento para todos los términos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 55
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
entonces,
N −1
T ≤ N max(Tbody,i + Tinc + Tstop = O(N f (n)) (1.53)
i=1
while (<cond>) {
<body>
}
En este caso debemos determinar también el número de veces que se eje-
cutará el lazo.
Ejemplo 1.5: Calcularemos el tiempo de ejecución del algoritmo de orde-
namiento por el “método de la burbuja” (“bubble-sort” ). Si bien a esta altura
no es necesario saber exactamente como funciona el método, daremos una
breve descripción del mismo. La función bubble_sort(...) toma como ar-
gumento un vector de enteros y los ordena de menor a mayor. En la ejecu-
ción del lazo de las lı́neas 6–16 para j=0 el menor elemento de todos es
insertado en a[0] mediante una serie de intercambios. A partir de ahı́ a[0]
no es tocado más. Para j=1 el mismo procedimiento es aplicado al rango de
ı́ndices que va desde j=1 hasta j=n-1, donde n es el número de elementos
en el vector, de manera que después de la ejecución del lazo para j=1 el se-
gundo elemento menor es insertado en a[1] y ası́ siguiendo hasta que todos
los elementos terminan en la posición que les corresponde en el elemento
ordenado.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 56
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
17. }
Tini = c4 ,
Tstop = c5 ,
(1.55)
Tinc = c6 ,
Tbody,j = c3 + (n − j − 1) c2 .
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 57
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
podemos aplicar (1.50), sino que debemos escribir explı́citamente una suma
n−2
X
T (lı́neas 6–16) = c4 + (c5 + c6 + c3 + (n − j − 1)c2 ) (1.56)
j=0
n−2
X
T (lı́neas 6–16) = c4 + (n − 1)(c3 + c5 + c6 ) + c2 (n − j − 1) (1.57)
j=0
1 1
1
n/2
=
n
j=1 2 3 4
n 2 /2
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 58
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
n(n − 1)
T (bubble sort) = c4 + c7 + (n − 1)(c5 + c6 ) + c2 (1.62)
2
Ahora vamos a simplificar esta expresión utilizando los conceptos de no-
tación asintótica. Primero notemos que
n2
T (bubble sort) ≤ (c4 + c7 ) + n(c5 + c6 ) + c2 (1.63)
2
y que los tres términos involucrados son O(1), O(n) y O(n2 ) respectiva-
mente. De manera que, aplicando la regla de la suma, tenemos que
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 59
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
y, en general
n n
np+1
X Z
p
j ≈ j p dj = = O(np+1 ) (1.67)
0 p+1
j=1
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 60
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
S3
main( )
S2
sub1( ) sub2( ) sub3( )
S1
sub4( ) sub5( ) sub1( )
S0
sub4( )
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 61
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
está fuera del arreglo) hubiera un ∞. La rutina utiliza una rutina auxiliar
bsearch2(a,k,j1,j2) la cual busca el elemento en un rango [j1 , j2 ) (que
significa j1 ≤ j < j2 ). Este rango debe ser un rango válido en a, es decir
j1 < j2 , 0 ≤ j1 < n, 1 ≤ j2 ≤ n y a[j1 ] ≤ k < a[j2 ]. Notar que j2 puede
tomar la posición “ficticia” n, pero j1 no.
La rutina bsearch() determina primero un rango válido inicial. Si k ≥ a0 ,
entonces [0, n) es un rango válido y llama a bsearch() mientras que si no
la posición j = 0 es la solución al problema.
La rutina bsearch2 opera recursivamente calculando un punto medio p y
llamando nuevamente a bsearch2(), ya sea con el intervalo [j1 , p) o [p, j2 ).
En cada paso el tamaño del rango se reduce en un factor cercano a 2, de
manera que en un cierto número de pasos el tamaño del intervalo se reduce
a 1, en cuyo caso termina la recursión.
Consideremos ahora el tiempo de ejecución de la función bsearch2()
como función del número de elementos m = j2 − j1 en el intervalo. Si la
condición de la lı́nea 2 da verdadero entonces m = 1 y el tiempo es una
constante c. Caso contrario, se realiza un número constante de operaciones
d más una llamada a bsearch2() (en la lı́nea 7 ó la 8) con un rango de lon-
gitud menor. Por simplicidad asumiremos que m es una potencia de 2, de
manera que puede verse que el nuevo intervalo es de longitud m/2. Resum-
iendo (
c ; si m = 1;
T (m) = (1.68)
d + T (m/2) ; si m > 1;
Ahora, aplicando recursivamente esta expresión, tenemos que
T (2) = d + T (1) = d + c
T (4) = d + T (2) = 2d + c
T (8) = d + T (4) = 3d + c (1.69)
..
.
T (2p ) = d + T (2p−1 ) = pd + c
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 62
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 63
C AP ÍTULO 1. D ISE ÑO Y AN ÁLISIS DE ALGORITMOS / Sección 1.4. Conteo de operaciones para el cálculo del tiempo de ejecución
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 64
Capı́tulo 2
65
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 66
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
L = (1, 3, 5, 7)
suprime elemento en la posición 2 (2.4)
→ L = (1, 3, 7)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 67
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
1. class iterator-t { /* . . . */ };
2.
3. class list {
4. private:
5. // . . .
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 68
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
6. public:
7. // . . .
8. iterator-t insert(iterator-t p,elem-t x);
9. iterator-t erase(iterator-t p);
10. elem-t & retrieve(iterator-t p);
11. iterator-t next(iterator-t p);
12. iterator-t begin();
13. iterator-t end();
14. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 69
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
1. iterator_t p,q,r;
2. list L;
3. elem_t x,y,z;
4. //...
5. // p es una posicion dereferenciable
6. q = [Link](p);
7. r = [Link]();
8. [Link](p);
9. x = *p; // incorrecto
10. y = *q; // incorrecto
11. [Link](r,z); // incorrecto
. Asignar:
p = [Link]();
q = [Link]();
. Avanzar:
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 70
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
q = [Link](p);
. Acceder al elemento:
x = [Link](p);
[Link](q) = y;
. Copiar:
q = p;
. Comparar: Notar que sólo se puede comparar por igualdad o
desigualdad, no por operadores de comparación, como < ó >.
q == p
r != [Link]();
Sin embargo, si min operara sobre estructuras más complejas serı́a deseable
que retornara directamente un objeto modificable, es decir que pudiéramos
hacer
1. min(v,n) = 2*min(v,n);
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 71
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
2. int x = v[0];
3. int jmin = 0;
4. int n=[Link]();
5. for (int k=1; k<n; k++) {
6. if (v[k]<x) {
7. jmin = k;
8. x = v[jmin];
9. }
10. }
11. return &v[jmin];
12. }
13.
14. void print(vector<int> &v) {
15. cout << "Vector: (";
16. for (auto x : v) cout << x << " ";
17. cout << "), valor minimo: " << *min(v) << endl;
18. }
19.
20. int main() {
21. vector<int> v={6,5,1,4,2,3};
22. print(v);
23. int n=[Link]();
24. for (int j=0; j<[Link](); j++) {
25. *min(v) = 2* (*min(v));
26. print(v);
27. }
28. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 72
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
C++ permite retornar directamente referencias (int &, por ejemplo) a los
elementos, de manera que no hace falta despues dereferenciarlos como en
la lı́nea 25. El mismo program usando referencias puede verse en el códi-
go 2.3. El método val=retrieve(p) en la interfaz presentada para listas es
un ejemplo. Esta técnica es usada frecuentemente en las STL.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 73
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
eliminar
L=( 1 3 2 5 6 3 8 2 6 3 )
p q
eliminar
L=( 1 3 2 5 6 8 2 6 )
q
p
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 74
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 75
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
ya verificado
p
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 76
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
Inicialmente p,q están en los comienzos de las listas y suma=0, que cier-
tamente cumple con las condiciones anteriores. Después de una serie de
pasos, se puede llegar a un estado como el mostrado en la figura 2.3. Ten-
emos (p->1,q->5,suma=4).
Para avanzar las posiciones comparamos el valor actual de suma con
[Link](q) y seguimos las siguientes reglas,
Mientras tanto, en todo momento antes de avanzar una posición hay que
verificar de mantener la validez de las mismas. El lazo termina cuando alguna
de las listas se termina. El programa debe retornar verdadero si al salir del
lazo ambas posiciones están al final de sus respectivas listas y suma==0.
Partiendo del estado de la figura 2.3, tenemos los siguientes pasos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 77
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
9. suma=0;
10. q = [Link](q);
11. }
12. else if (p==[Link]()) break;
13. else if (suma<[Link](q)) {
14. suma += [Link](p);
15. p = [Link](p);
16. }
17. else return false;
18. }
19. return suma==0 && p==[Link]() && q==[Link]();
20. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 78
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
elemento 0
elemento 1
elemento 2
.
.
.
.
MAX_SIZE
elemento n−2
elemento n−1
end() n
.
.
.
.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 79
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
[Link](p,x)
a a
. .
. .
. .
. .
p−1 d p−1 d
p e p x
p+1 f p+1 e
p+2 g p+2 f
p+3 g
z
end() z
end()
1. #include <iostream>
2. #include <aedsrc/lista.h>
3. #include <cstdlib>
4.
5. using namespace std;
6. using namespace aed;
7.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 80
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
8. int list::MAX-SIZE=100;
9.
10. list::list() : elems(new elem-t[MAX-SIZE]),
11. size(0) { }
12.
13. list::˜list() { delete[ ] elems; }
14.
15. elem-t &list::retrieve(iterator-t p) {
16. if (p<0 | | p>=size) {
17. cout << "p: mala posicion.\n";
18. abort();
19. }
20. return elems[p];
21. }
22.
23.
24. iterator-t list::begin() { return 0; }
25.
26. iterator-t list::end() { return size; }
27.
28. iterator-t list::next(iterator-t p) {
29. if (p<0 | | p>=size) {
30. cout << "p: mala posicion.\n";
31. abort();
32. }
33. return p+1;
34. }
35.
36. iterator-t list::prev(iterator-t p) {
37. if (p<=0 | | p>size) {
38. cout << "p: mala posicion.\n";
39. abort();
40. }
41. return p-1;
42. }
43.
44. iterator-t list::insert(iterator-t p,elem-t k) {
45. if (size>=MAX-SIZE) {
46. cout << "La lista esta llena.\n";
47. abort();
48. }
49. if (p<0 | | p>size) {
50. cout << "Insertando en posicion invalida.\n";
51. abort();
52. }
53. for (int j=size; j>p; j--) elems[j] = elems[j-1];
54. elems[p] = k;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 81
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
55. size++;
56. return p;
57. }
58.
59. iterator-t list::erase(iterator-t p) {
60. if (p<0 | | p>=size) {
61. cout << "p: posicion invalida.\n";
62. abort();
63. }
64. for (int j=p; j<size-1; j++) elems[j] = elems[j+1];
65. size--;
66. return p;
67. }
68.
69. iterator-t list::erase(iterator-t p,iterator-t q) {
70. if (p<0 | | p>=size) {
71. cout << "p: posicion invalida.\n";
72. abort();
73. }
74. if (q<0 | | q>size) {
75. cout << "q: posicion invalida.\n";
76. abort();
77. }
78. if (p>q) {
79. cout << "p debe estar antes de q\n";
80. abort();
81. }
82. if (p==q) return p;
83. int shift = q-p;
84. for (int j=p; j<size-shift; j++)
85. elems[j] = elems[j+shift];
86. size -= shift;
87. return p;
88. }
89.
90. void list::clear() { erase(begin(),end()); }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 82
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
via un typedef. Los únicos campos datos en la clase list son un puntero
a enteros elems y un entero size que mantiene la longitud de la lista. Por
simplicidad haremos que el vector subyacente elems tenga siempre el mis-
mo tamaño. Esta cantidad está guardada en la variable estática de la clase
MAX_SIZE. Recordemos que cuando una variable es declarada estática den-
tro de una clase, podemos pensar que en realidad es una constante dentro
de la clase, es decir que no hay una copia de ella en cada instancia de la
clase (es decir, en cada objeto). Estos miembros de la clase, que son datos,
están en la parte privada, ya que forman parte de la implementación de la
clase, y no de la interfaz, de manera que un usuario de la clase no debe tener
acceso a ellos.
Los métodos públicos de la clase están en las lı́neas lı́neas 9–19.
Además de los descriptos en la sección §2.1.3 (código 2.1) hemos agre-
gado el constructor y el destructor y algunos métodos que son variantes de
erase() como el erase(p,q) de un rango (lı́nea 13) y clear() que equivale
a erase(begin(),end()), es decir que borra todos los elementos de la lista.
También hemos introducido prev() que es similar a next() pero retorna el
antecesor, no el sucesor y un método básico de impresión print().
En la implementación (código 2.7), vemos que el constructor inicializa las
variables size y aloca el vector elems con new[]. El destructor desaloca el
espacio utilizado con delete[]. Notemos que la inicialización se realiza en la
“lista de inicialización” del constructor. Los métodos retrieve, next y prev
son triviales, simplemente retornan el elemento correspondiente del vector
o incrementan apropiadamente la posición, usando aritmética de enteros.
Notar que se verifica primero que la posición sea válida para la operación
correspondiente. En retrieve(), después de verificar que la posición es
válida para insertar (notar que en el test de la lı́nea 49 da error si p==size),
el elemento es retornado usando la indexación normal de arreglos a través
de []. El método insert(), después de verificar la validez de la posición
(notar que p==size no da error en este caso), corre todos los elementos
después de p en la lı́nea 53, inserta el elemento, e incrementa el contador
size. erase() es similar.
erase(p,q) verifica primero la validez del rango a eliminar. Ambas posi-
ciones deben ser válidas, incluyendo end() y p debe preceder a q (también
pueden ser iguales, en cuyo caso erase(p,q) no hace nada). shift es el
número de elementos a eliminar, y por lo tanto también el desplazamien-
to que debe aplicarse a cada elemento posterior a q. Notar que uno podrı́a
pensar en implementar erase(p,q) en forma “genérica”
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 83
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
Este código es genérico, ya que en principio serı́a válido para cualquier im-
plementación de listas que siga la interfaz código 2.1. Sin embargo, hay un
error en esta versión: después de ejecutar el primer erase(p) la posición
q deja de ser válida. Además, en esta implementación con arreglos hay ra-
zones de eficiencia para no hacerlo en forma genérica (esto se verá en de-
talle luego). clear() simplemente asigna a size 0, de esta forma es O(1).
La alternativa “genérica” (erase(begin(),end())), serı́a O(n).
Otro ejemplo de código genérico es purge. Por supuesto, la mayorı́a de
las funciones sobre listas que no pertenecen a la clase, son en principio
genéricas, ya que sólo acceden a la clase a través de la interfaz pública
y, por lo tanto, pueden usar cualquier otra implementación. Sin embargo, el
término genérico se aplica preferentemente a operaciones bien definidas,
de utilidad general, como purge() o sort() (que ordena los elementos de
menor a mayor). Estas funciones, a veces son candidatas a pertenecer a la
clase. print() es genérica y podrı́amos copiar su código tal cual e insertarlo
en cualquier otra implementación de listas. Pero todavı́a serı́a mejor evitar
esta duplicación de código, usando la noción de polimorfismo y herencia de
clases.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 84
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
n−1
X
Tprom (n) = Pj T (j) (2.5)
j=0
n−1
1 X
Tprom (n) = n−j−1
n
j=0
1 (2.6)
= ((n − 1) + (n − 2) + · · · + 1 + 0)
n
1 (n − 1)n n−1 n
= = ≈ = O(n)
n 2 2 2
Como se espera que insert(p,x) y erase(p) sean dos de las rutinas más
usadas sobre listas, es deseable encontrar otras representaciones que dis-
minuyan estos tiempos, idealmente a O(1).
Los tiempos de ejecución de las otras rutinas es O(1) (salvo erase(p,q)
y print()).
1. class cell;
2. typedef cell *iterator-t;
3.
4. class list {
5. private:
6. cell *first, *last;
7. public:
8. list();
9. ˜list();
10. iterator-t insert(iterator-t p,elem-t j);
11. iterator-t erase(iterator-t p);
12. iterator-t erase(iterator-t p,iterator-t q);
13. void clear();
14. iterator-t begin();
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 85
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 86
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
q r
x y z
w
s
Debemos definir ahora que tipo será, en esta implementación, una posi-
ción, es decir el tipo iterator_t. La elección natural parece ser cell *,
ya que si tenemos un puntero a la celda tenemos acceso al contenido.
Es decir, parece natural elegir como posición, el puntero a la celda que
contiene el dato. Sin embargo, consideremos el proceso de insertar un el-
emento en la lista (ver figura 2.7). Originalmente tenemos los elementos
L=(...,x,y,z,..) y queremos insertar un elemento w en la posición de
y es decir L=(...,x,w,y,z,..). Sean q y r los punteros a las celdas que
contienen a x e y. Las operaciones a realizar son
1. s = new cell;
2. s->elem = w;
3. s->next = r;
4. q->next = s;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 87
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
y está claro que podemos realizar las operaciones de enlace. Decimos que
las posiciones están “adelantadas” con respecto a los elementos. Notar que
después de la inserción la posición de y pasa a ser el puntero a la nueva
celda s, esto ilustra el concepto de que después de insertar un elemento las
posiciones posteriores a la de inserción (inclusive) son inválidas.
L
first
last
q0=begin() q1 q2 q3 q4=end()
1 3 2 5
celda de
encabezamiento
La lista en sı́ puede estar representada por un campo cell *first que
es un puntero a la primera celda. Recordemos que una vez que tenemos un
puntero a la primera celda podemos recorrer todas las siguientes. Pero el he-
cho de introducir un adelanto en las posiciones trae aparejado un problema.
¿Cuál es la posición del primer elemento de la lista? ¿A qué apunta first
cuando la celda esta vacı́a? Estos problemas se resuelven si introducimos
una “celda de encabezamiento”, es decir una celda que no contiene dato y
tal que first apunta a ella. Entonces, por ejemplo, si nuestra lista contiene
a los elementos L=(1,3,2,5), la representación por punteros serı́a como se
muestra en la figura 2.8. Si q0-q4 son punteros a las 5 celdas de la lista (in-
cluyendo la de encabezamiento), entonces el elemento 1 está en la posición
q0 de manera que, por ejemplo
[Link](q0) retornará 1.
[Link](q1) retornará 3.
[Link](q2) retornará 2.
[Link](q3) retornará 5.
[Link](q4) dará error ya que corresponde a la posición de la
celda ficticia (representada en lı́nea de trazos en la figura).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 88
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
3. }
4.
5. list::˜list() { clear(); delete first; }
6.
7. elem-t &list::retrieve(iterator-t p) {
8. return p->next->elem;
9. }
10.
11. iterator-t list::next(iterator-t p) {
12. return p->next;
13. }
14.
15. iterator-t list::prev(iterator-t p) {
16. iterator-t q = first;
17. while (q->next != p) q = q->next;
18. return q;
19. }
20.
21. iterator-t
22. list::insert(iterator-t p,elem-t k) {
23. iterator-t q = p->next;
24. iterator-t c = new cell;
25. p->next = c;
26. c->next = q;
27. c->elem = k;
28. if (q==NULL) last = c;
29. return p;
30. }
31.
32. iterator-t list::begin() { return first; }
33.
34. iterator-t list::end() { return last; }
35.
36. iterator-t list::erase(iterator-t p) {
37. if (p->next==last) last = p;
38. iterator-t q = p->next;
39. p->next = q->next;
40. delete q;
41. return p;
42. }
43.
44. iterator-t list::erase(iterator-t p,iterator-t q) {
45. if (p==q) return p;
46. iterator-t s, r = p->next;
47. p->next = q->next;
48. if (!p->next) last = p;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 89
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 90
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
1. iterator_t list::end() {
2. cell *q = first;
3. while (q->next) q = q->next;
4. return q;
5. }
L
first
last
q0=begin()=end()
celda de
encabezamiento
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 91
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
x y
w
c
p q q->next
x w y
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 92
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
p r q q->next
x w y z
eliminar
La gestión de celdas puede llegar a ser más eficiente que la del sis-
tema (en tiempo y memoria).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 93
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
Esto puede ser de interés sobre todo para el manejo de grandes can-
tidades de celdas relativamente pequeñas. Además, el uso de cursores es
interesante en si mismo, independientemente de las ventajas o desventajas,
ya que permite entender mejor el funcionamiento de los punteros.
Entre las desventajas que tienen los cursores podemos citar que,
1. class list;
2. typedef int iterator-t;
3.
4. class cell {
5. friend class list;
6. elem-t elem;
7. iterator-t next;
8. cell();
9. };
10.
11. class list {
12. private:
13. friend class cell;
14. static iterator-t NULL-CELL;
15. static int CELL-SPACE-SIZE;
16. static cell *cell-space;
17. static iterator-t top-free-cell;
18. iterator-t new-cell();
19. void delete-cell(iterator-t c);
20. iterator-t first, last;
21. void cell-space-init();
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 94
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
Las listas consistirán entonces en una serie de celdas dentro del ar-
reglo, con una celda de encabezamiento y terminadas por una celda cuyo
campo next posee el cursor inválido NULL_CELL. Por ejemplo, en la figu-
ra 2.13 vemos una situación tı́pica, el espacio de celdas cell_space tiene
CELL_SPACE_SIZE=12 celdas. En ese espacio conviven 2 listas L1=(6,9,5,3)
y L2=(2,5). La lista L1 ocupa 5 celdas incluyendo la de encabezamiento que
en este caso es la celda 2. Como el dato en las celdas de encabezamiento
es irrelevante ponemos un “*”. El campo next de la celda de encabezamien-
to apunta a la primera celda que en este caso es la 5. La celda 5 contiene el
primer elemento (que es un 6) en el campo elem y el campo next apunta a
la siguiente celda (que es la 11). Los enlaces para las celdas de la lista L1 se
muestran con flechas a la derecha del arreglo. La última celda (la 8) contiene
en el campo next el cursor inválido NULL_CELL, representado en el dibujo
por un pequeño cı́rculo negro. La lista L2 contiene 3 celdas, incluyendo la de
encabezamiento, a saber las celdas 9, 1 y 10. Las 4 celdas restantes (7,0,4
y 3) están libres.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 95
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
= NULL_CELL cell_space
= cualquier valor elem next
* nro. de celda 0
4
1
*
2 10
2
5
CELL_SPACE_SIZE
L1 3
*
first=2 4 *
last=8 5
* 3
6 11
6
5 8
top_free_cell 7
0
8
*
3
L2 9
first=9 10
* 1
last=10 5
11
9 6
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 96
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
Punteros Cursores
Area de almacenamiento heap cell space
Tipo usado para las di- cell* c int c
recciones de las celdas
(iterator t)
Dereferenciación de direc- *c cell space[c]
ciones (dirección → celda)
Dato de una celda dada su c->elem cell space[c].elem
dirección c
Enlace de una celda (campo c->next cell space[c].next
next) dada su dirección c
Alocar una celda c = new cell; c = new cell();
Liberar una celda delete cell; delete cell(c);
Dirección inválida NULL NULL CELL
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 97
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
1. cell::cell() : next(list::NULL-CELL) {}
2.
3. cell *list::cell-space = NULL;
4. int list::CELL-SPACE-SIZE = 100;
5. iterator-t list::NULL-CELL = -1;
6. iterator-t list::top-free-cell = list::NULL-CELL;
7.
8. list::list() {
9. if (!cell-space) cell-space-init();
10. first = last = new-cell();
11. cell-space[first].next = NULL-CELL;
12. }
13.
14. void list::cell-space-init() {
15. cell-space = new cell[CELL-SPACE-SIZE];
16. for (int j=0; j<CELL-SPACE-SIZE-1; j++)
17. cell-space[j].next = j+1;
18. cell-space[CELL-SPACE-SIZE-1].next = NULL-CELL;
19. top-free-cell = 0;
20. }
21.
22. iterator-t list::new-cell() {
23. iterator-t top = top-free-cell;
24. if (top==NULL-CELL) {
25. cout << "No hay mas celdas \n";
26. abort();
27. }
28. top-free-cell = cell-space[top-free-cell].next;
29. return top;
30. }
31.
32. void list::delete-cell(iterator-t c) {
33. cell-space[c].next = top-free-cell;
34. top-free-cell = c;
35. }
36.
37. list::˜list() { clear(); }
38.
39. elem-t &list::retrieve(iterator-t p) {
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 98
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 99
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
84. delete-cell(r);
85. r = s;
86. }
87. return p;
88. }
89.
90. void list::clear() { erase(begin(),end()); }
91.
92. void list::print() {
93. iterator-t p = begin();
94. while (p!=end()) {
95. cout << retrieve(p) << " ";
96. p = next(p);
97. }
98. cout << endl;
99. }
100.
101. void list::printd() {
102. cout << "h(" << first << ")" << endl;
103. iterator-t c = cell-space[first].next;
104. int j=0;
105. while (c!=NULL-CELL) {
106. cout << j++ << "(" << c << ") :" << cell-space[c].elem << endl;
107. c = next(c);
108. }
109. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 100
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
Tabla 2.2: Tiempos de ejecución de los métodos del TAD lista en las difer-
entes implementaciones. j, k son las posiciones enteras correspondientes a
p,q
ya que sólo difieren en cómo acceden a las celdas, pero de todas for-
mas las operaciones involucradas son O(1), en ambos casos, de man-
era que la comparación es entre punteros/cursores y arreglos. Las opera-
ciones begin(), end(), next(), retrieve() son O(1) en ambos casos.
La diferencia más importante es, como ya hemos mencionado, en las op-
eraciones insert(p,x) y erase(p). En la implementación por arreglos se
debe mover todos los elementos que están después de la posición p (los
lazos de las lı́neas 64 y 53, código 2.7), o sea que es O(n − j) donde j
es la posición (como número entero) de la posición abstracta p, mientras
que para punteros/cursores es O(1). erase(p,q) debe hacer el delete (o
delete_cell() de todas las celdas en el rango [p,q) de manera que re-
quiere O(k − j) operaciones, donde k, j son las posiciones enteras corre-
spondientes a p,q. Por otra parte, en la implementación por arreglos sólo
debe moverse los elementos en el rango [q,end()) (esto es n − k elemen-
tos) k − j posiciones hacia el comienzo. Pero el mover cada elemento en
un arreglo es tiempo constante, independientemente de cuantas posiciones
se mueve, de manera que la operación es O(n − k). En el lı́mite, la fun-
ción clear() es O(n) para punteros/cursores y O(1) para arreglos. Por otra
parte, la función prev(p) es O(j) para punteros/cursores, ya que involucra
ir al comienzo de la lista y recorrer todas las celdas hasta encontrar la p (los
lazos de las lı́neas lı́nea 17 en el código 2.9 y la lı́nea 50 en el código 2.11).
Esto involucra un tiempo O(j), mientras que en el caso de la implementación
por arreglos debe retornar p-1 ya que las posiciones son enteras, y por lo
tanto es O(1). Los tiempos de ejecución están listados en la Tabla 2.2. (No-
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 101
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
ta: Para insert por arreglos se indica en la tabla O(n), que corresponde al
peor caso que es cuando p está al principio de la lista y entre corchetes se
indica T = c(n − j) que es el número de operaciones dependiendo de j .
La constante c es el tiempo promedio para hacer una de las operaciones. Lo
mismo ocurre para otras funciones.)
Comparando globalmente las implementaciones, vemos que la imple-
mentación por arreglos es más competitiva en prev(), clear(). Pero
prev() decididamente es una operación para la cual no están diseñadas
las listas simplemente enlazadas y normalmente clear() deberı́a ser menos
usada que insert() o erase(), por lo cual raramente se usan arreglos para
representar listas. Por otra parte la diferencia para erase(p,q) puede ser a
favor de punteros/cursores (cuando se borran pequeños intervalos en la mi-
tad de la lista) o a favor de los arreglos (cuando se borran grandes regiones
cerca del final).
1. list<int> lista_1;
2. list<double> lista_2;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 102
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
p = next(p); → p++
p = prev(p); → p--
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 103
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
5. int suma = 0;
6. while (true) {
7. if (q==[Link]()) break;
8. else if (suma==*q) { suma=0; q++; }
9. else if (p==[Link]()) break;
10. else if (suma<*q) suma += *p++;
11. else return false;
12. }
13. return suma==0 && p==[Link]() && q==[Link]();
14. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 104
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
1. #ifndef AED-LIST-H
2. #define AED-LIST-H
3.
4. #include <cstddef>
5. #include <iostream>
6.
7. namespace aed {
8.
9. template<class T>
10. class list {
11. public:
12. class iterator;
13. private:
14. class cell {
15. friend class list;
16. friend class iterator;
17. T t;
18. cell *next;
19. cell() : next(NULL) {}
20. };
21. cell *first, *last;
22. public:
23. class iterator {
24. private:
25. friend class list;
26. cell* ptr;
27. public:
28. T & operator*() { return ptr->next->t; }
29. T *operator->() { return &ptr->next->t; }
30. bool operator!=(iterator q) { return ptr!=[Link]; }
31. bool operator==(iterator q) { return ptr==[Link]; }
32. iterator(cell *p=NULL) : ptr(p) {}
33. // Prefix:
34. iterator operator++() {
35. ptr = ptr->next;
36. return *this;
37. }
38. // Postfix:
39. iterator operator++(int) {
40. iterator q = *this;
41. ptr = ptr->next;
42. return q;
43. }
44. };
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 105
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
45.
46. list() {
47. first = new cell;
48. last = first;
49. }
50. ˜list() { clear(); delete first; }
51. iterator insert(iterator p,T t) {
52. cell *q = [Link]->next;
53. cell *c = new cell;
54. [Link]->next = c;
55. c->next = q;
56. c->t = t;
57. if (q==NULL) last = c;
58. return p;
59. }
60. iterator erase(iterator p) {
61. cell *q = [Link]->next;
62. if (q==last) last = [Link];
63. [Link]->next = q->next;
64. delete q;
65. return p;
66. }
67. iterator erase(iterator p,iterator q) {
68. cell *s, *r = [Link]->next;
69. [Link]->next = [Link]->next;
70. if (![Link]->next) last = [Link];
71. while (r!=[Link]->next) {
72. s = r->next;
73. delete r;
74. r = s;
75. }
76. return p;
77. }
78. void clear() { erase(begin(),end()); }
79. iterator begin() { return iterator(first); }
80. iterator end() { return iterator(last); }
81. void print() {
82. iterator p = begin();
83. while (p!=end()) std::cout << *p++ << " ";
84. std::cout << std::endl;
85. }
86. void printd() {
87. std::cout << "h(" << first << ")" << std::endl;
88. cell *c = first->next;
89. int j=0;
90. while (c!=NULL) {
91. std::cout << j++ << "(" << c << ") :" << c->t << std::endl;
92. c = c->next;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 106
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
93. }
94. }
95. int size() {
96. int sz = 0;
97. iterator p = begin();
98. while (p++!=end()) sz++;
99. return sz;
100. }
101. };
102.
103. }
104. #endif
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 107
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.1. El TAD Lista
1. iterator_t q = p->next;
se convierte en
1. cell *q = [Link]->next;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 108
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
venga utilizar una “lista doblemente enlazada”. En este tipo de listas cada
celda tiene dos punteros uno al elemento siguiente y otro al anterior.
1. class cell {
2. elem_t elem;
3. cell *next, *prev;
4. cell() : next(NULL), prev(NULL) {}
5. };
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 109
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
rpn[2 + 3] = 2, 3, + (2.7)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 110
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
1. elem-t top();
2. void pop();
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 111
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
Notar que empty() no modifica la pila, mucha gente tiende a confundirla con
clear().
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 112
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
8. return true;
9. }
10. }
11.
12. bool check1(stack &P,double &v1) {
13. if ([Link]()<1) {
14. cout << "Debe haber al menos 1 elemento en la pila!!\n";
15. return false;
16. } else {
17. v1 = [Link](); [Link]();
18. return true;
19. }
20. }
21.
22. int main() {
23. stack P,Q;
24. const int SIZE=100;
25. char line[SIZE];
26. double v1,v2;
27. // REPL (read, eval print loop)
28. while(true) {
29. // Read
30. cout << "calc> ";
31. assert(line);
32. [Link](line,SIZE,’\n’);
33. if(!cin) break;
34. // ‘Eval’ y ‘print’ dependiendo del caso
35. if (!strcmp(line,"+")) {
36. if (check2(P,v1,v2)) {
37. [Link](v1+v2);
38. printf("-> %lf\n",[Link]());
39. }
40. } else if (!strcmp(line,"-")) {
41. if (check2(P,v1,v2)) {
42. [Link](v1-v2);
43. printf("-> %lf\n",[Link]());
44. }
45. } else if (!strcmp(line,"*")) {
46. if (check2(P,v1,v2)) {
47. [Link](v1*v2);
48. printf("-> %lf\n",[Link]());
49. }
50. } else if (!strcmp(line,"/")) {
51. if (check2(P,v1,v2)) {
52. [Link](v1/v2);
53. printf("-> %lf\n",[Link]());
54. }
55. } else if (!strcmp(line,"log")) {
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 113
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
56. if (check1(P,v1)) {
57. [Link](log(v1));
58. printf("-> %lf\n",[Link]());
59. }
60. } else if (!strcmp(line,"exp")) {
61. if (check1(P,v1)) {
62. [Link](exp(v1));
63. printf("-> %lf\n",[Link]());
64. }
65. } else if (!strcmp(line,"sqrt")) {
66. if (check1(P,v1)) {
67. [Link](sqrt(v1));
68. printf("-> %lf\n",[Link]());
69. }
70. } else if (!strcmp(line,"atan2")) {
71. if (check2(P,v1,v2)) {
72. [Link](atan2(v1,v2));
73. printf("-> %lf\n",[Link]());
74. }
75. } else if (!strcmp(line,"c")) {
76. printf("vaciando la pila. . .\n");
77. [Link]();
78. } else if (!strcmp(line,"p")) {
79. printf("pila: ");
80. while(![Link]()) {
81. double x = [Link]();
82. cout << x << " ";
83. [Link]();
84. [Link](x);
85. }
86. while(![Link]()) {
87. double x = [Link]();
88. [Link]();
89. [Link](x);
90. }
91. cout << endl;
92. } else if (!strcmp(line,"x")) {
93. "Saliendo de calc!!\n";
94. exit(0);
95. } else {
96. double val;
97. int nread = sscanf(line," %lf",&val);
98. if (nread!=1) {
99. printf("Entrada invalida!!: \" %s\"\n",line);
100. continue;
101. } else {
102. [Link](val);
103. printf("<- %g\n",val);
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 114
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
104. }
105. }
106. }
107. }
La lı́nea se lee con la función getline() del standard input cin. Si hay
cualquier tipo de error al leer (fin de archivo, por ejemplo) cin queda en un
estado que retorna false, de ahı́ que basta con verificar !cin para ver si
la lectura ha sido exitosa. El valor leı́do queda en el string (de C) line. El
string tiene un tamaño fijo SIZE. También se podrı́a hacer dinámicamente
con rutinas más elaboradas y seguras como la snprintf o asprintf (ver
Foundation [b]). Antes de leer la lı́nea se imprime el prompt “calc> ”.
Después de leer la lı́nea se entra en una secuencia de if-else (simi-
lar a un switch). Si la lı́nea entrada es un operador o función, entonces se
extrae el número apropiado de operandos de la pila, se aplica la operación
correspondiente y el resultado es ingresado en la pila. Es importante veri-
ficar que la pila contenga un número apropiado de valores antes de hacer la
operación. Por ejemplo, si el usuario entra + entonces debemos verificar que
al menos haya 2 operandos en la pila. Esto se hace con la función check2
que verifica que efectivamente haya dos operandos, los extrae de la pila y los
pone en las variables v1 y v2. Si no hay un número apropiado de valores en-
tonces check2 retorna false. Para funciones u operadores unarios usamos
la función similar check1.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 115
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 116
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
1. stack::stack() : size-m(0) { }
2.
3. elem-t& stack::top() {
4. return retrieve(begin());
5. }
6.
7. void stack::pop() {
8. erase(begin()); size-m--;
9. }
10.
11. void stack::push(elem-t x) {
12. insert(begin(),x); size-m++;
13. }
14.
15. void stack::clear() {
16. erase(begin(),end()); size-m = 0;
17. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 117
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.2. El TAD pila
18.
19. bool stack::empty() {
20. return begin()==end();
21. }
22.
23. int stack::size() {
24. return size-m;
25. }
vectores
Notar que la pila deriva directamente de la lista, pero con una declaración
private. De esta forma el usuario de la clase stack no puede usar métodos
de la clase lista. El hecho de que la pila sea tan simple permite que pueda ser
implementada en términos de otros contenedores también, como por ejem-
plo el contenedor vector de STL. De esta forma, podemos pensar a la pila
como un “adaptador” (“container adaptor” ), es decir que brinda un subcon-
junto de la funcionalidad del contenedor original ver figura 2.14. La ventaja
de operar sobre el adaptador (en este caso la pila) y no directamente sobre
el contenedor básico (en este caso la lista) es que el adaptador puede de-
spués conectarse fácilmente a otros contenedores (en la figura representado
por enchufes).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 118
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
1. #ifndef AED-STACK-H
2. #define AED-STACK-H
3.
4. #include <aedsrc/list.h>
5.
6. namespace aed {
7.
8. template<class T>
9. class stack : private list<T> {
10. private:
11. int size-m;
12. public:
13. stack() : size-m(0) { }
14. void clear() { erase(begin(),end()); size-m = 0; }
15. T &top() { return *begin(); }
16. void pop() { erase(begin()); size-m--; }
17. void push(T x) { insert(begin(),x); size-m++; }
18. int size() { return size-m; }
19. bool empty() { return size-m==0; }
20. };
21. }
22. #endif
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 119
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
a0 ≤ a2 ≤ · · · ≤ an−2
(2.10)
a1 ≤ a3 ≤ · · · ≤ an−1
a = 10 1 12 3 14 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
(2.11)
Verificamos que los elementos en las posiciones pares ( 10 12 14 16 . . . )
están ordenados entre sı́, como también los que están en las posiciones
impares ( 1 3 5 7 . . . ). Consideremos primero el algoritmo de “orde-
namiento por inserción” (ver código 2.19, los algoritmos de ordenamiento
serán estudiados en más detalle en un capı́tulo posterior).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 120
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
7. a[k+1] = x;
8. }
9. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 121
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
j
10 1 12 3 14 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
p
1 10 12 3 14 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
j
1 1012 3 14 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
p
1 1012 3 14 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
j
1 10 12 3 14 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
p
1 3 10 12 14 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
j
1 3 10 1214 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
p
1 3 10 1214 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
j
1 3 10 12 14 5 16 7 18 9 20 51 22 53 24 55 26 57 28 59
p (2.12)
1 3 5 10 12 14 16 7 18 9 20 51 22 53 24 55 26 57 28 59
j
1 3 5 10 12 1416 7 18 9 20 51 22 53 24 55 26 57 28 59
p
1 3 5 10 12 1416 7 18 9 20 51 22 53 24 55 26 57 28 59
j
1 3 5 10 12 14 16 7 18 9 20 51 22 53 24 55 26 57 28 59
p
1 3 5 7 10 12 14 16 18 9 20 51 22 53 24 55 26 57 28 59
j
1 3 5 7 10 12 14 1618 9 20 51 22 53 24 55 26 57 28 59
p
1 3 5 7 10 12 14 1618 9 20 51 22 53 24 55 26 57 28 59
j
1 3 5 7 10 12 14 16 18 9 20 51 22 53 24 55 26 57 28 59
p
1 3 5 7 9 10 12 14 16 18 20 51 22 53 24 55 26 57 28 59
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 122
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
n−1
X
T (n) = (p − j) (2.14)
j=1
o, tomando promedios
n−1
X
Tprom (n) = dj (2.15)
j=1
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 123
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
√
la conclusión que el desplazamiento promedio es O( n), de manera que
3
el algoritmo resulta ser O(n /2 ). Esto representa una gran ventaja contra el
O(n2 ) del algoritmo de ordenamiento original.
De todas formas, podemos mejorar más aún esto si tenemos en cuenta
que las subsecuencias pares e impares están ordenadas. Por ejemplo con-
sideremos lo que ocurre en el seguimiento (2.12) al mover los elementos 18
y 9 que originalmente estaban en las posiciones q = 8 y q + 1 = 9. Como
vemos, los elementos en las posiciones 0 a q − 1 = 7 están ordenados.
Notar que el máximo del rango ya ordenado [0, q) es menor que el máximo
de estos dos nuevos elementos aq y aq+a , ya que todos los elementos en
[0, q) provienen de elementos en las subsecuencias que estaban antes de
aq y aq+1 .
q−1
max aj < max(aq , aq+1 ) (2.17)
j=0
por lo tanto después de insertar los dos nuevos elementos, el mayor (que en
este caso es 18) quedará en la posición q + 1. El menor (min(aq , aq+1 ) =
9) viaja una cierta distancia, hasta la posición p = 4. Notar que, por un
razonamiento similar, todos los elementos en las posiciones [q + 2, n) deben
ser mayores que min(aq , aq+1 ), de manera que los elementos en [0, p) no
se moverán a partir de esta inserción.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 124
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
19. a[p++] = x;
20. // Saca primer elemento de C . . .
21. }
22. a[p++] = minr;
23. a[p++] = minr;
24. // Apendizar ‘maxr’ al rango [0,p) . . .
25. q += 2;
26. }
27. // Apendizar todos los elementos en C menores que
28. // min(a-q,a-{q+1}) al rango [0,p)
29. // . . .
30. }
Código 2.20: Algoritmo de intercalación con una cola auxiliar [Archivo: mr-
[Link]]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 125
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
momento la cola contiene los elementos 10,12,14,16 y 18. Como son todos
menores que min(aq , aq+1 ) = 20 apendizamos todos al rango [0, p = 5) de
manera que queda p = 10. Se apendiza también el 20, con lo cual queda
p = 11 y finalmente se apendiza max(aq , aq+1 ) = 51 a la cola. Como en
ese momento la cola esta vacı́a, depués de la inserción queda en la cola solo
el 51.
1. #ifndef AED-QUEUE-H
2. #define AED-QUEUE-H
3.
4. #include <aedsrc/list.h>
5.
6. namespace aed {
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 126
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
7.
8. template<class T>
9. class queue : private list<T> {
10. private:
11. int size-m;
12. public:
13. queue() : size-m(0) { }
14. void clear() { erase(begin(),end()); size-m = 0; }
15. T &front() { return *begin(); }
16. void pop() { erase(begin()); size-m--; }
17. void push(T x) { insert(end(),x); size-m++; }
18. int size() { return size-m; }
19. bool empty() { return size-m==0; }
20. };
21. }
22. #endif
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 127
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.3. El TAD cola
El lazo sobre q se ejecuta n/2 veces. Dentro del lazo todas las op-
eraciones son de tiempo constante, salvo los lazos sobre la cola de las
lı́neas 20–23 y 29–32. Las veces que el primer lazo se ejecuta para cada
q puede ser completamente variable, pero notar que por cada ejecución de
este lazo, un elemento es introducido en el rango [0, p). Lo mismo ocurre
para el segundo lazo. Como finalmente todos los elementos terminan en el
rango [0, p), el número de veces total que se ejecutan los dos lazos debe ser
menor que n. De hecho como para cada ejecución del cuerpo del lazo sobre
q se introduce un elemento en [0, p) en la lı́nea 24, el número de veces total
que se ejecutan los dos lazos es exactamente igual a n/2. De manera que
el algoritmo es finalmente O(n).
Sin embargo, el algoritmo no es in-place, la memoria adicional está dada
por el tamaño de la cola C. En el peor caso, C puede llegar a tener n/2 ele-
mentos y en el mejor caso ninguno. En el caso promedio, el tamaño máximo
de C es tanto como el número de desplazamientos que deben hacerse en el
√
algoritmo de inserción puro, descrito en la sección §[Link], es decir O( n).
Todo esto esta resumido en la tabla (M es la memoria adicional requeri-
da).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 128
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
inssort merge
Tpeor (n) O(n2 ) O(n)
3
Tprom (n) O(n /2 ) O(n)
Tmejor (n) O(n) O(n)
Mpeor (n) O(n) O(n)
√
Mprom (n) O(n) O( n)
Mmejor (n) O(n) O(1)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 129
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
D
-1 C
1 1
0
0
3
4
2
9
-3
Ejemplo 2.5: Consigna: Escribir un programa que memoriza para cada doc-
umento de identidad el sueldo de un empleado. Se van ingresando números
de documento, si el documento ya tiene un sueldo asignado, entonces esto
se reporta por consola, sino el usuario debe entrar un sueldo el cual es asig-
nado a ese número de documento en la tabla. Una posible interacción con el
programa puede ser como sigue
1. [mstorti@spider aedsrc]$ payroll
2. Ingrese nro. documento > 14203323
3. Ingrese salario mensual: 2000
4. Ingrese nro. documento > 13324435
5. Ingrese salario mensual: 3000
6. Ingrese nro. documento > 13323421
7. Ingrese salario mensual: 2500
8. Ingrese nro. documento > 14203323
9. Doc: 14203323, salario: 2000
10. Ingrese nro. documento > 13323421
11. Doc: 13323421, salario: 2500
12. Ingrese nro. documento > 13242323
13. Ingrese salario mensual: 5000
14. Ingrese nro. documento > 0
15. No se ingresan mas sueldos...
16. [mstorti@spider aedsrc]$
Solución: Un posible seudocódigo puede observarse en el código 2.23.
El programa entra en un lazo infinito en el cual se ingresa el número de doc-
umento y se detiene cuando se ingresa un documento nulo. Reconocemos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 130
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
Código 2.23: Seudocódigo para construir una tabla que representa la cor-
respondencia número de documento → sueldo. [Archivo: [Link]]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 131
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
6. public:
7. iterator-t find(domain-t key);
8. iterator-t insert(domain-t key,range-t val);
9. range-t& retrieve(domain-t key);
10. void erase(iterator-t p);
11. int erase(domain-t key);
12. domain-t key(iterator-t p);
13. range-t& value(iterator-t p);
14. iterator-t begin();
15. iterator-t next(iterator-t p);
16. iterator-t end();
17. void clear();
18. void print();
19. };
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 132
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
1. map sueldo;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 133
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
2. while(1) {
3. cout << "Ingrese nro. documento > ";
4. int doc;
5. double salario;
6. cin >> doc;
7. if(!doc) break;
8. iterator-t q = [Link](doc);
9. if (q==[Link]()) {
10. cout << "Ingrese salario mensual: ";
11. cin >> salario;
12. [Link](doc,salario);
13. cout << [Link]() << " salarios cargados" << endl;
14. } else {
15. cout << "Doc: " << doc << ", salario: "
16. << [Link](doc) << endl;
17. }
18. }
19. cout << "No se ingresan mas sueldos. . ." << endl;
D
C
4
-1
3 1
2 9
-3
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 134
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
A las listas y vectores se les llama contenedores lineales, ya que en ellos ex-
iste un ordenamiento natural de las posiciones. En lo que sigue discutiremos
la implementación del TAD correspondencia basadas en estos contenedores
lineales. Más adelante, en otro capı́tulo, veremos otras implementaciones
más eficientes. Cuando hablemos de la implementación con listas asumire-
mos una implementación de listas basada en punteros o cursores, mientras
que para vectores asumiremos arreglos estándar de C++ o el mismo vector
de STL. En esta sección asumiremos que las asignaciones son insertadas
en el contenedor ya sea al principio o en el final del mismo, de manera que
el orden entre las diferentes asignaciones es en principio aleatorio. Más ade-
lante discutiremos el caso en que las asignaciones se mantienen ordenadas
por la clave. En ese caso las asignaciones aparecerı́an en el contenedor
como en (2.20).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 135
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 136
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
1. class map;
2.
3. class elem-t {
4. private:
5. friend class map;
6. domain-t first;
7. range-t second;
8. };
9. // iterator para map va a ser el mismo que para listas.
10. class map {
11. private:
12. list l;
13.
14. iterator-t lower-bound(domain-t key) {
15. iterator-t p = [Link]();
16. while (p!=[Link]()) {
17. domain-t dom = [Link](p).first;
18. if (dom >= key) return p;
19. p = [Link](p);
20. }
21. return [Link]();
22. }
23.
24. public:
25. map() { }
26. iterator-t find(domain-t key) {
27. iterator-t p = lower-bound(key);
28. if (p!=[Link]() && [Link](p).first == key)
29. return p;
30. else return [Link]();
31. }
32. iterator-t insert(domain-t key,range-t val) {
33. iterator-t p = lower-bound(key);
34. if (p==[Link]() | | [Link](p).first != key) {
35. elem-t elem;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 137
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 138
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 139
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
1. #ifndef AED-MAP-H
2. #define AED-MAP-H
3.
4. #include <aedsrc/list.h>
5. #include <iostream>
6.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 140
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 141
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
En vez elem_t
del se tipo
define un template
pair<class first_t,class second_t>. Este template es usa-
do para map y otros contenedores y algoritmos de STL. Los campos
first y second de pair son públicos. Esto es un caso muy especial
dentro de las STL y la programación orientada a objetos en general
ya que en general se desaconseja permitir el acceso a los campos
datos de un objeto. (La motivación para esto es que pair<> es una
construcción tan simple que se permite violar la regla.) pair<> es una
forma muy simple de asociar pares de valores en un único objeto. Otro
uso de pair<> es para permitir que una función retorne dos valores al
mismo tiempo. Esto se logra haciendo que retorne un objeto de tipo
pair<>.
La clase map es un template de las clases domain_t y range_t. Los
elementos de la lista serán de tipo pair<domain_t,range_t>.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 142
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
1. map<int,double> sueldo;
2. while(1) {
3. cout << "Ingrese nro. documento > ";
4. int doc;
5. double salario;
6. cin >> doc;
7. if (!doc) break;
8. map<int,double>::iterator q = [Link](doc);
9. if (q==[Link]()) {
10. cout << "Ingrese salario mensual: ";
11. cin >> salario;
12. sueldo[doc]=salario;
13. } else {
14. cout << "Doc: " << doc << ", salario: "
15. << sueldo[doc] << endl;
16. }
17. }
18. cout << "No se ingresan mas sueldos. . ." << endl;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 143
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
1. #ifndef AED-MAPV-H
2. #define AED-MAPV-H
3.
4. #include <iostream>
5. #include <vector>
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 144
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
6.
7. using namespace std;
8.
9. namespace aed {
10.
11. template<typename first-t,typename second-t>
12. class pair {
13. public:
14. first-t first;
15. second-t second;
16. pair() : first(first-t()), second(second-t()) {}
17. };
18.
19. // iterator para map va a ser el mismo que para listas.
20. template<typename domain-t,typename range-t>
21. class map {
22.
23. public:
24. typedef int iterator;
25.
26. private:
27. typedef pair<domain-t,range-t> pair-t;
28. typedef vector<pair-t> vector-t;
29. vector-t v;
30.
31. iterator lower-bound(domain-t key) {
32. int p=0, q=[Link](), r;
33. if (!q | | v[p].first >key) return 0;
34. while (q-p > 1) {
35. r = (p+q)/2;
36. domain-t kr = v[r].first;
37. if (key > kr) p=r;
38. else if (key < kr) q=r;
39. else if (kr==key) return r;
40. }
41. if (v[p].first == key) return p;
42. else return q;
43. }
44.
45. public:
46. map() { }
47.
48. iterator find(domain-t key) {
49. int p = lower-bound(key);
50. if (p == [Link]() | | v[p].first == key) return p;
51. else return [Link]();
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 145
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
52. }
53. range-t & operator[ ](domain-t key) {
54. iterator p = lower-bound(key);
55. if (p == [Link]() | | v[p].first != key) {
56. [Link]-back(pair-t());
57. iterator q = [Link]();
58. while (--q > p) v[q] = v[q-1];
59. v[p].first = key;
60. }
61. return v[p].second;
62. }
63. int erase(domain-t key) {
64. iterator p = find(key); int r = 0;
65. if (p!=end()) { erase(p); r = 1; }
66. return r;
67. }
68. bool empty() { return [Link]()==0; }
69. void erase(iterator p) {
70. iterator q = p;
71. while (q != [Link]()) {
72. v[q] = v[q+1];
73. q++;
74. }
75. [Link]-back();
76. }
77. iterator begin() { return 0; }
78. iterator end() { return [Link](); }
79. void clear() { [Link](); }
80. int size() { return [Link](); }
81. };
82. }
83. #endif
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 146
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
p r q
Una vez que tenemos un rango válido [p, q) podemos refinarlo (ver figu-
ra 2.17) calculando la posición media
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 147
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 148
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
ya que cada uno de las componentes del primer par es menor que la del
segundo par, pero no sabrı́amos como comparar (2, 3) con (5, 1). Primero
definamos más precisamente qué es una “relación de orden”.
Definición: “<” es una relación de orden en el conjunto C si,
a < b,
b<a
a = b.
a<c<e
a<c=eyd<f
a=c<eyb<d
a=c=eyb<d<f
y es obvio que en cada una de ellas resulta ser (a, b) < (e, f ). También es
fácil demostrar la condición 2.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 149
C AP ÍTULO 2. T IPOS DE DATOS ABSTRACTOS FUNDAMENTALES / Sección 2.4. El TAD correspondencia
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 150
Capı́tulo 3
Arboles
151
C AP ÍTULO 3. A RBOLES / Sección 3.1. Nomenclatura básica de árboles
n1 n2 nk
T1 T2 Tk
anuser/
[Link] p1.h g1 g2
[Link] [Link]
[Link]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 152
C AP ÍTULO 3. A RBOLES / Sección 3.1. Nomenclatura básica de árboles
b c d
e f g
Hojas. Un nodo que no tiene hijos es una “hoja” del árbol. (Recordemos
que, por contraposición el nodo que no tiene padre es único y es la raı́z.) En
el ejemplo, los nodos e, f , h y d son hojas.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 153
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
[Link].3. Nodos hermanos Se dice que los nodos que tienen un mismo
padre son “hermanos” entre sı́. Notar que no basta con que dos nodos estén
en el mismo nivel para que sean hermanos. Los nodos f y g en el árbol de
la figura 3.3 están en el mismo nivel, pero no son hermanos entre sı́.
a a
b c c b
En este capı́tulo, estudiamos árboles para los cuales el orden entre los
hermanos es relevante. Es decir, los árboles de la figura 3.4 son diferentes
ya que si bien a tiene los mismos hijos, están en diferente orden. Volviendo
a la figura 3.3 decimos que el nodo c está a la derecha de b, o también que
c es es el hermano derecho de b. También decimos que b es el “hijo más
a la izquierda” de a. El orden entre los hermanos se propaga a los hijos,
de manera que h está a la derecha de e ya que ambos son descendientes
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 154
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
a a
b c d Λ b c d
e f g e f g
h Λ h
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 155
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
b c d Λ8
e f Λ3 g Λ6 Λ7
Λ1 Λ2
h Λ5
Λ4
m=n
m es antecesor propio de n
n es antecesor propio de m
m está a la derecha de n
n está a la derecha de m
N = {n}∪{descendientes(n)}∪{antecesores(n)}∪{derecha(n)}∪{izquierda(n)}
(3.2)
En la figura 3.7 vemos la partición inducida para los nodos c y f . Notar que
en el caso del nodo f el conjunto de los descendientes es vacı́o (∅).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 156
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
antecesores
antecesores
a a
izquierda derecha
b c d izquierda b c d
e f g descendientes e f g derecha
h h
Existen varias formas de recorrer un árbol listando los nodos del mismo,
generando una lista de nodos. Dado un nodo n con hijos n1 , n2 , . . . nm ,
el “listado en orden previo” (“preorder” ) del nodo n que denotaremos como
oprev(n) se puede definir recursivamente como sigue
Además el orden previo del árbol vacı́o es la lista vacı́a: oprev(Λ) = ().
Consideremos por ejemplo el árbol de la figura 3.3. Aplicando recursiva-
mente (3.3) tenemos
Una forma más visual de obtener el listado en orden previo es como se mues-
tra en la figura 3.8. Recorremos el borde del árbol en el sentido contrario a
las agujas del reloj, partiendo de un punto imaginario a la izquierda del nodo
raı́z y terminando en otro a la derecha del mismo, como muestra la lı́nea de
puntos. Dado un nodo como el b el camino pasa cerca de él en varios puntos
(3 en el caso de b, marcados con pequeños números en el camino). El orden
previo consiste en listar los nodos una sola vez, la primera vez que el camino
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 157
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
pasa cerca del árbol. Ası́ en el caso del nodo b, este se lista al pasar por 1.
Queda como ejercicio para el lector verificar el orden resultante coincide con
el dado en (3.4).
1
b 3 c d
2
e f g
Recorriendo el borde del árbol igual que antes (esto es en sentido con-
trario a las agujas del reloj), listando el nodo la última vez que el recor-
rido pasa por al lado del mismo. Por ejemplo el nodo b serı́a listado al
pasar por el punto 3.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 158
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
camino pasa cera de ellos. Una vez que la lista es obtenida, invertimos
la lista. En el caso de la figura el recorrido en sentido contrario darı́a
(a, d, c, g, h, b, f, e). Al invertirlo queda como en (3.6).
Existe otro orden que se llama “simétrico”, pero este sólo tiene sentido
en el caso de árboles binarios, ası́ que no será explicado aquı́.
+ −
2 3 4 5
Figura 3.9: Arbol correspondiente a la expresión matemática (2 + 3) ∗ (4 − 5)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 159
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
*
+ +
3 * 20 −
sin − 10 7
+ 5 exp
4 20 3
Figura 3.10: Arbol correspondiente a la expresión matemática (3.7)
1. (f (g a b) (h t u v) (q r (s w)))
Para expresiones más complejas como la de (3.7), la forma Lisp para el árbol
(figura 3.10) da el código Lisp correspondiente
1. (a (b e f) (c (g h)) d)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 160
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
g h q
a b t u v r s
Notemos que el orden de los nodos es igual al del orden previo. Se puede dar
una definición precisa de la notación Lisp como para el caso de los órdenes
previo y posterior:
(
si n es una hoja: n
lisp(n) = (3.9)
caso contrario: (n lisp(n1 ) lisp(n2 ) . . . lisp(nm ))
donde n1 . . . nm son los hijos del nodo n.
Es evidente que existe una relación unı́voca entre un árbol y su notación
Lisp. Los paréntesis dan la estructura adicional que permite establecer la
relación unı́voca. La utilidad de esta notación es que permite fácilmente es-
cribir árboles en una lı́nea de texto, sin tener que recurrir a un gráfico. Basado
en esta notación, es fácil escribir una función que convierta un árbol a una
lista y viceversa.
También permite “serializar” un árbol, es decir, convertir una estructura
“bidimensional” como es el árbol, en una estructura unidimensional como es
una lista. El serializar una estructura compleja permite almcenarla en disco
o comunicarla a otro proceso por mensajes.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 161
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
a a a a
b c d b d b b
c c c d
Figura 3.12: Los cuatro árboles de la figura tienen el mismo orden previo
(a, b, c, d)
a a a a
b c d b d d d
c c b c
Figura 3.13: Los cuatro árboles de la figura tienen el mismo orden posterior
(b, c, d, a)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 162
C AP ÍTULO 3. A RBOLES / Sección 3.2. Orden de los nodos
Solución: De los primeros dos nodos en orden previo se deduce que z debe
ser el nodo raı́z y w su primer hijo. No hay nodos antes de w en orden pos-
terior de manera que w no tiene hijos. El nodo siguiente a w en orden previo
es a que por lo tanto debe ser el segundo hijo de z . Los nodos que están
antes de a pero después de w en orden posterior son x e y , de manera que
estos son descendientes de a. De la misma forma se deduce que el tercer
hijo de z es c y que sus descendientes son m, t, u, v . A esta altura podemos
esbozar un dibujo del árbol como se muestra en la figura 3.14. Las lı́neas de
puntos indican que, por ejemplo, sabemos que m, t, u, v son descendientes
de c, pero todavı́a no conocemos la estructura de ese subárbol.
w a c
x m
y t
u
v
Figura 3.14: Etapa parcial en la reconstrucción del árbol del ejemplo 3.2
oprev(c) = (c, m, t, u, v)
(3.13)
opost(c) = (t, u, v, m, c)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 163
C AP ÍTULO 3. A RBOLES / Sección 3.3. Operaciones con árboles
w a c
x y m
t u v
Código 3.1: Algoritmo para recorrer un árbol en orden previo. [Archivo: pre-
[Link]]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 164
C AP ÍTULO 3. A RBOLES / Sección 3.3. Operaciones con árboles
Código 3.3: Algoritmo para imprimir los datos de un árbol en notación Lisp.
[Archivo: [Link]]
En el código 3.2 se puede ver un código similar para generar la lista con
el orden posterior, basada en (3.5). Similarmente, en código 3.3 puede verse
la implementación de una rutina que imprime la notación Lisp de un árbol.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 165
C AP ÍTULO 3. A RBOLES / Sección 3.3. Operaciones con árboles
a a
b c d b c d
e f z g e f z g
h h
inserta z en Λ3 inserta z en g
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 166
C AP ÍTULO 3. A RBOLES / Sección 3.3. Operaciones con árboles
5. iterator
6. ct = /* hijo mas izquierdo de ‘nt’ . . .*/,
7. cq = /* hijo mas izquierdo de ‘nq’ . . .*/;
8. while (/* ‘ct’ no es ‘Lambda’. . . */) {
9. cq = tree-copy(T,ct,Q,cq);
10. ct = /* hermano derecho de ‘ct’. . . */;
11. cq = /* hermano derecho de ‘cq’. . . */;
12. }
13. return nq;
14. }
1 2 3
T Q Q Q
a a a a
n n
b c t b Λ1 q b c b c
c c c cq
e f r tg t w e f e f Λ2 q e f r Λ3
s t h s t
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 167
C AP ÍTULO 3. A RBOLES / Sección 3.3. Operaciones con árboles
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 168
C AP ÍTULO 3. A RBOLES / Sección 3.3. Operaciones con árboles
Código 3.6: Algoritmo que elimina los nodos de un árbol que son impares,
incluyendo todo su subárbol [Archivo: [Link]]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 169
C AP ÍTULO 3. A RBOLES / Sección 3.4. Interfaz básica para árboles
1. class iterator-t {
2. /* . . . . */
3. public:
4. iterator-t lchild();
5. iterator-t right();
6. };
7.
8. class tree {
9. /* . . . . */
10. public:
11. iterator-t begin();
12. iterator-t end();
13. elem-t &retrieve(iterator-t p);
14. iterator-t insert(iterator-t p,elem-t t);
15. iterator-t erase(iterator-t p);
16. void clear();
17. iterator-t splice(iterator-t to,iterator-t from);
18. };
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 170
C AP ÍTULO 3. A RBOLES / Sección 3.4. Interfaz básica para árboles
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 171
C AP ÍTULO 3. A RBOLES / Sección 3.4. Interfaz básica para árboles
Q T Q T
a u a u
to
b c v b c r v
e f r g w x y e f g w s t x y
s t h h
from
[Link](v,r)
Figura 3.18: Operación splice.
7. c = [Link]();
8. }
9. }
10. void preorder(tree &T,list<int> &L) {
11. if ([Link]()) return;
12. preorder(T,[Link](),L);
13. }
14.
15. //---:---<*>---:---<*>---:---<*>---:---<*>
16. void postorder(tree &T,iterator-t n,list<int> &L) {
17. iterator-t c = [Link]();
18. while (c!=[Link]()) {
19. postorder(T,c,L);
20. c = [Link]();
21. }
22. [Link]([Link](),[Link](n));
23. }
24. void postorder(tree &T,list<int> &L) {
25. if ([Link]()) return;
26. postorder(T,[Link](),L);
27. }
28.
29. //---:---<*>---:---<*>---:---<*>---:---<*>
30. void lisp-print(tree &T,iterator-t n) {
31. iterator-t c = [Link]();
32. if (c==[Link]()) cout << [Link](n);
33. else {
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 172
C AP ÍTULO 3. A RBOLES / Sección 3.4. Interfaz básica para árboles
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 173
C AP ÍTULO 3. A RBOLES / Sección 3.4. Interfaz básica para árboles
80.
81. void mirror-copy(tree &T,tree &Q) {
82. if ([Link]() != [Link]())
83. mirror-copy(T,[Link](),Q,[Link]());
84. }
85.
86. //---:---<*>---:---<*>---:---<*>---:---<*>
87. iterator-t prune-odd(tree &T,iterator-t n) {
88. if ([Link](n) % 2) n = [Link](n);
89. else {
90. iterator-t c = [Link]();
91. while (c != [Link]()) c = prune-odd(T,c);
92. n = [Link]();
93. }
94. return n;
95. }
96.
97. void prune-odd(tree &T) {
98. if ([Link]() != [Link]()) prune-odd(T,[Link]());
99. }
Código 3.8: Diversos algoritmos sobre árboles con la interfaz básica. [Archi-
vo: [Link]]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 174
C AP ÍTULO 3. A RBOLES / Sección 3.4. Interfaz básica para árboles
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 175
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
x hermano derecho
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 176
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
celda de encabezamiento
*
c c
r g w r g w
s t h s t h
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 177
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
b c d Λ8
e f Λ3 g Λ6 Λ7
Λ1 Λ2
h Λ5
Λ4
[Link]
y
[Link]−>left_child
v
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 178
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
miento, al igual que con las listas. La raı́z del árbol, si existe, es una celda
hija de la celda de encabezamiento. Si el árbol está vacı́o, entonces el iterator
correspondiente a la raı́z (y que se obtiene llamando a begin()) corresponde
a ptr=NULL, prev=NULL, father=celda de encabezamiento.
1. class tree;
2. class iterator-t;
3.
4. //---:---<*>---:---<*>---:---<*>---:---<*>
5. class cell {
6. friend class tree;
7. friend class iterator-t;
8. elem-t elem;
9. cell *right, *left-child;
10. cell() : right(NULL), left-child(NULL) {}
11. };
12.
13. //---:---<*>---:---<*>---:---<*>---:---<*>
14. class iterator-t {
15. private:
16. friend class tree;
17. cell *ptr,*prev,*father;
18. iterator-t(cell *p,cell *prev-a, cell *f-a)
19. : ptr(p), prev(prev-a), father(f-a) { }
20. public:
21. iterator-t(const iterator-t &q) {
22. ptr = [Link];
23. prev = [Link];
24. father = [Link];
25. }
26. bool operator!=(iterator-t q) { return ptr!=[Link]; }
27. bool operator==(iterator-t q) { return ptr==[Link]; }
28. iterator-t()
29. : ptr(NULL), prev(NULL), father(NULL) { }
30.
31. iterator-t lchild() {
32. return iterator-t(ptr->left-child,NULL,ptr);
33. }
34. iterator-t right() {
35. return iterator-t(ptr->right,ptr,father);
36. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 179
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
37. };
38.
39. //---:---<*>---:---<*>---:---<*>---:---<*>
40. class tree {
41. private:
42. cell *header;
43. tree(const tree &T) {}
44. public:
45.
46. tree() {
47. header = new cell;
48. header->right = NULL;
49. header->left-child = NULL;
50. }
51. ˜tree() { clear(); delete header; }
52.
53. elem-t &retrieve(iterator-t p) {
54. return [Link]->elem;
55. }
56.
57. iterator-t insert(iterator-t p,elem-t elem) {
58. assert(!([Link]==header && [Link]));
59. cell *c = new cell;
60. c->right = [Link];
61. c->elem = elem;
62. [Link] = c;
63. if ([Link]) [Link]->right = c;
64. else [Link]->left-child = c;
65. return p;
66. }
67. iterator-t erase(iterator-t p) {
68. if(p==end()) return p;
69. iterator-t c = [Link]();
70. while (c!=end()) c = erase(c);
71. cell *q = [Link];
72. [Link] = [Link]->right;
73. if ([Link]) [Link]->right = [Link];
74. else [Link]->left-child = [Link];
75. delete q;
76. return p;
77. }
78.
79. iterator-t splice(iterator-t to,iterator-t from) {
80. assert(!([Link]==header && [Link]));
81. if ([Link]->right == [Link]) return from;
82. cell *c = [Link];
83.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 180
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 181
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 182
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
[Link]=[Link]
x
[Link]=NULL [Link]=[Link]−>left_child
y
[Link]=[Link]
y
[Link]=[Link] [Link]=[Link]
x y
• [Link]= [Link]->right
• [Link]= [Link]
• [Link]= [Link]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 183
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 184
C AP ÍTULO 3. A RBOLES / Sección 3.5. Implementación de la interfaz básica por punteros
• ptr=header->left_child
• prev=NULL
• father=header
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 185
C AP ÍTULO 3. A RBOLES / Sección 3.6. Interfaz avanzada
1. #ifndef AED-TREE-H
2. #define AED-TREE-H
3.
4. #include <cassert>
5. #include <iostream>
6. #include <cstddef>
7. #include <cstdlib>
8.
9. namespace aed {
10.
11. //---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>---:
12. template<class T>
13. class tree {
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 186
C AP ÍTULO 3. A RBOLES / Sección 3.6. Interfaz avanzada
14. public:
15. class iterator;
16. private:
17. class cell {
18. friend class tree;
19. friend class iterator;
20. T t;
21. cell *right, *left-child;
22. cell() : right(NULL), left-child(NULL) {}
23. };
24. cell *header;
25.
26. iterator tree-copy-aux(iterator nq,
27. tree<T> &TT,iterator nt) {
28. nq = insert(nq,*nt);
29. iterator
30. ct = [Link](),
31. cq = [Link]();
32. while (ct!=[Link]()) {
33. cq = tree-copy-aux(cq,TT,ct);
34. ct = [Link]();
35. cq = [Link]();
36. }
37. return nq;
38. }
39. public:
40. static int cell-count-m;
41. static int cell-count() { return cell-count-m; }
42. class iterator {
43. private:
44. friend class tree;
45. cell *ptr,*prev,*father;
46. iterator(cell *p,cell *prev-a,cell *f-a) : ptr(p),
47. prev(prev-a), father(f-a) { }
48. public:
49. iterator(const iterator &q) {
50. ptr = [Link];
51. prev = [Link];
52. father = [Link];
53. }
54. T &operator*() { return ptr->t; }
55. T *operator->() { return &ptr->t; }
56. bool operator!=(iterator q) { return ptr!=[Link]; }
57. bool operator==(iterator q) { return ptr==[Link]; }
58. iterator() : ptr(NULL), prev(NULL), father(NULL) { }
59.
60. iterator lchild() { return iterator(ptr->left-child,NULL,ptr); }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 187
C AP ÍTULO 3. A RBOLES / Sección 3.6. Interfaz avanzada
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 188
C AP ÍTULO 3. A RBOLES / Sección 3.6. Interfaz avanzada
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 189
C AP ÍTULO 3. A RBOLES / Sección 3.6. Interfaz avanzada
155. };
156.
157. template<class T>
158. int tree<T>::cell-count-m = 0;
159.
160. template<class T>
161. void swap(tree<T> &T1, tree<T> &T2) { [Link](T2); }
162. }
163. #endif
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 190
C AP ÍTULO 3. A RBOLES / Sección 3.6. Interfaz avanzada
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 191
C AP ÍTULO 3. A RBOLES / Sección 3.6. Interfaz avanzada
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 192
C AP ÍTULO 3. A RBOLES / Sección 3.6. Interfaz avanzada
67. }
68.
69. int max-node(tree-t &T) {
70. return max-node(T,[Link]());
71. }
72.
73. //---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>---:
74. int max-leaf(tree-t &T,node-t n) {
75. if (n==[Link]()) return -1;
76. int w = *n;
77. node-t c = [Link]();
78. if (c==[Link]()) return w;
79. w = 0;
80. while (c!=[Link]()) {
81. int ww = max-leaf(T,c++);
82. if (ww > w) w = ww;
83. }
84. return w;
85. }
86.
87. int max-leaf(tree-t &T) {
88. return max-leaf(T,[Link]());
89. }
90.
91. //---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>---:
92. int leaf-count(tree-t &T,node-t n) {
93. if (n==[Link]()) return 0;
94. node-t c = [Link]();
95. if (c==[Link]()) return 1;
96. int w = 0;
97. while (c!=[Link]()) w += leaf-count(T,c++);
98. return w;
99. }
100.
101. int leaf-count(tree-t &T) {
102. return leaf-count(T,[Link]());
103. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 193
C AP ÍTULO 3. A RBOLES / Sección 3.7. Tiempos de ejecución
Operación T (n)
O(1)
begin(), end(), [Link](), n++,
n.left_child(), *n, insert(),
splice(to,from)
O(n)
erase(), find(), clear(), T1=T2
En la Tabla 3.1 vemos los tiempos de ejecución para las diferentes op-
eraciones sobre árboles. Es fácil ver que todas las funciones básicas tienen
costo O(1). Es notable que una función como splice() también sea O(1).
Esto se debe a que la operación de mover todo el árbol de una posición
a otra se realiza con una operación de punteros. Las operaciones que no
son O(1) son erase(p) que debe eliminar todos los nodos del subárbol del
nodo p, clear() que equivale a erase(begin()), find(x) y el constructor
por copia (T1=T2). En todos los casos n es o bien el número de nodos del
subárbol (erase(p) y find(x,p)) o bien el número total de nodos del árbol
(clear(), find(x) y el constructor por copia T1=T2).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 194
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
a a a
b b b
Los árboles que hemos estudiado hasta ahora son “árboles ordenados
orientados” (AOO) ya que los hermanos están ordenados entre sı́ y hay una
orientación de los caminos desde la raı́z a las hojas. Otro tipo importante de
árbol es el “árbol binario” (AB) en el cual cada nodo puede tener a lo sumo
dos hijos. Además, si un dado nodo n tiene un sólo hijo, entonces este puede
ser el hijo derecho o el hijo izquierdo de n. Por ejemplo si consideramos las
posibles estructuras de árboles con dos nodos (ver figura 3.25), tenemos que
para el caso de un AOO la única posibilidad es un nodo raı́z con un nodo hijo.
Por otra parte, si el árbol es binario, entonces existen dos posibilidades, que
el único hijo sea el hijo izquierdo o el derecho. Dicho de otra forma los AB
del centro y la derecha son diferentes, mientras que si fueran AOO entonces
serı́an ambos iguales al de la izquierda.
La notación Lisp para árboles debe ser modificada un poco con respecto
a la de AOO, ya que debemos introducir algún tipo de notación para un hijo
Λ. Básicamente, en el caso en que un nodo tiene un sólo hijo, reemplazamos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 195
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
b c
e d
nivel 0, 1 nodo
nivel 1, 2 nodos
nivel 2, 4 nodos
nivel l, 2lnodos
Figura 3.27: Cantidad máxima de nodos por nivel en un árbol binario lleno.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 196
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
nodos. Pero ésta es una serie geométrica de razón dos, por lo cual
2l+1 − 1
n≤ = 2l+1 − 1. (3.18)
2−1
O bien
n < 2l+1 . (3.19)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 197
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
Notar que sólo cambian las dos primeras y la inserción con respecto a las de
AOO.
1. class iterator-t {
2. /* . . . */
3. public:
4. iterator-t left();
5. iterator-t right();
6. };
7.
8. class btree {
9. /* . . . */
10. public:
11. iterator-t begin();
12. iterator-t end();
13. elem-t & retrieve(iterator-t p);
14. iterator-t insert(iterator-t p,elem-t t);
15. iterator-t erase(iterator-t p);
16. void clear();
17. iterator-t splice(iterator-t to,iterator-t from);
18. };
En el código 3.12 vemos una interfaz posible (recordemos que las STL
no tienen clases de árboles) para AB. Como siempre, la llamamos básica
porque no tiene templates, clases anidadas ni sobrecarga de operadores. Es
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 198
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
Código 3.13: Predicado que determina si dos árboles son iguales. [Archivo:
[Link]]
Como ejemplo de uso de esta interfaz vemos en código 3.13 una función
predicado (es decir una función que retorna un valor booleano) que determi-
na si dos árboles binarios T y Q son iguales. Dos árboles son iguales si
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 199
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
3 2
7 9 6 4
6 0 7 8
2 3
Código 3.14: Función predicado que determina si dos árboles son seme-
jantes. [Archivo: [Link]]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 200
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
Notar que la única diferencia es que no se comparan los valores de las raı́ces
de los subárboles comparados. En el código 3.14 se muestra una función
predicado que determina si dos árboles son semejantes. El código es igual
al de equal_p sólo que se elimina la lı́nea 5.
3 3
7 9 9 7
6 0 0 6
2 2
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 201
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
T0 T1 T2 T3 T4
n n tmp n tmp n n
3 3 7 3 7 3 3
7 9 9 6 9 6 9 7 9 7
6 0 0 0 0 6 0 6
2 2 2 2 2
Figura 3.30: Descripción gráfica del procedimiento para copiar convertir “in
place” un árbol en su espejo.
11. }
12. void mirror(btree &T) { mirror(T,[Link]()); }
Código 3.15: Función para copiar convertir “in place” un árbol en su espejo.
[Archivo: [Link]]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 202
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
x
hijo izquierdo hijo derecho
celda de encabezamiento
*
3 3
7 9 7 9
6 0 6 0
2 2
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 203
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 204
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 205
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
98.
99. iterator-t splice(iterator-t to,iterator-t from) {
100. cell *c = [Link];
101. [Link] = NULL;
102. if ([Link] == iterator-t::R)
103. [Link]->right = NULL;
104. else
105. [Link]->left = NULL;
106. if ([Link] == iterator-t::R) [Link]->right = c;
107. else [Link]->left = c;
108. [Link] = c;
109. return to;
110. }
111. iterator-t find(elem-t t) { return find(t,begin()); }
112. iterator-t find(elem-t t,iterator-t p) {
113. if(p==end() | | [Link]->t == t) return p;
114. iterator-t l = find(t,[Link]());
115. if (l!=end()) return l;
116. iterator-t r = find(t,[Link]());
117. if (r!=end()) return r;
118. return end();
119. }
120. void clear() { erase(begin()); }
121. iterator-t begin() {
122. return iterator-t(header->left,
123. iterator-t::L,header);
124. }
125. iterator-t end() { return iterator-t(); }
126.
127. void lisp-print(iterator-t n) {
128. if (n==end()) { cout << "."; return; }
129. iterator-t r = [Link](), l = [Link]();
130. bool is-leaf = r==end() && l==end();
131. if (is-leaf) cout << retrieve(n);
132. else {
133. cout << "(" << retrieve(n) << " ";
134. lisp-print(l);
135. cout << " ";
136. lisp-print(r);
137. cout << ")";
138. }
139. }
140. void lisp-print() { lisp-print(begin()); }
141. };
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 206
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
b c
d Λ1 Λ2 Λ3
Λ4 Λ5
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 207
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
que tienen ptr=NULL). Como end() retorna un iterator Λ (ver más aba-
jo), entonces esto habilita a usar los lazos tı́picos
[copy]
1. while (c!=[Link]()) {
2. // . . . .
3. c = [Link]();
4. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 208
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
1. template<class T>
2. class btree {
3. /* . . . */
4. public:
5. class iterator {
6. /* . . . */
7. public:
8. T &operator*();
9. T *operator->();
10. bool operator!=(iterator q);
11. bool operator==(iterator q);
12. iterator left();
13. iterator right();
14. };
15. iterator begin();
16. iterator end();
17. iterator insert(iterator p,T t);
18. iterator erase(iterator p);
19. iterator splice(iterator to,iterator from);
20. void clear();
21. };
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 209
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
2. *n = w;
3. y = n->member;
4. n->member = v;
A esta altura nos serı́a fácil escribir algoritmos que modifican los valores
de un árbol, por ejemplo sumarle a todos los valores contenidos en un árbol
un valor, o duplicarlos. Todos estos son casos particulares de un algoritmo
más general apply(Q,f) que tiene como argumentos un árbol Q y una “fun-
ción escalar” T f(T). y le aplica a cada uno de los valores nodales la función
en cuestión. Este es un ejemplo de “programación funcional”, es decir, pro-
gramación en los cuales los datos de los algoritmos pueden ser también
funciones.
C++ tiene un soporte básico para la programación funcional en la cual se
pueden pasar “punteros a funciones”. Un soporte más avanzado se obtiene
usando clases especiales que sobrecargan el operador (), a tales funciones
se les llama “functors”. Nosotros vamos a escribir ahora una herramienta
simple llamada apply(Q,f) que aplica a los nodos de un árbol una función
escalar t f(T) pasada por puntero.
1. template<class T>
2. void apply(btree<T> &Q,
3. typename btree<T>::iterator n,
4. T(*f)(T)) {
5. if (n==[Link]()) return;
6. *n = f(*n);
7. apply(Q,[Link](),f);
8. apply(Q,[Link](),f);
9. }
10. template<class T>
11. void apply(btree<T> &Q,T(*f)(T)) {
12. apply(Q,[Link](),f);
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 210
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
1. #ifndef AED-BTREE-H
2. #define AED-BTREE-H
3.
4. #include <iostream>
5. #include <cstddef>
6. #include <cstdlib>
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 211
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
7. #include <cassert>
8. #include <list>
9.
10. using namespace std;
11.
12. namespace aed {
13.
14. //---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>---:---<*>---:
15. template<class T>
16. class btree {
17. public:
18. class iterator;
19. private:
20. class cell {
21. friend class btree;
22. friend class iterator;
23. T t;
24. cell *right,*left;
25. cell() : right(NULL), left(NULL) {}
26. };
27. cell *header;
28. enum side-t {NONE,R,L};
29. public:
30. static int cell-count-m;
31. static int cell-count() { return cell-count-m; }
32. class iterator {
33. private:
34. friend class btree;
35. cell *ptr,*father;
36. side-t side;
37. iterator(cell *p,side-t side-a,cell *f-a)
38. : ptr(p), side(side-a), father(f-a) { }
39. public:
40. iterator(const iterator &q) {
41. ptr = [Link];
42. side = [Link];
43. father = [Link];
44. }
45. T &operator*() { return ptr->t; }
46. T *operator->() { return &ptr->t; }
47. bool operator!=(iterator q) { return ptr!=[Link]; }
48. bool operator==(iterator q) { return ptr==[Link]; }
49. iterator() : ptr(NULL), side(NONE), father(NULL) { }
50.
51. iterator left() { return iterator(ptr->left,L,ptr); }
52. iterator right() { return iterator(ptr->right,R,ptr); }
53.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 212
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
54. };
55.
56. btree() {
57. header = new cell;
58. cell-count-m++;
59. header->right = NULL;
60. header->left = NULL;
61. }
62. btree<T>(const btree<T> &TT) {
63. if (&TT != this) {
64. header = new cell;
65. cell-count-m++;
66. header->right = NULL;
67. header->left = NULL;
68. btree<T> &TTT = (btree<T> &) TT;
69. if ([Link]()!=[Link]())
70. copy(begin(),TTT,[Link]());
71. }
72. }
73. btree &operator=(btree<T> &TT) {
74. if (this != &TT) {
75. clear();
76. copy(begin(),TT,[Link]());
77. }
78. return *this;
79. }
80. ˜btree() { clear(); delete header; cell-count-m--; }
81. iterator insert(iterator p,T t) {
82. assert(p==end());
83. cell *c = new cell;
84. cell-count-m++;
85. c->t = t;
86. if ([Link]==R) [Link]->right = c;
87. else [Link]->left = c;
88. [Link] = c;
89. return p;
90. }
91. iterator erase(iterator p) {
92. if(p==end()) return p;
93. erase([Link]());
94. erase([Link]());
95. if ([Link]==R) [Link]->right = NULL;
96. else [Link]->left = NULL;
97. delete [Link];
98. cell-count-m--;
99. [Link] = NULL;
100. return p;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 213
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
101. }
102.
103. iterator splice(iterator to,iterator from) {
104. if (from==end()) return to;
105. cell *c = [Link];
106. [Link] = NULL;
107. if ([Link]==R) [Link]->right = NULL;
108. else [Link]->left = NULL;
109.
110. if ([Link]==R) [Link]->right = c;
111. else [Link]->left = c;
112. [Link] = c;
113. return to;
114. }
115. iterator copy(iterator nq,btree<T> &TT,iterator nt) {
116. nq = insert(nq,*nt);
117. iterator m = [Link]();
118. if (m != [Link]()) copy([Link](),TT,m);
119. m = [Link]();
120. if (m != [Link]()) copy([Link](),TT,m);
121. return nq;
122. }
123. iterator find(T t) { return find(t,begin()); }
124. iterator find(T t,iterator p) {
125. if(p==end() | | [Link]->t == t) return p;
126. iterator l = find(t,[Link]());
127. if (l!=end()) return l;
128. iterator r = find(t,[Link]());
129. if (r!=end()) return r;
130. return end();
131. }
132. void clear() { erase(begin()); }
133. iterator begin() { return iterator(header->left,L,header); }
134.
135. void lisp-print(iterator n) {
136. if (n==end()) { cout << "."; return; }
137. iterator r = [Link](), l = [Link]();
138. bool is-leaf = r==end() && l==end();
139. if (is-leaf) cout << *n;
140. else {
141. cout << "(" << *n << " ";
142. lisp-print(l);
143. cout << " ";
144. lisp-print(r);
145. cout << ")";
146. }
147. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 214
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 215
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 216
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
150 bits
hli =
100 caracteres
= 0.70 × 1 + 0.1 × 3 + 0.1 × 3 + 0.1 × 2 (3.23)
X
= P (c)l(c)
c
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 217
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
<nulo>
0 1
00 01 10 11
...
000 001
C1 C2 C3
<nulo> <nulo> <nulo>
0 1 0 1 0 1
a a
00 01 10 11 10 11 01 10
a b c d d b c
100 101 101
b c d
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 218
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
C4
<nulo>
0 1
a
10 11
101 111
d
1010
10100 10101
b c
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 219
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 220
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
T1 T2 T3
nc =2
nc =3
T4 T5 T6
T7 T8 T9
nc =4
Figura 3.37: Posibles árboles binarios llenos con nc hojas.
del árbol”. Los códigos se obtienen asignando cada uno de los nc caracteres
a una de las hojas del árbol. Entonces, por cada uno de los árboles de T4
a T9 se pueden obtener 4! = 24 posibles tablas de códigos permutando los
caracteres entre sı́. Por ejemplo, los tres árboles de la figura 3.38 son al-
gunos de los árboles que se obtienen de la estructura de T4 en la figura 3.37
permutando las letras entre sı́. Como el número de permutaciones de nc
caracteres es nc !, tenemos que en total hay a lo sumo (nc − 1)!nc ! posibles
tablas de códigos. Usando las herramientas desarrolladas en la sección §1.3
(en particular §1.3.9), vemos que
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 221
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
d d a
.....
c a b
a b b c d c
Figura 3.38: Posibles tablas de códigos que se obtienen permutando las le-
tras en las hojas de una estructura dada.
comb(T0 , T1 , T2 , T3 ) = (comb(comb(T0 , T1 ), T2 , T3 ),
comb(comb(T0 , T2 ), T1 , T3 ),
comb(comb(T0 , T3 ), T1 , T2 ),
(3.25)
comb(comb(T1 , T2 ), T0 , T3 ),
comb(comb(T1 , T3 ), T0 , T2 ),
comb(comb(T2 , T3 ), T0 , T1 ))
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 222
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
T3 T2
T2 T3 T2 T3 T0 T1
T0 T1 T0 T1
comb(comb(T0 , T1 ), T2 , T3 ) = (comb(comb(comb(T0 , T1 ), T2 ), T3 ),
comb(comb(comb(T0 , T1 ), T3 ), T2 ),
comb(comb(T2 , T3 ), comb(T0 , T1 )))
(3.26)
Estos tres posibles combinaciones pueden observarse en la figura 3.39. Para
la figura hemos asumido que los árboles originales son nodos simples, pero
podrı́an ser a su vez árboles.
Entonces, cada una de las sublistas en (3.25) genera 3 árboles. En gen-
eral vamos a tener
n2n−1
Nfbt (n) = O (3.30)
2n
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 223
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 224
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
40. pj->splice(pj->begin(),[Link]());
41.
42. pk=[Link]();
43. for (int kk=0; kk<k; kk++) pk++;
44. pk = [Link](pk,btree-t());
45. pk->splice(pk->begin(),[Link]());
46.
47. }
48. }
49. }
Código 3.20: Implementación del algoritmo que genera todos los árboles
llenos. [Archivo: [Link]]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 225
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
Una estrategia más simple serı́a escribir una función basada en este
mismo algoritmo que genere todos los árboles posibles en una lista. Luego
se recorre la lista calculando la longitud media para cada árbol y reteniendo
la menor. La implementación propuesta es mucho más eficiente en uso de
memoria ya que en todo momento sólo hay un árbol generado y también de
tiempo de cálculo ya que en esta estrategia más simple los árboles se deben
ir combinando por copia, mientras que en la propuesta el mismo árbol va
pasando de una forma a la otra con simples operaciones de splice().
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 226
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
n
ml mr
c d e
a b
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 227
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 228
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 229
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 230
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
de Huffman.
T1 T2 T3 T4 T5 T6 T1 T7 T8
0.4 0.15 0.15 0.1 0.1 0.1 0.4 0.25 0.35
j=0
a b c d e f a j=3
c d b
T1 T2 T3 T4 T7
e f
0.4 0.15 0.15 0.1 0.2
j=1 T1 T9
a b c d
0.4 0.60
e f
a j=4
T1 T2 T8 T6
0.4 0.15 0.25 0.2 c d b
j=2
e f
a b
c d e f T10
1.0
a j=5
c d b
e f
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 231
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
<nulo> <nulo>
0 1 0 1
a a
10 11 10 11
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 232
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
1. struct huffman-tree {
2. double p;
3. btree<int> T;
4. };
5.
6. void
7. huffman(const vector<double> &prob,btree<int> &T) {
8. typedef list<huffman-tree> bosque-t;
9.
10. // Contiene todos los arboles
11. bosque-t bosque;
12. // Numero de caracteres del codigo
13. int N = [Link]();
14. // Crear los arboles iniciales poniendolos en
15. // una lista Los elementos de la lista contienen
16. // la probabilidad de cada caracter y un arbol
17. // con un solo nodo. Los nodos interiores del
18. // arbol tienen un -1 (es solo para
19. // consistencia) y las hojas tienen el indice
20. // del caracter. (entre 0 y N-1)
21. for (int j=0; j<N; j++) {
22. // Agrega un nuevo elemento a la lista
23. bosque-t::iterator htree =
24. [Link]([Link](),huffman-tree());
25. htree->p = prob[j];
26. htree->[Link](htree->[Link](),j);
27. }
28.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 233
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 234
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
76. [Link]([Link](),[Link]()->[Link]());
77. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 235
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
1. void
2. huffman-codes(btree<int> &T,btree<int>::iterator node,
3. const vector<double> &prob,
4. codigo-t &codigo, vector<codigo-t> &codigos) {
5. // ‘codigo’ es el codigo calculado hasta node.
6. // La funcion se va llamando recursivamente y a
7. // medida que va bajando en el arbol va
8. // agregando bits al codigo.
9. if (*node>=0) {
10. // Si es una hoja directamente inserta un
11. // codigo en ‘codigos’
12. codigos[*node] = codigo;
13. return;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 236
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
14. } else {
15. // Le va pasando ‘codigo’ a los hijos los
16. // cuales van agregando codigos a ‘codigos’.
17. // ‘codigo’ se va pasando por referencia de
18. // manera que las llamadas recursivas lo deben
19. // dejar tal como estaba. Por eso, despues
20. // despues de agregar un 0 hay que sacarlo
21. // y lo mismo con el 1.
22. [Link]-back(0);
23. huffman-codes(T,[Link](),prob,codigo,codigos);
24. [Link]-back();
25.
26. [Link]-back(1);
27. huffman-codes(T,[Link](),prob,codigo,codigos);
28. [Link]-back();
29. return;
30. }
31. }
32.
33. void
34. huffman-codes(btree<int> &H,const vector<double> &prob,
35. vector<codigo-t> &codigos) {
36. // Este es el codigo de un caracter en particular. Es
37. // pasado por referencia, de manera que hay una sola instancia
38. // de codigo.
39. codigo-t codigo;
40. huffman-codes(H,[Link](),prob,codigo,codigos);
41. }
42.
43. const int NB = 8;
44. const int bufflen = 1024;
45.
46. void qflush(queue<char> &Q, queue<char-t> &Qbytes,
47. int &nbits) {
48. // Convierte ‘NB’ bytes de ‘Q’ a un char.
49. // Si ‘Q’ queda viacia entonces rellena con 0’s.
50. char-t c=0;
51. for (int j=0; j<NB; j++) {
52. int b = 0;
53. if (![Link]()) {
54. b = [Link]();
55. [Link]();
56. nbits++;
57. }
58. c <<= 1;
59. if (b) c |= 1;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 237
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 238
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 239
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
154. assert(zip);
155. } else zip = stdout;
156.
157. // Guarda encabezamiento en archivo zippeado conteniendo
158. // las probabilidades para despues poder reconstruir el arbol
159. for (int j=0; j<N; j++) {
160. fwrite(&prob[j],sizeof(double),1,zip);
161. fwrite(&letters[j],sizeof(char-t),1,zip);
162. }
163. // Terminador (probabilidad negativa)
164. double p = -1.0;
165. fwrite(&p,sizeof(double),1,zip);
166.
167. vector<char-t> buff(bufflen);
168. // Cantidad de bits almacenados en buff
169. int nbits=0;
170.
171. // Zippea. Va convirtiendo los caracteres de ‘fin’ en
172. // codigos y los inserta en la cola ‘Q’, o sea que ‘Q’
173. // contiene todos elementos 0 o 1. Por otra parte va sacan
174. // dode a 8 bits de Q y los convierte en un byte en
175. // ‘Qbytes’. O sea que ‘Qbytes’ contiene caracteres que
176. // pueden tomar cualquier valor entre 0 y NUMCHAR-1.
177. queue<char> Q;
178. queue<char-t> Qbytes;
179. assert(fid);
180. while(![Link]()) {
181. // Va tomando de a un elemento de ‘fin’ y pone todo el
182. // codigo correspondiente en ‘Q’
183. int c = [Link]();
184. [Link]();
185. assert(c<NUMCHAR);
186. int k = indx[c];
187. assert(k>=0 && k<N);
188. codigo-t &cod = codigos[k];
189. for (int j=0; j<[Link](); j++) [Link](cod[j]);
190. // Convierte bits de ‘Q’ a caracteres
191. while ([Link]()>NB) qflush(Q,Qbytes,nbits);
192. // Escribe en el archivo zippeado.
193. while ([Link]()>bufflen) bflush(Qbytes,buff,nbits,zip);
194. }
195.
196. // Convierte el resto que puede quedar en Q
197. while ([Link]()>0) qflush(Q,Qbytes,nbits);
198. // Escribe el resto de lo que esta en Qbytes en ‘zip’
199. while ([Link]()>0) bflush(Qbytes,buff,nbits,zip);
200. // Terminador final con longitud de bloque=0
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 240
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 241
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 242
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 243
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
342. }
343. // Va convirtiendo bits de ‘Q’ en
344. // caracteres. Si ‘pop-char()’ no puede
345. // sacar un caracter, entonces va a devolver
346. // 0 y se termina el lazo. En ese caso ‘m’
347. // queda en la posicion correspondiente en el
348. // arbol.
349. while(pop-char(Q,H,m,k)) putc(letters[k],unz);
350. }
351. }
352.
353. assert(!.empty());
354. // Cerrar los archivos abiertos.
355. fclose(zip);
356. fclose(unz);
357. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 244
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 245
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
de la escritura a disco.
Para descomprimir el archivo es necesario contar con el árbol que
produjo la compresión. La solución utilizada aquı́ es guardar el vec-
tor de probabilidades utilizado prob y los caracteres correspondientes,
ya que el árbol puede ser calculado unı́vocamente usando la función
huffman() a partir de las probabilidades. Para guardar el árbol se
van escribiendo en el archivo la probabilidad y el caracter de a uno
(lı́neas 159–162). Para indicar el fin de la tabla se escribe una proba-
bilidad negativa (-1.0). La lectura de la tabla se hace en hufunzip()
se hace en la lı́neas 264–275. Ambas funciones (hufzip y hufunzip)
calculan el árbol usando huffman() en las lı́neas 141 y 280, respecti-
vamente.
El lazo que comprime son las lı́neas 180–194. Simplemente va toman-
do caracteres de fin y los convierte a bits, usando el código corre-
spondiente, en Q. Simultáneamente va pasando tantas NB-tuplas de
bits de Q a Qbytes con la función qflush() y tantos bytes de Qbytes
al archivo zippeado con bflush(). La rutina bflush() va imprimiendo
en el archivo de a bufflen bytes.
En el archivo comprimido se van almacenando los bytes de a blo-
ques de longitud bufflen o menor. Los bloques se almacenan gra-
bando primero la longitud del bloque (un entero) (lı́nea 73) y después
el bloque de bytes correspondiente (lı́nea 81).
Después del lazo pueden quedar bits en Q y bytes en Qbytes. Los
lazos de las lı́neas 197 y 199 terminan de procesar estos restos.
El archivo se descomprime en las lı́nea 312 de hufunzip(). Se leen
bloques de bytes en la lı́nea 327 y se van convirtiendo a bits en
lı́nea 341.
La función pop_char(Q,H,m,k) va sacando bits de Q y moviendo el no-
do m en el árbol hasta que m llega a una hoja (en cuyo caso pop_char()
retorna un caracter por el argumento k, o mejor dicho el ı́ndice corre-
spondiente) o hasta que Q queda vacı́a. En este caso m es vuelto a la
raı́z del árbol. Por ejemplo, refiriéndonos al código C2 de la figura 3.35
si inicialmente m está en el nodo 1 y Q={0110010110}, entonces el
primer bit 0 de la cola mueve m al nodo 10 y el segundo a 101. A esa
altura pop_char() devuelve el caracter c ya que ha llegado a una ho-
ja y m vuelve a la raı́z. La cola de bits queda en Q={10010110}. Si
volvemos a llamar a pop_char() repetidamente va a ir devolviendo los
caracteres b (100) y c (101). A esa altura queda Q={10}. Si volvemos
a llamar a pop_char(), m va a descender hasta el nodo 10 y Q va a
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 246
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 247
C AP ÍTULO 3. A RBOLES / Sección 3.8. Arboles binarios
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 248
Capı́tulo 4
Conjuntos
249
C AP ÍTULO 4. C ONJUNTOS / Sección 4.1. Introducción a los conjuntos
A ∪ B = (A ∩ B) ∪ (A − B) ∪ (B − A) (4.2)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 250
C AP ÍTULO 4. C ONJUNTOS / Sección 4.1. Introducción a los conjuntos
13. /* . . . */;
14. public:
15. set();
16. set(const set &);
17. ˜set();
18. elem-t retrieve(iterator-t p);
19. pair<iterator-t,bool> insert(elem-t t);
20. void erase(iterator-t p);
21. int erase(elem-t x);
22. void clear();
23. iterator-t next(iterator-t p);
24. iterator-t find(elem-t x);
25. iterator-t begin();
26. iterator-t end();
27. };
28. void set-union(set &A,set &B,set &C);
29. void set-intersection(set &A,set &B,set &C);
30. void set-difference(set &A,set &B,set &C);
Como en los otros contenedores STL vistos, una clase iterator per-
mite recorrer el contenedor. Los iterators soportan los operadores de
comparación == y !=.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 251
C AP ÍTULO 4. C ONJUNTOS / Sección 4.1. Introducción a los conjuntos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 252
C AP ÍTULO 4. C ONJUNTOS / Sección 4.1. Introducción a los conjuntos
1: t=?
gen[0]={1,2,3}
B0 2: p=?
kill[0]={4,5,6,7,8,9}
3: q=?
B2 q<=p? gen[2]=kill[2]={}
no gen[3]={6}
B3 6: t=p; kill[3]={1,9}
si
B4 7: p=q; gen[4]={7,8}
8: q=t; kill[4]={2,3,4,5}
si
B5 p%q==0? gen[5]=kill[5]={}
no gen[6]=kill[6]={}
B6 cout << q;
B7 9: t=p%q; gen[7]={9}
kill[7]={1,6}
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 253
C AP ÍTULO 4. C ONJUNTOS / Sección 4.1. Introducción a los conjuntos
defin[j]
gen[j] kill[j]
Bj
defout[j]
Figura 4.2: Ecuación de balance para las asignaciones que llegan y salen de
un bloque.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 254
C AP ÍTULO 4. C ONJUNTOS / Sección 4.1. Introducción a los conjuntos
En este análisis los conjuntos gen[j] y kill[j] pueden por simple ob-
servación del código, mientras que los defin[j] y defout[j] son el resul-
tado buscado. Para obtenerlos debemos escribir una “ecuación de balance
de asignaciones” en el bloque, a saber (ver figura 4.2)
la cual expresa que las asignaciones que salen del bloque son aquellas que
llegan, más las generadas en el bloque menos las que son eliminadas en el
mismo.
Ahora consideremos las asignaciones que llegan al B4 , es decir
defin[4]. Estas pueden proceder o bien del bloque B3 o bien del B7 , es
decir
defin[4] = defout[3] ∪ defout[7] (4.6)
En general tenemos que
X
defin[j] = defout[m] (4.7)
m∈ent[j]
ent[0]=∅
ent[1]={0}
ent[2]={1}
ent[3]={2}
(4.8)
ent[4]={3, 7}
ent[5]={2, 4}
ent[6]={5}
ent[7]={5}
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 255
C AP ÍTULO 4. C ONJUNTOS / Sección 4.1. Introducción a los conjuntos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 256
C AP ÍTULO 4. C ONJUNTOS / Sección 4.1. Introducción a los conjuntos
defin[j]k ⊆ defin[j]k+1
(4.11)
defout[j]k ⊆ defout[j]k+1
Las Tablas 4.1 y 4.2 muestran el avance de las iteraciones hasta llegar
a convergencia. La iteración 6 coincide con la 5, por lo tanto se comprueba
que el algoritmo ha convergido.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 257
C AP ÍTULO 4. C ONJUNTOS / Sección 4.1. Introducción a los conjuntos
5. vector<set> &ent) {
6. int nblock = [Link]();
7. set tmp;
8. bool cambio=true;
9. while (cambio) {
10. for (int j=0; j<nblock; j++) {
11. defin[j].clear();
12. iterator-t p = ent[j].begin();
13. while (p!=ent[j].end()) {
14. int k = ent[j].retrieve(p);
15. set-union(defin[j],defout[k],tmp);
16. defin[j] = tmp;
17. p = ent[j].next(p);
18. }
19. }
20. cambio=false;
21. for (int j=0; j<nblock; j++) {
22. int out-prev = defout[j].size();
23. set-union(defin[j],gen[j],tmp);
24. set-difference(tmp,kill[j],defout[j]);
25. if (defout[j].size()!=out-prev) cambio=true;
26. }
27. }
28. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 258
C AP ÍTULO 4. C ONJUNTOS / Sección 4.2. Implementación por vectores de bits
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 259
C AP ÍTULO 4. C ONJUNTOS / Sección 4.2. Implementación por vectores de bits
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 260
C AP ÍTULO 4. C ONJUNTOS / Sección 4.2. Implementación por vectores de bits
Código 4.5: Funciones auxiliares para definir conjuntos dentro de las letras
a-z y A-Z. [Archivo: setbasadefs.h]
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 261
C AP ÍTULO 4. C ONJUNTOS / Sección 4.2. Implementación por vectores de bits
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 262
C AP ÍTULO 4. C ONJUNTOS / Sección 4.3. Implementación con listas
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 263
C AP ÍTULO 4. C ONJUNTOS / Sección 4.3. Implementación con listas
Tabla 4.3: Tabla de equivalencia entre las operaciones del TAD conjunto y el
TAD correspondencia.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 264
C AP ÍTULO 4. C ONJUNTOS / Sección 4.3. Implementación con listas
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 265
C AP ÍTULO 4. C ONJUNTOS / Sección 4.3. Implementación con listas
Si
xja < xkb (4.15)
entonces en el siguiente paso pa avanza a xj+1
a . Los elementos de B antes
de pb siguen satisfaciendo
con lo cual la condición sobre pa se sigue cumpliendo. Por otra parte, ahora
j
a los elementos antes de pa se agregó xa con lo cual tenemos antes de pa
que cumplen la condición requerida por (4.14) y (4.15). Puede verse las
j
condiciones también se siguen satisfaciendo si xa > xkb y avanzamos pb,
j
o si xa = xkb y avanzamos ambas posiciones.
Para cualquiera de las operaciones binarias inicializamos los iterators
con pa=[Link]() y pb=[Link]() y los vamos avanzando con el mecan-
ismo explicado, es decir siempre el menor o los dos cuando son iguales. El
proceso se detiene cuando alguno de los iterators llega al final de su con-
junto. En cada paso alguno de los iterators avanza, de manera que es claro
que en un número finito de pasos alguno de los iterators llegará al fin, de
hecho en menos de na + nb pasos. Las posiciones pa y pb recorren todos
los elementos de alguno de los dos conjuntos, mientras que en el otro puede
quedar un cierto “resto”, es decir una cierta cantidad de elementos al final de
la lista.
Ahora consideremos la operación de set_union(A,B,C). Debemos ase-
gurarnos de insertar todos los elementos de A y B , pero una sola vez y en
forma ordenada. Esto se logra si en cada paso insertamos en el fin de C el
elemento menor de xa y xb (si son iguales se inserta una sola vez). Efecti-
vamente, si en un momento xa < xb entonces, por lo discutido previamente
xa seguramente no está en B y podemos insertarlo en C , ya que en el
siguiente paso pa avanzará, dejándolo atrás, con lo cual seguramente no lo
insertaremos nuevamente. Además en pasos previos xa no puede haber si-
do insertado ya que si era el menor pa habrı́a avanzado dejándolo atrás y
si era el mayor no habrı́a sido insertado. El caso en que son iguales puede
analizarse en forma similar. Puede verse que los elementos de C quedan
ordenados, ya que de xa y xb siempre avanzamos el menor. Una vez que
uno de los iterators (digamos pa) llegó al final, si quedan elementos en B (el
“resto” ) entonces podemos insertarlos directamente al fin de C ya que está
garantizado que estos elementos no pueden estar en A.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 266
C AP ÍTULO 4. C ONJUNTOS / Sección 4.3. Implementación con listas
xa =1, xb =3,
xa =3, xb =3, inserta 3
xa =5, xb =5, inserta 5
xa =7, xb =7, inserta 7
xa =10, xb =9,
xa =10, xb =10, inserta 10
pa llega a [Link]()
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 267
C AP ÍTULO 4. C ONJUNTOS / Sección 4.3. Implementación con listas
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 268
C AP ÍTULO 4. C ONJUNTOS / Sección 4.3. Implementación con listas
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 269
C AP ÍTULO 4. C ONJUNTOS / Sección 4.4. Interfaz avanzada para conjuntos
Método T (N )
retrieve(p), insert(x), erase(x), clear(), O(n)
find(x), lower bound(x), set union(A,B,C),
set intersection(A,B,C),
set difference(A,B,C),
erase(p), begin(), end(), O(1)
Tabla 4.4: Tiempos de ejecución de los métodos del TAD conjunto imple-
mentado con listas ordenadas.
1. template<class T>
2. class set {
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 270
C AP ÍTULO 4. C ONJUNTOS / Sección 4.4. Interfaz avanzada para conjuntos
3. private:
4. /* . . . */
5. public:
6. class iterator {
7. friend class set;
8. T & operator*();
9. T *operator->();
10. bool operator!=(iterator q);
11. bool operator==(iterator q);
12. }
13. set() {}
14. set(const set &A) : L(A.L) {}
15. ˜set() {}
16. set &operator=(set<T> &);
17. iterator lower-bound(T t);
18. pair<iterator,bool> insert(T x);
19. void erase(iterator p);
20. int erase(T x);
21. void clear();
22. iterator find(T x);
23. iterator begin();
24. iterator end();
25. int size();
26. };
27.
28. template<class T>
29. void set-union(set<T> &A,set<T> &B,set<T> &C);
30.
31. template<class T>
32. void set-intersection(set<T> &A,set<T> &B,set<T> &C);
33.
34. template<class T>
35. void set-difference(set<T> &A,set<T> &B,set<T> &C);
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 271
C AP ÍTULO 4. C ONJUNTOS / Sección 4.4. Interfaz avanzada para conjuntos
1. template<class T>
2. class set {
3. private:
4. list<T> L;
5. public:
6. typedef typename list<T>::iterator iterator;
7. typedef pair<iterator,bool> pair-t;
8. set() {}
9. set(const set &A) : L(A.L) {}
10. ˜set() {}
11. iterator lower-bound(T t) {
12. iterator p = [Link]();
13. while (p!=[Link]() && t>*p) p++;
14. return p;
15. }
16. pair-t insert(T x) {
17. iterator p = lower-bound(x);
18. if(p==end() | | *p!=x) {
19. p = [Link](p,x);
20. return pair-t(p,true);
21. } else {
22. return pair-t(end(),false);
23. }
24. }
25. void erase(iterator p) { [Link](p); }
26. int erase(T x) {
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 272
C AP ÍTULO 4. C ONJUNTOS / Sección 4.4. Interfaz avanzada para conjuntos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 273
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 274
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
1. int h(string t) {
2. return t[0]-’a’;
3. }
En este caso está garantizado que los números de cubetas devueltos por
h() están en el rango [0, B). En la práctica, el programador de la clase puede
proveer funciones de hash para los tipos más usuales (como int, double,
string...) dejando la posibilidad de que el usuario defina la función de hash
para otros tipos, o también para los tipos básicos si considera que los que
el provee son más eficientes (ya veremos cuáles son los requisitos para una
buena función de hash). Asumiremos siempre que el tiempo de ejecución
de la función de dispersión es O(1). Para mayor seguridad, asignamos al
elemento t la cubeta b=h(t)%B, de esta forma está siempre garantizado que
b está en el rango [0, B).
Básicamente, las cubetas son guardadas en un arreglo de cubetas
(vector<elem_t> v(B)). Para insertar un elemento, simplemente calculam-
os la cubeta a usando la función de dispersión y guardamos el elemento
en esa cubeta. Para hacer un find(x) o erase(x), calculamos la cubeta
y verificamos si el elemento está en la cubeta o no. De esta forma tanto las
inserciones como las supresiones son O(1). Este costo tan bajo es el interés
principal de estas estructuras.
Pero normalmente el número de cubetas es mucho menor que el número
de elementos del conjunto universal N (en muchos casos este último es in-
finito). En el ejemplo de los strings, todos los strings que empiezan con a van
a la primera cubeta. Si un elemento es insertado y la cubeta correspondiente
ya está ocupada decimos que hay una “colisión” y no podemos insertar el el-
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 275
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 276
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 277
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 278
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 279
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 280
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
Tabla 4.5: Tiempos de ejecución de los métodos del TAD diccionario imple-
mentado con tablas de dispersión abiertas.
next_aux().
Si ésta función de dispersión es usada con strings que provienen por ejem-
plo de palabras encontradas encontradas en texto usual en algún lenguaje
como español, entonces es probable que haya muchas más palabras que
comiencen con la letra a y por lo tanto vayan a la cubeta 97 (el valor ASCII
de a) que con la letra x (cubeta 120).
1. int h2(string s) {
2. int v = 0;
3. for (int j=0; j<[Link](); j++) {
4. v += s[j];
5. v = v % 256;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 281
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
6. }
7. return v;
8. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 282
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
Insertado={1,13,4,1,24}
Insertado={1,13,4,1,24,12,15,34,4,44,22,15,17}
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 283
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 284
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
Nro. de Probabilidad
intentos de ocurrencia
infructuosos P (m) =
(m) αm (1 − α)
0 0.250000
1 0.187500
2 0.140625
3 0.105469
4 0.079102
5 0.059326
6 0.044495
7 0.033371
8 0.025028
9 0.018771
10 0.014078
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 285
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
P (m) = αm (1 − α) (4.20)
B−1
X
hmi = m P (m)
m=0
(4.21)
B−1
X
= m αm (1 − α)
m=0
d m
mαm = α α (4.22)
dα
de manera que
∞
X d m
hmi = (1 − α) α α
dα
m=0
∞
!
d X
= α (1 − α) αm
dα (4.23)
k=0
d 1
= α (1 − α)
dα 1−α
α
=
1−α
Por ejemplo, en el caso de tener B = 100 cubetas y α = 0.9 (90 % de
cubetas ocupadas) el número de intentos medio es de hmi = 0.9/(1 −
0.9) = 9.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 286
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
1 α
Z
hmn.e. i = hmi dα0 (4.24)
α α0 = 0
1 α α0
Z
hmn.e. i = dα0
α α0 = 0 1 − α0
1 α
Z
1
= − 1 dα0
α α0 = 0 1 − α0 (4.25)
1 α
= − log(1 − α0 ) − α0 α0 = 0
α
1
= − log(1 − α) − 1
α
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 287
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
10
0
0 0.2 0.4 0.6 0.8 1
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 288
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 289
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
la nueva tabla tendrá todos los elementos undef, y las inserciones no gener-
an elementos deleted, la tabla reinsertada estará libre de deleted’s. Esta
tarea es O(B + n) y se ve compensada por el tiempo que se ahorrará en
unas pocas operaciones.
Para determinar cuando se dispara la reinserción se controla la tasa de
suprimidos que existe actualmente
ndel
ß= (4.27)
B
Cuando ß ≈ 1 − α quiere decir que de la fracción de cubetas no ocupadas
1 − α, una gran cantidad de ellas dada por la fracción ß está ocupada por
suprimidos, degradando la eficiencia de la tabla. Por ejemplo, si α = 0.5 y
ß = 0.45 entonces 50 % de las cubetas está ocupada, y del restante 50 %
el 45 % está ocupado por deleted. En esta situación la eficiencia de la tabla
es equivalente una con un 95 % ocupado.
3 13 3 13 3 13 3 13
4 4 4 4 4 <undef> 4 24
5 24 5 <undef> 5 <undef> 5 <undef>
6 <undef> 6 <undef> 6 <undef> 6 <undef>
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 290
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 291
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 292
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
2510 = 110012
1310 = 011012 (4.29)
2510 ⊕ 1310 = 101002
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 293
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
4.
5. int linear-redisp-fun(int j) { return j; }
6.
7. class hash-set {
8. private:
9. hash-set(const hash-set&) {}
10. hash-set& operator=(const hash-set&) {}
11. int undef, deleted;
12. hash-fun h;
13. redisp-fun rdf;
14. int B;
15. int count;
16. std::vector<key-t> v;
17. std::stack<key-t> S;
18. iterator-t locate(key-t x,iterator-t &fdel) {
19. int init = h(x);
20. int bucket;
21. bool not-found = true;
22. for (int i=0; i<B; i++) {
23. bucket = (init+rdf(i)) % B;
24. key-t vb = v[bucket];
25. if (vb==x | | vb==undef) break;
26. if (not-found && vb==deleted) {
27. fdel=bucket;
28. not-found = false;
29. }
30. }
31. if (not-found) fdel = end();
32. return bucket;
33. }
34. iterator-t next-aux(iterator-t bucket) {
35. int j=bucket;
36. while(j!=B && (v[j]==undef | | v[j]==deleted)) {
37. j++;
38. }
39. return j;
40. }
41. public:
42. hash-set(int B-a,hash-fun h-a,
43. key-t undef-a,key-t deleted-a,
44. redisp-fun rdf-a=&linear-redisp-fun)
45. : B(B-a), undef(undef-a), v(B,undef-a), h(h-a),
46. deleted(deleted-a), rdf(rdf-a), count(0)
47. {}
48. std::pair<iterator-t, bool>
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 294
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
49. insert(key-t x) {
50. iterator-t fdel;
51. int bucket = locate(x,fdel);
52. if (v[bucket]==x)
53. return std::pair<iterator-t,bool>(bucket,false);
54. if (fdel!=end()) bucket = fdel;
55. if (v[bucket]==undef | | v[bucket]==deleted) {
56. v[bucket]=x;
57. count++;
58. return std::pair<iterator-t,bool>(bucket,true);
59. } else {
60. std::cout << "Tabla de dispersion llena!!\n";
61. abort();
62. }
63. }
64. key-t retrieve(iterator-t p) { return v[p]; }
65. iterator-t find(key-t x) {
66. iterator-t fdel;
67. int bucket = locate(x,fdel);
68. if (v[bucket]==x) return bucket;
69. else return(end());
70. }
71. int erase(const key-t& x) {
72. iterator-t fdel;
73. int bucket = locate(x,fdel);
74. if (v[bucket]==x) {
75. v[bucket]=deleted;
76. count--;
77. // Trata de purgar elementos ‘deleted’
78. // Busca el siguiente elemento ‘undef’
79. int j;
80. for (j=1; j<B; j++) {
81. op-count++;
82. int b = (bucket+j) % B;
83. key-t vb = v[b];
84. if (vb==undef) break;
85. [Link](vb);
86. v[b]=undef;
87. count--;
88. }
89. v[bucket]=undef;
90. // Va haciendo erase/insert de los elementos
91. // de atras hacia adelante hasta que se llene
92. // ‘bucket’
93. while (![Link]()) {
94. op-count++;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 295
C AP ÍTULO 4. C ONJUNTOS / Sección 4.5. El diccionario
95. insert([Link]());
96. [Link]();
97. }
98. return 1;
99. } else return 0;
100. }
101. iterator-t begin() {
102. return next-aux(0);
103. }
104. iterator-t end() { return B; }
105. iterator-t next(iterator-t p) {
106. return next-aux(++p);
107. }
108. void clear() {
109. count=0;
110. for (int j=0; j<B; j++) v[j]=undef;
111. }
112. int size() { return count; }
113. };
En el código 4.13 se puede ver una posible implementación del TAD dic-
cionario con tablas de dispersión cerrada y redispersión continua.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 296
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
Una forma muy eficiente de representar conjuntos son los árboles bina-
rios de búsqueda (ABB). Un árbol binario es un ABB si es vacı́o (Λ) o:
Todos los elementos en los nodos del subárbol izquierdo son menores
que el nodo raı́z.
Todos los elementos en los nodos del subárbol derecho son mayores
que el nodo raı́z.
Los subárboles del hijo derecho e izquierdo son a su vez ABB.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 297
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
10
5 14
7 12 18
15
Figura 4.6: Ejemplos de árboles binarios de búsqueda
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 298
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
6. max = -INT-MAX;
7. if (n==[Link]()) return true;
8.
9. l = [Link]();
10. r = [Link]();
11.
12. if (!abb-p(T,l,minl,maxl) | | maxl>*n) return false;
13. if (!abb-p(T,r,minr,maxr) | | minr<*n) return false;
14.
15. min = (l==[Link]()? *n : minl);
16. max = (r==[Link]()? *n : maxr);
17. return true;
18. }
19.
20. bool abb-p(aed::btree<int> &T) {
21. if ([Link]()) return false;
22. int min,max;
23. return abb-p(T,[Link](),min,max);
24. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 299
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
min 10 max
5 14
7 12 18
15
Figura 4.7:
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 300
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 301
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
d
1 X l
hli = 2 l (4.35)
n
l=0
2l = eαl (4.36)
α=log 2
d αl
e = l eαl . (4.37)
dα
Entonces
d
1 X l
hli = 2 l
n
l=0
d
1 X deαl
= , (4.38)
n dα α=log 2
l=0
" d #
1 d X αl
= e .
n dα
l=0 α=log 2
d
X eα(d+1) − 1
eαl = . (4.39)
eα − 1
l=0
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 302
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
Figura 4.8: El balanceo del árbol depende del orden en que son ingresados
los elementos.
Notar que el balanceo del árbol depende del orden en que son insertados
los elementos en el árbol. En la figura 4.8 se muestran los árboles obtenidos
al insertar los enteros del 1 al 7, primero en forma ascendente, después de-
scendente y finalmente en el orden {4, 2, 6, 1, 3, 5, 7}. Vemos que en los dos
primeros casos el desbalanceo es total, el árbol degenera en dos listas por
hijo derecho en el primer caso y por hijo izquierdo en el segundo. En el tercer
caso los elementos son ingresados en forma desordenada y el balanceo es
el mejor posible. El árbol resultante es un arbol completo hasta el nivel 3.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 303
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
con lo cual el caso de inserción aleatoria está muy cercano al mejor caso.
find 15 find 11
10 10
5 14 5 14
7 12 18 7 12 18
15 Λ 15
Figura 4.9:
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 304
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
borrar 7,18
10 10
5 14 5 14
un solo hijo
7 12 18 12 16
sin hijos
15 17
16
15 17
Figura 4.10: Supresión en ABB cuando el nodo no tiene o tiene un solo hijo.
borrar 10
x sale
10 12
5 16 5 16
minr
7 12 18 7 14 18
14 13 15
13 15
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 305
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
5 16 5 16 16 30
p
7 12 18 7 12 18 12 18 25 35
14 14 14
p p
13 15 13 15 13 15
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 306
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
1. // Forward declarations
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 307
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
2. template<class T>
3. class set;
4. template<class T> void
5. set-union(set<T> &A,set<T> &B,set<T> &C);
6. template<class T> void
7. set-intersection(set<T> &A,set<T> &B,set<T> &C);
8. template<class T> void
9. set-difference(set<T> &A,set<T> &B,set<T> &C);
10.
11. template<class T>
12. class set {
13. private:
14. typedef btree<T> tree-t;
15. typedef typename tree-t::iterator node-t;
16. tree-t bstree;
17. node-t min(node-t m) {
18. if (m == [Link]()) return [Link]();
19. while (true) {
20. node-t n = [Link]();
21. if (n==[Link]()) return m;
22. m = n;
23. }
24. }
25.
26. void set-union-aux(tree-t &t,node-t n) {
27. if (n==[Link]()) return;
28. else {
29. insert(*n);
30. set-union-aux(t,[Link]());
31. set-union-aux(t,[Link]());
32. }
33. }
34. void set-intersection-aux(tree-t &t,
35. node-t n, set &B) {
36. if (n==[Link]()) return;
37. else {
38. if ([Link](*n)!=[Link]()) insert(*n);
39. set-intersection-aux(t,[Link](),B);
40. set-intersection-aux(t,[Link](),B);
41. }
42. }
43. void set-difference-aux(tree-t &t,
44. node-t n, set &B) {
45. if (n==[Link]()) return;
46. else {
47. if ([Link](*n)==[Link]()) insert(*n);
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 308
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
48. set-difference-aux(t,[Link](),B);
49. set-difference-aux(t,[Link](),B);
50. }
51. }
52. int size-aux(tree-t t,node-t n) {
53. if (n==[Link]()) return 0;
54. else return 1+size-aux(t,[Link]())
55. +size-aux(t,[Link]());
56. }
57. public:
58. class iterator {
59. private:
60. friend class set;
61. node-t node;
62. tree-t *bstree;
63. iterator(node-t m,tree-t &t)
64. : node(m), bstree(&t) {}
65. node-t next(node-t n) {
66. node-t m = [Link]();
67. if (m!=bstree->end()) {
68. while (true) {
69. node-t q = [Link]();
70. if (q==bstree->end()) return m;
71. m = q;
72. }
73. } else {
74. // busca el padre
75. m = bstree->begin();
76. if (n==m) return bstree->end();
77. node-t r = bstree->end();
78. while (true) {
79. node-t q;
80. if (*n<*m) { q = [Link](); r=m; }
81. else q = [Link]();
82. if (q==n) break;
83. m = q;
84. }
85. return r;
86. }
87. }
88. public:
89. iterator() : bstree(NULL) { }
90. iterator(const iterator &n)
91. : node([Link]), bstree([Link]) {}
92. iterator& operator=(const iterator& n) {
93. bstree=[Link];
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 309
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 310
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
141. [Link]([Link](),[Link]());
142. p = [Link](p);
143. [Link](p,[Link]());
144. } else {
145. node-t r = min(qr);
146. T minr = *r;
147. erase(iterator(r,bstree));
148. *p = minr;
149. }
150. }
151. int erase(T x) {
152. iterator q = find(x);
153. int ret;
154. if (q==end()) ret = 0;
155. else {
156. erase(q);
157. ret = 1;
158. }
159. return ret;
160. }
161. void clear() { [Link](); }
162. iterator find(T x) {
163. node-t m = [Link]();
164. while (true) {
165. if (m == [Link]())
166. return iterator(m,bstree);
167. if (x<*m) m = [Link]();
168. else if (x>*m) m = [Link]();
169. else return iterator(m,bstree);
170. }
171. }
172. iterator begin() {
173. return iterator(min([Link]()),bstree);
174. }
175. iterator end() {
176. return iterator([Link](),bstree);
177. }
178. int size() {
179. return size-aux(bstree,[Link]()); }
180. friend void
181. set-union<T>(set<T> &A,set<T> &B,set<T> &C);
182. friend void
183. set-intersection<>(set<T> &A,set<T> &B,set<T> &C);
184. friend void
185. set-difference<>(set<T> &A,set<T> &B,set<T> &C);
186. friend void f();
187. };
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 311
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
188.
189. template<class T> void
190. set-union(set<T> &A,set<T> &B,set<T> &C) {
191. [Link]();
192. [Link]-union-aux([Link],[Link]());
193. [Link]-union-aux([Link],[Link]());
194. }
195.
196. template<class T> void
197. set-intersection(set<T> &A,set<T> &B,set<T> &C) {
198. [Link]();
199. [Link]-intersection-aux([Link],
200. [Link](),B);
201. }
202.
203. // C = A - B
204. template<class T> void
205. set-difference(set<T> &A,set<T> &B,set<T> &C) {
206. [Link]();
207. [Link]-difference-aux([Link],
208. [Link](),B);
209. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 312
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 313
C AP ÍTULO 4. C ONJUNTOS / Sección 4.6. Conjuntos con árboles binarios de búsqueda
Tabla 4.7: Tiempos de ejecución de los métodos del TAD set implementado
con ABB.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 314
Capı́tulo 5
Ordenamiento
5.1. Introducción
315
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.1. Introducción
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 316
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.1. Introducción
mayor: (a b) = (b a)
equivalencia: (a ≡ b) = !(a b) && !(b a)
(5.4)
menor o equivalente: (a b) = !(b a)
mayor o equivalente: (a b) = !(a b)
También en algunos lenguajes (e.g. Perl) es usual definir una función
int cmp(T x,T y) asociada a una dada relación de orden que retorna
1, 0 o -1 dependiendo si x y , x ≡ y o x y . En ese caso, el valor de
cmp(x,y) se puede obtener de
cmp(x, y) = (y x) − (x y) (5.5)
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 317
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.1. Introducción
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 318
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.1. Introducción
orden es fuerte.
Recordemos que en la serie ASCII las mayúsculas están antes que las
minúsculas, las minúsculas a-z están en el rango 97-122 mientras que las
mayúsculas A-Z están en el rango 65-90.
1. template<class T>
2. bool less(T &x,T &y) {
3. return x<y;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 319
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.1. Introducción
4. }
Código 5.3: Template de las STL que provee un predicado binario al oper-
ador intrı́nseco “<” del tipo T. [Archivo: lesst.h]
1. char tolower(char c) {
2. if (c>=’A’ && c<=’Z’) c += ’a’-’A’;
3. return c;
4. }
5.
6. bool string-less-ci(const string &a,
7. const string &b) {
8. int na = [Link]();
9. int nb = [Link]();
10. int n = (na>nb ? nb : na);
11. for (int j=0; j<n; j++) {
12. char
13. aa = tolower(a[j]),
14. bb = tolower(b[j]);
15. if (aa < bb) return true;
16. else if (bb < aa) return false;
17. }
18. return na<nb;
19. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 320
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.1. Introducción
5.1.4. Estabilidad
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 321
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.1. Introducción
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 322
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.2. Métodos de ordenamiento lentos
sort() no se puede aplicar a cualquier contenedor sino que tiene que ser
un “contenedor de acceso aleatorio”, es decir un contenedor en el cual los
iteradores soportan operaciones de aritmética entera, es decir si tenemos
un iterador p, podemos hacer p+j (avanzar el iterador j posiciones, en tiem-
po O(1)). Los operadores de acceso aleatorio en las STL son vector<> y
deque<>.
El ordenamiento se realiza mediante la relación de orden operator< del
tipo T del cual están compuestos los elementos del contenedor. Si el tipo T
es una clase definida por el usuario, este debe sobrecargar el operator<.
La segunda versión toma un argumento adicional que es la función
de comparación. Esto puede ser útil cuando se quiere ordenar un con-
tenedor por un orden diferente a operator< o bien T no tiene definido
operator<. Las STL contiene en el header functional unos templates
less<T>, greater<T> que devuelven funciones de comparación basados en
operator< y operator> respectivamente. Por ejemplo, si queremos ordenar
de mayor a menor un vector de enteros, basta con hacer
[copy]
1. vector<int> v;
2. // Inserta elementos en v. . .
3. sort([Link](), [Link](), greater<int>);
Usar less<int> es totalmente equivalente a usar la versión
sort(first,last) es decir sin función de comparación.
Si queremos ordenar un vector de strings por orden lexicográfico inde-
pendientemente de minúsculas/mayúsculas debemos hacer
[copy]
1. vector<string> v;
2. // Inserta elementos en v. . .
3. sort([Link](), [Link](), string-less-ci);
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 323
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.2. Métodos de ordenamiento lentos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 324
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.2. Métodos de ordenamiento lentos
En este método (ver código 5.6) también hay un doble lazo. En el la-
zo sobre j el rango [0, j) está ordenado e insertamos el elemento j en el
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 325
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.2. Métodos de ordenamiento lentos
En este método (ver código 5.7) también hay un doble lazo (esta es una
caracterı́stica de todos los algoritmos lentos). En el lazo j se elige el menor
del rango [j, N ) y se intercambia con el elemento en la posición j .
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 326
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.2. Métodos de ordenamiento lentos
Por otra parte selección puede ser una opción interesante cuando se
debe minimizar el número de intercambios. Sin embargo, veremos en la sigu-
iente sección que, ordenando “indirectamente” los elementos, cualquier se
puede lograr que cualquier método de ordenación haga sólo n intercambios.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 327
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.3. Ordenamiento indirecto
5.2.5. Estabilidad
Una forma de verificar si un algoritmo de ordenamiento es estable o no es
controlar que la estabilidad no se viole en ningún intercambio. Por ejemplo
en el caso del método de la burbuja la estabilidad se mantiene ya que el
intercambio se realiza sólo en las lı́neas 9–11. Pero como el intercambio
sólo se realiza si *(first+k) es estrictamente menor que *(first+k-1)
y los dos elementos están en posiciones consecutivas el intercambio nunca
viola la estabilidad.
En el caso del método de inserción pasa algo similar. En las
lı́neas 11–14 el elemento *(first+j) es intercambiado con todo el ran-
go [first+k,first+j) que son elementos estrictamente mayores que
*(first+j).
En cambio, en el caso del método de selección, después de buscar la
posición del mı́nimo en el lazo de las lı́neas 12–15, el intercambio se re-
aliza en las lı́neas 16–18. Pero al realizar este intercambio, el elemento
*(first+j), que va a ir a la posición min, puede estar cambiando de posi-
ción relativa con elementos equivalentes en el rango (first+j,min), violan-
do la estabilidad.
1. template<class T>
2. void apply-perm(typename std::vector<T>::iterator first,
3. typename std::vector<T>::iterator last,
4. std::vector<int> &indx) {
5. int size = last-first;
6. assert([Link]()==size);
7. int sorted = 0;
8. T tmp;
9. while (sorted<size) {
10. if(indx[sorted]!=sorted) {
11. int k = sorted;
12. tmp = *(first+k);
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 328
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.3. Ordenamiento indirecto
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 329
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.3. Ordenamiento indirecto
v={ 3 2 7 2 8 1 0 9 4 0 }
indx={ 6 9 5 1 3 0 8 2 4 7 }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 330
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
w
quicksort(w,0,n)
l=particiona(w,0,n,v)
<v >=v
quicksort(w,0,l) l quicksort(w,l,n)
ordenado ordenado
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 331
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
1. void quicksort(w,j1,j2) {
2. // Ordena el rango [j1,j2) de ‘w’
3. if (n==1) return;
4. // elegir pivote v . . .
5. l = partition(w,j1,j2,v);
6. quicksort(w,j1,l);
7. quicksort(w,l,j2);
8. }
3 1 4 1 5 9 2 6 5 3
particiona(v=3)
2 1 1 4 5 9 3 6 5 3
part(v=2) part(v=5)
1 1 2 4 3 3 9 6 5 5
part(v=4) part(v=9)
3 3 4 5 6 5 9
part(v=6)
5 5 6
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 332
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 333
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
esto) Entonces
T (n) = Tpart−piv (n) + T (n1 ) + T (n2 )
(5.12)
= cn + T (n/2) + T (n/2)
Llamando T (1) = d y aplicando sucesivamente
T (2) = c + 2T (1) = c + 2d
T (4) = 4c + 2T (2) = 3 · 4c + 4d
T (8) = 8c + 2T (4) = 4 · 8c + 8d
T (16) = 16c + 2T (8) = 5 · 16c + 16d (5.13)
.. ..
. = .
T (2p ) = (p + 1)n(c + d)
pero como n = 2p entonces p = log2 n y por lo tanto
T (n) = O(n log n). (5.14)
Por otro lado el peor caso es cuando la partición es muy desbalanceada,
es decir n1 = 1 y n2 = n − 1 o viceversa. En este caso tenemos
T (n) = cn + T (1) + T (n − 1)
(5.15)
= cn + d + T (n − 1)
y aplicando sucesivamente,
T (2) = 2c + 2d
T (3) = 3c + d + (2c + 2d) = 5c + 3d
T (4) = 4c + d + (5c + 3d) = 9c + 4d
T (5) = 5c + d + (9c + 4d) = 14c + 5d (5.16)
.. ..
. = .
n(n + 1)
T (n) = − 2 c + nd = O(n2 )
2
El peor caso ocurre, por ejemplo, si el vector está inicialmente ordenado y
usando como estrategia para el pivote el mayor de los dos primeros distintos.
Si tenemos en v, por ejemplo los enteros 1 a 100 ordenados, que podemos
denotar como un rango [1, 100], entonces el pivote serı́a inicialmente 2. La
partición izquierda tendrı́a sólo al 1 y la derecha serı́a el rango [2, 99]. Al
particionar [2, 99] tendrı́amos el pivote 3 y las particiones serı́an 2 y [3, 99]
(ver figura 5.4). Puede verificarse que lo mismo ocurrirı́a si el vector está
ordenado al revés.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 334
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
1 2 3 4 5 ... 100
particiona(v=2)
1 2 3 4 5 ... 100
part(v=3)
2 3 4 5 ... 100
part(v=4)
3 4 5 6 ... 100
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 335
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
los elementos, para distribuciones más uniformes de los elementos tal vez,
es posible que el promedio sea un elección razonable. De todas formas el
promedio es un concepto que es sólo aplicable a tipos para los cuales las
operaciones algebraicas tienen sentido. No es claro como podrı́amos calcu-
lar el promedio de una serie de cadenas de caracteres.
Volviendo En el caso k = 2 tomamos de los dos primeros elementos
distintos el que está en la posición 1, es decir el mayor de los dos, de manera
que k = 2 equivale a la estrategia propuesta en las secciones anteriores. El
caso del balance perfecto (5.12) se obtiene tomando como pivote la mediana
de todo el vector, es decir k = n.
Para una dada estrategia de elección del pivote podemos preguntarnos,
cual es la probabilidad P (n, n1 ) de que el pivote genere subparticiones de
longitud n1 y n − n1 , con 1 ≤ n1 < n. Asumiremos que los elementos
del vector están distribuidos aleatoriamente. Si, por ejemplo, elegimos como
pivote el primer elemento del vector (o sea la mediana de los primeros k = 1
distintos), entonces al ordenar el vector este elemento puede terminar en
cualquier posición del vector, ordenado de manera que P (n, n1 ) = 1/(n−1)
para cualquier n1 = 1, .., n − 1. Por supuesto, recordemos que esta no es
una elección aceptable para el pivote en la práctica ya que no garantizarı́a
que ambas particiones sean no nulas. Si el primer elemento resultara ser
el menor de todos, entonces la partición izquierda resultarı́a ser nula. En la
figura 5.6 vemos esta distribución de probabilidad. Para que la curva sea
independiente de n hemos graficado nP (n, n1 ) en función de n1 /n.
a b x x
a x b x
a x x b
b a x x
x a b x
x a x b
b x a x
x b a x
x x a b
b x x a
x b x a
x x b a
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 336
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
por simplicidad que todos los elementos son distintos. Sean a y b los dos
primeros elementos del vector, entonces después de ordenar los elementos
estos elementos pueden terminar en cualquiera de las posiciones j, k del
vector con la misma probabilidad. Si la longitud del vector es n = 4, en-
tonces hay n(n − 1) = 12 posibilidades esencialmente distintas como se
muestra en la figura 5.5.
Notemos que las primeras tres corresponden a que a termine en la posi-
ción 0 (base 0) y b en cada una de las tres posiciones restantes. Las sigu-
ientes 3 corresponden a a en la posición 1 (base 0), y ası́ siguiendo. En el
primero de los doce casos el pivote serı́a b y terminarı́a en la posición 1.
Revisando todos los posibles casos tenemos que en 2 casos (lı́neas 1 y 4)
el pivote termina en la posición 1, en 4 casos (lı́neas 2, 5, 7 y 8) termina en
la posición 2 y en 6 casos (lı́neas 3, 6, 9, 10, 11 y 12) termina en la posición
3. Notemos que en este caso es más probable que el pivote termine en las
posiciones más a la derecha que en las que están más a la izquierda. Por
supuesto esto se debe a que estamos tomando el mayor de los dos. Una for-
ma de contar estas posibilidades es considerar que para que el mayor esté
en la posición j debe ocurrir que a esté en la posición j y b en las posiciones
0 a j − 1, o que b quede en la posición j y a en las posiciones 0 a j − 1, o
sea un total de 2j posibilidades.
Ahora veamos que ocurre si tomamos como estrategia para la elec-
ción del pivote la mediana de los primeros k = 3 distintos. En este caso,
si denotamos los tres primeros distintos como a, b y c, entonces existen
n(n − 1)(n − 2) casos distintos: a en cualquiera de las n posiciones, b en
cualquiera de las n − 1 restantes y c en cualquiera de las n − 2 restantes.
Para que el pivote quede en la posición j deberı́a ocurrir que, por ejemplo, a
quede en la posición j , b en una posición [0, j) y c en una posición (j, n), o
sea j(n − j − 1) posibilidades. Las restantes posibilidades se obtienen por
permutación de los elementos a, b y c, en total
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 337
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
3.0
11
2.5
9
n P(n1,n)
7
2.0
5
3
1.5
k=1
1.0
0.5
0
0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 1.00
n1/n
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 338
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
1000
k=1
k=3
T(n)
mediana
n(log2 n +1)
100
10
1
1 10 n 100
Figura 5.7:
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 339
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
k=4
P(m/n)
k=3
1.5
k=2
1
k=1
0.5
0
6 7 8 9 10 11
m/n
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 340
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
Ni
P (ξ) ≈ . (5.19)
N
Haciendo tender el número de simulaciones en el experimento N a infinito el
miembro derecho tiende a la probabilidad P (x).
Basta con observar la gráfica para ver que a medida que k se incrementa
la distribución de los valores es más concentrada, resultando en una cam-
pana más delgada y puntiaguda. Esto se puede cuantificar buscando cuáles
son los valores de ξ que delimitan el 80 % de los valores centrales. Por ejem-
plo, se observa que para el valor más bajo k = 1 el 80 % de los valores está
entre ξ =8.1 y 9.8 (ancho de la campana 1.7), mientras que para k =4 el
80 % de los valores está entre ξ =7.1 y 7.65 (ancho de la campana 0.55). En
la figura se muestran sombreadas las áreas que representan el 80 % central
de los valores para k = 1 y k = 4.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 341
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
1. int partition(w,first,last,v) {
2. // Particiona el rango [j1,j2) de ‘w’
3. // con respecto al pivote ‘v’
4. if (n==1) return (w[first]<v ? first : last);
5. int middle = (first+last)/2;
6. l1 = partition(w,first,middle,v);
7. l2 = partition(w,middle,last,v);
8. // Intercambia [l1,middle) con [middle,l2)
9. swap(l1,middle,l2);
10. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 342
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
1. template<class T>
2. typename std::vector<T>::iterator
3. partition(typename std::vector<T>::iterator first,
4. typename std::vector<T>::iterator last,
5. bool (*comp)(T&,T&),T &pivot) {
6. typename std::vector<T>::iterator
7. l = first,
8. r = last;
9. r--;
10. while (true) {
11. T tmp = *l;
12. *l = *r;
13. *r = tmp;
14. while (comp(*l,pivot)) l++;
15. while (!comp(*r,pivot)) r--;
16. if (l>r) break;
17. }
18. return l;
19. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 343
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
1. template<class T>
2. int median(typename std::vector<T>::iterator first,
3. typename std::vector<T>::iterator last,
4. std::vector<T> &dif, int k,
5. bool (*comp)(T&,T&)) {
6. typename std::vector<T>::iterator
7. q = first;
8. int ndif=1;
9. dif[0] = *q++;
10. while (q<last) {
11. T val = *q++;
12. int j;
13. for (j=0; j<ndif; j++)
14. // Aca debe compararse por ‘equivalente’
15. // es decir usando comp
16. if (!comp(dif[j],val)
17. && !comp(val,dif[j])) break;
18. if (j==ndif) {
19. dif[j] = val;
20. ndif++;
21. if (ndif==k) break;
22. }
23. }
24. typename std::vector<T>::iterator
25. s = [Link]();
26. bubble-sort(s,s+ndif,comp);
27. return ndif;
28. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 344
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
El algoritmo es O(n) mientras que k sea fijo, esto es, que no crezca con
n. Se recorre el rango y se van introduciendo los nuevos elementos distintos
en el vector dif. Para ver si un elemento es distinto se compara con todos los
elementos previamente insertados en dif. En muy importante que la com-
paración debe realizarse por equivalencia (ver lı́nea 17), y no por igualdad.
Es decir dos elementos a y b son equivalentes si comp(a,b) && comp(b,a)
es verdadero. Para relaciones de orden débiles esto es muy importante ya
que si todos los elementos en el rango son equivalentes pero no iguales
(pensemos en (−1, 1, −1) con la relación de orden (5.3), menor en valor
absoluto), entonces si partition() comparara por igualdad reportarı́a dos
elementos distintos, pero después al particionar una de las particiones resul-
tarı́a vacı́a y entrarı́a en un lazo infinito.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 345
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
5.4.10. Estabilidad
Quick-sort es estable si el algoritmo de partición lo es, y tal cual como
está implementado aquı́, el algoritmo de partición no es estable, ya que al
hacer el intercambio en partition() un elemento puede ser intercambiado
con un elemento equivalente.
1. template<class T>
2. typename std::vector<T>::iterator
3. stable-partition(typename std::vector<T>::iterator first,
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 346
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
partition(first,middle,v) partition(middle,last,v)
x<v x>=v
first l last
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 347
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
rangos están particionados sólo hace falta intercambiar (“swap” ) los rangos
[l1,middle) y [middle,l2). Si el particionamiento de ambos subrangos
fue estable y al hacer el swap mantenemos el orden relativo de los elemen-
tos en cada uno de los rangos, entonces la partición de [first,last) será
estable, ya que los elementos de [middle,l2) son estrictamente mayores
que los de [l1,middle).
n1 n2
l1 k1 middle k1 l2
w=
swap
w=
k2 k2
n2 n1
Figura 5.10:
o recı́procamente, (
k2 + n1 ; si k2 < n2
k1 = (5.21)
k2 − n2 ; si k2 ≥ n2
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 348
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
w= 0 1 2 3 4 5 6 7 8 9
swap
w= 4 5 6 7 8 9 0 1 2 3
Para describir el algoritmo es más simple pensar que tenemos los ele-
mentos del rango [l1,l2) en un vector w de longitud n1+n2. Consideremos
por ejemplo el caso n1 = 4, n2 = 6 (ver figura 5.11). De acuerdo con (5.21)
el elemento que debe ir a la primera posición es el que esta en la posición
4. Podemos guardar el primer elemento (posición 0) en una variable tem-
poraria tmp y traer el 4 a la posición 0. A su vez podemos poner en 4 el
que corresponde allı́, que está inicialmente en la posición 8 y ası́ siguiendo
se desencadenan una serie de intercambios hasta que el que corresponde
poner en la posición a rellenar es el que tenemos guardado en la variable
temporaria (por ahora el 0).
1. T tmp = w[0];
2. int k2 = 0;
3. while (true) {
4. int k1 = (k2<n2 ? k2+n1 : k2-n2);
5. if (k1==0) break;
6. w[k2] = w[k1];
7. k2 = k1;
8. }
9. w[k2] = tmp;
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 349
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
Notar que los elementos que se rotan son exactamente los que fueron rota-
dos previamente, incrementados en uno.
Si n1 = n2 (por ejemplo n1 = n2 = 5), entonces hay cinco rotaciones
de dos elementos,
tmp ← w[0] ← w[5] ← tmp
tmp ← w[1] ← w[6] ← tmp
tmp ← w[2] ← w[7] ← tmp (5.24)
tmp ← w[3] ← w[8] ← tmp
tmp ← w[4] ← w[9] ← tmp
Si n1 divide a n2 (por ejemplo n1 = 2 y n2 = 8), entonces se generan 2
rotaciones de 5 elementos, a saber
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 350
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
14.
15. template<class T>
16. void range-swap(typename std::vector<T>::iterator first,
17. typename std::vector<T>::iterator middle,
18. typename std::vector<T>::iterator last) {
19. int
20. n1 = middle-first,
21. n2 = last-middle;
22. if (!n1 | | !n2) return;
23. int m = gcd(n1,n2);
24. for (int j=0; j<m; j++) {
25. T tmp = *(first+j);
26. int k2 = j;
27. while (true) {
28. int k1 = (k2<n2 ? k2+n1 : k2-n2);
29. if (k1==j) break;
30. *(first+k2) = *(first+k1);
31. k2 = k1;
32. }
33. *(first+k2) = tmp;
34. }
35. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 351
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.4. El método de ordenamiento rápido, quick-sort
.. ..
. = .
f(n)
2f(n/2)
f(n)
2f(n/2) f(n/2)
f(n/2)
n/2 n n/2 n
Si f (n) es una función “cóncava hacia arriba” (ver figura 5.12, izquierda)
entonces es válido que
2f (n/2) ≤ f (n), (5.29)
mientras que si es cóncava hacia abajo (ver figura 5.12, derecha) entonces
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 352
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
También decimos que la función tiene crecimiento “más que lineal” o “menos
que lineal”, respectivamente. Si la función crece más que linealmente, como
en el caso de n log n, entonces podemos acotar
2f (2) ≤ f (4)
2f (4) ≤ f (8)
4f (2) ≤ 2f (4) ≤ f (8) (5.31)
.. ..
. .
de manera que
T (8) ≤ 3f (8) + 8d
T (16) = f (16) + 2T (8) ≤ f (16) + 6f (8) + 16d ≤ 4f (16) + 16d (5.32)
.. ..
. .
y, en general
T (n) ≤ (log n) f (n) + nd. (5.33)
Si lo aplicamos a quick-sort estable con f (n) = n log n llegamos a
1. // Fase inicial
2. // Pone todos los elementos en S
3. while (![Link]()) {
4. x = *[Link]();
5. [Link](x);
6. [Link]([Link]());
7. }
8. // Fase final
9. // Saca los elementos de S usando ‘min’
10. while (![Link]()) {
11. x = *[Link]();
12. [Link]([Link]());
13. [Link]([Link](),x);
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 353
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
5.5.1. El montı́culo
El “montı́culo” (“heap” ) es una estructura de datos que permite repre-
sentar en forma muy conveniente un TAD similar al conjunto llamado “cola
de prioridad”. La cola de prioridad difiere del conjunto en que no tiene las op-
eraciones binarias ni tampoco operaciones para recorrer el contenedor como
end() y operator++(). Si tiene una función min() que devuelve una posi-
ción al menor elemento del conjunto, y por lo tanto es equivalente a begin().
El montı́culo representa la cola de prioridad almacenando los elementos
en un árbol binario con las siguientes caracterı́sticas
Es “parcialmente ordenado” (PO), es decir el padre es siempre menor
o igual que sus dos hijos.
Es “parcialmente completo” : Todos los niveles están ocupados, menos
el último nivel, en el cual están ocupados todos los lugares más a la
izquierda.
En la figura 5.13 vemos tres árboles binarios de los cuales sólo el de más
a la izquierda cumples con todas las condiciones de montı́culo. El del centro
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 354
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
No son montículos
23 11 32 18 23 11 32 13 23 11 Λ 18
24 25 12 22 25 12 24 Λ 12
5.5.2. Propiedades
0
5
1 2
10 16
3 4 5 6
23 11 32 18
7 8 9
24 25 12
5 10 16 23 11 32 18 24 25 12
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 355
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
hijo izquierdo de j = 2j + 1,
(5.35)
hijo derecho de j = 2j + 2.
5.5.3. Inserción
inserta 4
5 4
10 16 5 16
23 11 32 18 23 10 32 18
24 25 12 4 24 25 12 11
Para poder usar el montı́culo para poder ordenar debemos poder insertar
nuevos elementos, manteniendo la propiedad de montı́culo. El procedimien-
to consiste en insertar inicialmente el elemento en la primera posición libre,
es decir la posición libre lo más a la izquierda posible del último nivel semi-
completo o, si no hay ningún nivel semicompleto, la primera posición a la
izquierda del primer nivel vacı́o. En la figura 5.15 vemos un ejemplo en el
cual insertamos el elemento 4 en un montı́culo que hasta ese momento con-
tiene 10 elementos. Una vez ası́ insertado el elemento, se cumple la condi-
ción de parcialmente completo pero probablemente no la de PO. Esta última
se restituye haciendo una serie de intercambios. Notar que los intercambios
de elementos no pueden quebrar la propiedad de parcialmente completo.
Para restituir la propiedad de PO vamos intercambiando el elemento in-
sertado con su padre, si éste es estrictamente mayor. El proceso se detiene
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 356
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
a
b n
I D
si no
n<a
n a
b a b n
I D I D
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 357
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
plazado la raı́z por un elemento todavı́a menor. Por otra parte I ya era un
montı́culo y lo seguirá siendo porque no fue modificado. Finalmente la condi-
ción de PO se satisface localmente entre n, b y a ya que n < a y como el la
condición se satisfacı́a localmente antes de que subiera n, debı́a ser a ≤ b,
por lo tanto n < a ≤ b.
Notemos que esta estimación es válida en el peor caso. A diferencia del ABB
(ver sección §4.6), el montı́culo no sufre de problemas de “balanceo” ya que
siempre es mantenido en un árbol parcialmente completo.
Este algoritmo de inserción permite implementar la lı́nea 5 en el seu-
docódigo 5.17 en O(n log2 n).
sale
4 11 Re-heap 5
5 16 5 16 10 16
23 10 32 18 23 10 32 18 23 11 32 18
24 25 12 11 24 25 12 24 25 12
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 358
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
a b
I D
si no
n>a
a n
n b a b
I D I D
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 359
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
contrario el árbol queda igual. Queremos ver que cada vez que el nodo n va
bajando una posición la condición de PO se viola (eventualmente) sólo en
el nodo que está bajando y en ese caso se viola localmente. Consideremos
primero el caso n > a, podemos ver que se ha restablecido la condición PO
en la raı́z, ya que a < n y habı́amos asumido que a ≤ b. Entonces a esta
altura la condición de PO puede violares solamente en la raı́z del subárbol
izquierdo I . Por otra parte si n ≤ a entonces todo el árbol es un montı́culo
ya que n ≤ a y n ≤ b (ya que a ≤ b).
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 360
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
4 5 8
5 8 10 8 10 16
12 23 16 10 12 23 16 12 23
4 5 8 12 23 16 10 5 10 8 12 23 16 4 8 10 16 12 23 5 4
heap heap ord heap ord
re-heap
10 10 4
re-heap re-heap
23 16 5 4 5 8
12 5 4 8 12 23 16 8 12 23 16 10
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 361
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
l
X
T (n) = 2j (l − j) (5.37)
j=0
l
X l
X
T (n) = l 2j − j2j (5.38)
j=0 j=0
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 362
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 363
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
5.5.9. Implementación
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 364
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.5. Ordenamiento por montı́culos
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 365
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.6. Ordenamiento por fusión
L= 7 3 8 -1 4 0 1 3
split
L1 = 7 8 4 1 L2 = 3 -1 0 3
sort(L1) sort(L2)
L1 = 1 4 7 8 L2 = 0 -1 3 3
merge
L= 0 1 -1 3 3 4 7 8
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 366
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.6. Ordenamiento por fusión
8. merge-sort(L2,comp);
9. // Fusion: concatenar las listas ‘L1’ y ‘L2’ en ‘L’ . . .
10. }
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 367
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.6. Ordenamiento por fusión
5.6.1. Implementación
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 368
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.6. Ordenamiento por fusión
5.6.2. Estabilidad
std::list<T> &LL =
(comp(*[Link](),*[Link]()) ? L1 : L2);
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 369
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.6. Ordenamiento por fusión
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 370
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.6. Ordenamiento por fusión
L= 7 3 8 -1 4 0 1 3
stable split
L1 = 7 3 8 -1 L2 = 4 0 1 3
sort(L1) sort(L2)
L1 = -1 3 7 8 L2 = 0 1 3 4
merge
L= 0 -1 1 3 3 4 7 8
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 371
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.6. Ordenamiento por fusión
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 372
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.6. Ordenamiento por fusión
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 373
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.7. Comparación de algunas implementaciones de algoritmos de ordenamiento
un solo elemento, de manera que hay que ordenar los elementos del
bloque entre sı́. Esto se puede hacer cargando todos los elementos
del bloque en un vector y ordenándolos con algún algoritmo de orde-
namiento interno.
Además, cuando se hace la fusión de las listas de bloques en la
lı́nea 28 se debe hacer la fusión elemento a elemento (no por bloques).
Por supuesto las operaciones sobre los bloques deben ser implemen-
tadas en forma “indirecta”, es decir sin involucrar una copia explı́cita de
los datos. Por ejemplo, si los bloques son representados por archivos
entonces podrı́amos tener en las listas los nombres de los archivos.
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 374
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.7. Comparación de algunas implementaciones de algoritmos de ordenamiento
1e-05
T(n)/n [sec]
merge-sort[list]
quick-sort[st] merge-sort[ext,M=1e5]
merge-sort[ext,M=1e6]
1e-06 merge-sort[ext,M=1e7]
heap-sort
libc-sort
merge-sort[vec,st]
STL[vec]
1e-07
1 10 100 1000 10000 100000 1e+06 1e+07 1e+08 1e+09
n
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 375
C AP ÍTULO 5. O RDENAMIENTO / Sección 5.7. Comparación de algunas implementaciones de algoritmos de ordenamiento
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 376
Indice alfabético
377
INDICE ALFAB ÉTICO / INDICE ALFABÉTICO
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 378
INDICE ALFAB ÉTICO / INDICE ALFABÉTICO
214, 262, 268, 273, 278, if, 142, 146, 188, 199, 213, 370
295, 300, 311 if, tiempos de ejec. de bloques if, 54
floor(x), función de la librerı́a implementación de un TAD, 37
estándar de C. , 147 in-place, ordenamiento i.p., 315
for, 293, 370 indefinido, 282
free store, 86 indirecto, ordenamiento, 328
front, 127 indx, 260
relación de o. fuerte, 315 inicialización, lista de i. de una clase,
fusión, ordenamiento por f., 367 83
inserción, método de i., 325
gcd, 350 insert, 106, 137, 180, 188, 205, 213,
genérico, función, 83 261, 268, 272, 278, 294,
grafo, 16 310
denso, 53
insertar, en listas, 67
no orientado, 16
inserter, 40
ralo, 53
insertion-sort, 325
graph, 32
inssort, 120
greedy, 34, 35
intercalamiento, alg. de ordenamien-
greedyc, 30, 31, 33
to por i., 51
h, 275 interfaz, 37
h2, 281 interno, ordenamiento, 315
hash tables, 274 intersección de conjuntos, 250
hash-set, 277, 278, 294 inválidas, posiciones, 70
heap, 86, 354 iteradores, 30, 39
heap-sort, 364, 365 iterativo, método, 256
height, 191, 192 iterator, 68, 105, 187, 212, 309
hermanos, 154 iterator-t, 179, 204, 277
heurı́stico, véase algoritmo iterators, 30, 39
hijos, 152
hoja, 153 key, 129, 138
huffman, 233
Huffman, árboles de H., 215 lazos, tiempo de ejec. de l., 55
Huffman, algoritmo de H., 230 lchild, 179, 187
huffman-codes, 236, 237 leaf-count, 193
huffman-exh, 229 left, 204, 212
hufunzip, 241 less, 319
hufzip, 238 lexicográfico, orden, 136, 318
LIFO, 109
ibubble-sort, 329 lineales, contenedores, 135
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 379
INDICE ALFAB ÉTICO / INDICE ALFABÉTICO
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 380
INDICE ALFAB ÉTICO / INDICE ALFABÉTICO
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 381
INDICE ALFAB ÉTICO / INDICE ALFABÉTICO
((vers aed-2.0.5-1780-g27b33e33) (date Wed Aug 13 07:49:06 2025 -0300) (proc Sat Aug 16 09:46:44 2025 -0300)) 382
Bibliografı́a
383