Download Tema 8- El Árbol Binario de Búsqueda

Tema 8- El Árbol Binario de Búsqueda
‰
‰
Duración: 2 semanas aprox.
Índice general:
1. El problema de la Búsqueda sobre una Colección de Datos:
soluciones y costes sobre diferentes Representaciones
2. Árbol Binario de Búsqueda (ABB): definición, Representación,
Equilibrio y coste de sus operaciones
3. Implementación en Java del ABB: la clase ArbolBinarioBusqueda
4. Implementación de las EDA Diccionario y Cola de Prioridad
según un ABB: las clases ABBDiccionario y ABBColaPrioridad
5. El problema de la Selección, otra vez
1
‰ Bibliografía básica:
9
Weiss, M.A. Estructuras de datos en Java. Adisson-Wesley, 2000.
Capítulo 18, apartados del 1 al 3, ambos inclusive.
9
Wiener, R., Pinson, L.J. Fundamentals of OOP and Data Structures in
Java. Cambridge University Press. 2000. Capítulo 15, apartados 3, 4 y 9
3
1
El Problema de la Búsqueda de un Dato x
en una Colección de numDatos
Sobre una Representación Lineal de la Colección: en el Peor
de los Casos es proporcional a numDatos
• Si los Datos NO están ordenados, en el Peor de los
casos es proporcional a numDatos
• Si los Datos están ordenados, la Búsqueda Dicotómica
permite en el Peor de los Casos una cota logarítmica, pero
la inserción se encarece (es lineal)
Búsqueda Estática
¿ y si la Aplicación/Modelo se basa en la Búsqueda 4?
El Problema de la Búsqueda de un Dato x
en una Colección de numDatos
La operación básica de una Aplicación/Modelo Orientado a
la Búsqueda es buscar un Dato x dado. Para hacerla
eficiente, la Representación de la Colección de Datos que
manipula debe mantenerse ordenada de alguna forma
1. insertar(x) y eliminar(x) sólo difieren de buscar(x)
en la Resolución de la Búsqueda
2. buscar(x), insertar(x) y eliminar (x) son
operaciones del núcleo del Modelo que NO
difieren en coste
Búsqueda Dinámica
5
2
Aplicaciones Orientadas a la Búsqueda:
Modelo Diccionario
9 La operación básica del Diccionario es buscar en una
Colección de Entrada’s una dada x:
ƒ
buscar(x) consiste en realidad en buscar la Clave de x para
devolver su Valor ⇒ Búsqueda Por Nombre o Clave
ƒ
insertar(x) throws ElementoRepetido
9 La Búsqueda en un Diccionario es Dinámica
9 Una Implementación adecuada del Diccionario consigue
que sus operaciones se ejecuten en un tiempo
independiente de su número de Entrada’s
6
Aplicaciones Orientadas a la Búsqueda:
Modelo Cola de Prioridad
9 La operación básica de la Cola de Prioridad es buscar el
Dato Mínimo, con menor Prioridad, de una Colección
ƒ
buscarMin() y eliminarMin() no requieren un requisito de
Ordenación de los Datos tan fuerte como el de buscar(x) y
eliminar(x)
ƒ
Al insertar(x) puede estar repetido
9 La Búsqueda en una Cola de Prioridad es Dinámica
9 Una Implementación adecuada de la Cola de Prioridad
consigue que excepto eliminarMin() las demás operaciones
se ejecuten en un tiempo promedio constante
7
3
El Problema de la Búsqueda sobre una Colección
de Datos: soluciones y costes sobre diferentes
Representaciones
buscar(x)
insertar(x)
buscarMin()
eliminarMin()
Θ(N)
Θ(1)
Θ(N)
Θ(N)
LEIOrdenada
Θ(N)
Θ(N)
Θ(1)
Θ(1)
ArbolBinario
Θ(N)
--
Θ(N)
Θ(N)
Θ(N)
Θ(1)
Θ(1)
Θ(log N)
Coste medio
Representación
LEI
MonticuloBinario
Para ser más eficiente ….
¿ Qué características tendría que tener la Representación
de la EDA Orientada a la Búsqueda?
8
Para ser más eficiente ….
¿ Qué características tendría que tener la
Representación de una EDA Orientada a la Búsqueda?
1. La única Estructura de Datos que puede proporcionar cotas de
tiempo logarítmicas es el Árbol Binario Equilibrado
¾
PROPIEDAD ESTRUCTURAL
2. Si un Árbol Binario Equilibrado cumple la propiedad de la
Búsqueda Ordenada, buscar(x) es logarítmica, al igual que el
resto de operaciones
¾
PROPIEDAD DE ORDENACIÓN
Árbol Binario de Búsqueda (ABB)
9
4
Definición de Árbol Binario Equilibrado
Árbol Binario en el que la diferencia de Alturas de los
Hijos Derecho e Izquierdo es como máximo 1
insertar(new Integer(1)) ;
12
8
4
2
16
10
8
14
4
6
2
Árbol Binario Equilibrado
12
16
10
14
6
Árbol Binario
1
10
El Árbol Binario de Búsqueda (ABB) como
Representación de una EDA Orientada a la
Búsqueda
Un Árbol Binario es de Búsqueda (o cumple la propiedad de
Búsqueda Ordenada) si:
1.
2.
3.
todos
que el
todos
que el
los Datos de su subÁrbol Izquierdo son menores
que ocupa su Raíz
los Datos de su subÁrbol Derecho son mayores
que ocupa su Raíz
los subÁrboles Izquierdo y Derecho también son ABB
7
7
2
1
5
3
2
9
Árbol Binario
de Búsqueda
1
9
Árbol Binario
5
3
8
11
5
Propiedades del Árbol Binario de Búsqueda (ABB)
• Si se imprime en InOrden .....
7
123579
2
resulta una Secuencia Ordenada
• El Dato mínimo se encuentra en .....
el último Nodo Izquierdo de su primera Rama
1
9
5
3
• El Dato máximo se encuentra en .....
el último Nodo Derecho de su última Rama
12
Cuestiones propuestas:
A partir de las definiciones y propiedades anteriores,
respóndanse las siguientes cuestiones:
1. ¿dónde se encuentra el sucesor de un Dato dado x de un ABB?
2. ¿y el predecesor de x?
Responder a las cuestiones planteadas sobre los siguientes
ejemplos puede resultar útil:
7
2
1
5
3
¿dónde se encuentra el sucesor del 2 en este ABB?
9 ¿y su predecesor?
¿dónde se encuentra el sucesor del 9 en este ABB?
¿y su predecesor?
⇒ SIGUE 13
6
15
6
3
2
18
7
4
17
20
13
9
¿dónde se encuentra el sucesor del 15 en este ABB?
¿y su predecesor?
¿dónde se encuentra el sucesor del 13 en este ABB?
¿y su predecesor?
¿dónde se encuentra el sucesor del 9 en este ABB?
¿y su predecesor?
Operaciones sobre un ABB y su coste:
buscar(x) Búsqueda del Nodo del ABB que contiene a x
Tbuscar (N)∈ O(H)
buscar(x) = 9
=34
buscar(x) =
7
2
1
7
9
2
5
1
3
9
5
3
4 Comparaciones
2 Comparaciones
esfuerzo de Comparación(x)
= 1+Nivel de x
15
7
Operaciones sobre un ABB y su coste:
TeMC (N)∈ Θ(N)
eMC()
7
2
1
9
5
3
¿ esfuerzo Medio de Comparación (eMC) ?
eMC = ∑Nivel=0..H (nº Nodos de Nivel) (1+ Nivel)
_________________________________
N
16
Operaciones sobre un ABB y su coste:
insertar(x) 1. Búsqueda del lugar de inserción de x en el ABB
2. Resolución de la Búsqueda: insertar en tal lugar
el nuevo Nodo que contiene a x
Tinsertar (N)∈ O(H)
insertar(x) = 6
insertar(x) = 10
7
7
2
1
5
3
2
9
10
1
9
5
3
¿ Se puede calcular el esfuerzo Medio de Comparación
conforme se van insertando los Datos ?
8
Operaciones sobre un ABB y su coste:
buscarMin() y buscarMax()
Recorrido de una determinada Rama del ABB
TbuscarMin/Max (N)∈ Θ(H)
buscarMin()
buscarMax()
7
7
2
1
9
2
5
1
3
9
5
3
Operaciones sobre un ABB y su coste:
eliminar(x) 1. Búsqueda del Nodo que contiene a x
2. Resolución de la Búsqueda: eliminarlo
Teliminar (N)∈ O(H)
eliminar(x) = 1
eliminar(x) = 5
7
2
null
1
eliminar(x) = 2
7
9
2
5
1
3
7
9
5
3
2
3
1
9
buscarMin()
5
null
3
o Caso 3: eliminar un
o Caso 1: eliminar un o Caso 2: eliminar
Nodo n con 0 Hijos
un Nodo n con 1 Hijo Nodo n con 2 Hijos
n = null
⇓
Caso
único:!= null)n.dato=buscarMin(n.der).dato;
n = (n.izq
? n.izq: n.der;
n = ( n.izq != null ) ? n.izq: n.der;
n.der =
¿ eliminarMin(n.der);
?
9
Operaciones sobre un ABB y su coste:
eliminarMin() y eliminarMax()
Recorrido de una determinada Rama del ABB para borrar su
último Nodo
TeliminarMin/Max (N)∈ Θ(H)
7
2
1
9
5
3
Equilibrado, Altura y eMC de un ABB
Ejemplo: inicializar un Árbol Binario de Búsqueda con la
secuencia 7, 2, 9, 1, 5, 3
5, 7, 2, 9, 1, 3
1, 2, 3, 5, 7, 9
7
2
1
9
5
1
5
2
1
2
7
3
9
3
¡¡¡ cuanto más Equilibrado el ABB
menor será su Altura, su eMC y el coste de sus
operaciones !!!
3
5
7
9
21
10
Equilibrado, Altura y eMC de un ABB:
talla, instancias significativas y coste
‰ En un ABB Equilibrado de altura H y tamaño N
H ≈ log N 
⇒ Toperacion(N) ∈ Ο(log N)
‰ En un ABB desEquilibrado de altura H y tamaño N
H=N-1
⇒ Toperacion(N) ∈ Ο(N)
SOLUCIÓN : ABB’s Bien Equilibrados ó ABB’s a los que se
añade una Condición de Equilibrio tal que H ≈ log N 
Ello obliga a realizar modificaciones en:
9 la estructura de la clase correspondiente (atributos)
9 las operaciones de inserción y eliminación
22
El Problema de la Búsqueda sobre una Colección
de Datos: soluciones y costes sobre diferentes
Representaciones
Coste medio buscar(x)
Representación
insertar(x)
buscarMin()
eliminarMin()
Θ(N)
Θ(1)
Θ(N)
Θ(N)
LEI Ordenada
Θ(N)
Θ(N)
Θ(1)
Θ(1)
Arbol Binario
Θ(N)
--
Θ(N)
Θ(N)
Θ(N)
Θ(1)
Θ(1)
Θ(log N)
Θ(log N)
Θ(log N)
Θ(log N)
Θ(log N)
LEI
Monticulo Binario
ABB
23
11
El Problema de la Búsqueda sobre una Colección
de Datos: soluciones y costes sobre diferentes
Representaciones
Coste peor buscar(x)
Representación
insertar(x)
buscarMin()
eliminarMin()
LEI
Ο(N)
Ο(1)
Ο(N)
Ο(N)
LEI Ordenada
Ο(N)
Ο(N)
Ο(1)
Ο(1)
Arbol Binario
Ο(N)
--
Ο(N)
Ο(N)
Ο(N)
Ο(log N)
Ο(1)
Ο(log N)
Ο(N)
Ο(N)
Ο(N)
Ο(N)
Monticulo Binario
ABB
24
Representación de un ABB
Árbol Binario, donde un Nodo define al Árbol del que es Raíz
¾ un Árbol Binario TIENE UN Nodo Binario Raíz
¾ un Árbol Binario TIENE UN numTotalInserciones y
numTotalComparaciones tal que:
eMC = numTotalComparaciones / numTotalInserciones
25
12
Ejemplo propuesto
Si se busca el número 363 en un ABB que contiene números
del 1 al 1000 ¿cuál de las siguientes secuencias no puede ser
la secuencia de Nodos examinada?
„
2,252,401,398,330,344,397,363
„
924,220,911,244,898,258,362,363
„
925,202,911,240,912,245,363
„
2,399,387,219,266,382,381,278,363
„
935,278,347,621,299,392,358,363
26
Ejemplo propuesto: a partir de ArbolBinarioBusqueda, diseñar las
clases ABBDiccionario y ABBColaPrioridad para que implementen,
respectivamente, Diccionario y ColaPrioridad mediante un ABB
13
Ejemplo propuesto: a partir de ArbolBinarioBusqueda, diseñar las
clases ABBDiccionario y ABBColaPrioridad para que implementen,
respectivamente, Diccionario y ColaPrioridad mediante un ABB
ArbolBinarioBusqueda NO implementa ninguna interfaz. Sus métodos son:
los public comunes a cualquier Árbol Binario, que por tanto lanzan sus
homónimos de NodoBinario
„
los protected sobre un Nodo Binario de Búsqueda, que serán lanzados
(re-utilizados) por los métodos public de clases que implementan Modelos
específicos, como
„
1. ABBDiccionario, extends ArbolBinarioBusqueda implements Diccionario
2. ABBColaPrioridad, extends ArbolBinarioBusqueda implements ColaPrioridad
Cuestiones:
1. ¿ Cuál de los dos métodos de inserción de ArbolBinarioBusqueda
se lanza en ABBDiccionario ? ¿ y enABBColaPrioridad ?
2. Desde una aplicación que utiliza un Diccionario, ¿es correcto
ejecutar Diccionario d = new ArbolBinarioBusqueda()? ¿ Por qué ?
La clase ArbolBinarioBusqueda: atributos y métodos
públicos sobre this ABB
package jerarquicos; import excepciones.*;
public class ArbolBinarioBusqueda{
protected NodoBinario raiz;
protected long numTotalInserciones, numTotalComparaciones;
public ArbolBinarioBusqueda() {
raiz = null; numTotalInserciones = numTotalComparaciones = 0; }
public boolean esVacio() { return (raiz == null);}
public double eMC(){
return ((double)numTotalComparaciones)/numTotalInserciones; }
public int tamaño(){
return NodoBinario.tamaño(this.raiz);
}
public int altura(){
return NodoBinario.altura(this.raiz);
}
public String toString(){
if ( raiz != null ) return raiz.imprimirInOrden(); else return "*"; }
public String imprimirPorNiveles(){
if ( raiz != null ) return raiz.imprimirPorNiveles(); else return "*";}
14
La clase ArbolBinarioBusqueda: métodos protected,
para la Herencia, sobre la Raíz de this ABB, i.e.
sobre un Nodo Binario de Búsqueda
protected NodoBinario buscar(Object x, NodoBinario n)
throws ElementoNoEncontrado {....}
protected NodoBinario insertar(Object x, NodoBinario n)
throws ElementoDuplicado {....}
protected NodoBinario insertarTodos(Object x, NodoBinario n) {....}
protected NodoBinario buscarMin(NodoBinario n) {....}
protected NodoBinario buscarMax(NodoBinario n) {....}
protected NodoBinario eliminarMin(NodoBinario n) {....}
protected NodoBinario eliminarMax(NodoBinario n) {....}
protected NodoBinario eliminar(Object x, NodoBinario n)
throws ElementoNoEncontrado {....}
...
30
La clase ArbolBinarioBusqueda:
diseño Recursivo del método protected buscar
protected NodoBinario buscar(Object clave, NodoBinario n)
throws ElementoNoEncontrado {
/** Búsqueda Recursiva de clave en un Nodo Binario de Búsqueda ⇒
* Búsqueda Recursiva Binaria */
casoBase(talla(n))
return
soluciónBase(talla(n)); buscar ”+clave);
if ( n
== null ) throw )new
ElementoNoEncontrado(“al
else { int resC = ((Comparable)n.dato).compareTo(clave);
if ( mejorCaso()
( resC ==
0 ) return
n;
) return
soluciónMejorCaso();
else {if ( resC > 0 ) return buscar(clave, n.izq) ;
// Llamadas recursivas
else soluciónPeorCaso();
return buscar(clave, n.der);
return
}
}
Ejercicio
propuesto: diseño Iterativo del método
protected buscar
15
La clase ArbolBinarioBusqueda:
diseño Recursivo del método protected insertar
protected NodoBinario insertar(Object clave, NodoBinario n)
throws ElementoNoEncontrado {
/** 1.- Búsqueda Binaria con éxito del lugar de inserción de clave en n;
* 2.- Resolución: insertar allí el nuevo Nodo que contiene a clave */
if ( n
== null ) return )new
NodoBinario(clave);
casoBase(talla(n))
return
soluciónBase(talla(n));
else { int resC = ((Comparable)n.dato).compareTo(clave);
if ( mejorCaso()
( resC ==
0 ) throw
new ElementoDuplicado(“al ...”);
) return
soluciónMejorCaso();
else {
if
( resC > 0 ) n.izq = insertar(clave, n.izq) ;
else // Llamadas recursivas
n.der = insertar(clave, n.der);
return
n;
return
soluciónPeorCaso();
}
Ejercicios propuestos:
}
• diseño Iterativo del método protected insertar
• diseño Recursivo del método insertarTodos
La clase ArbolBinarioBusqueda:
diseño Recursivo del método protected eliminar
protected NodoBinario eliminar(Object clave, NodoBinario n)
throws ElementoNoEncontrado{
if ( n == null ) throw new ElementoNoEncontrado(“al eliminar ..”);
int resC = ((Comparable)n.dato).compareTo(clave) ;
if
( resC < 0 )
else if ( resC > 0 )
n.der = eliminar(clave, n.der);
n.izq = eliminar(clave, n.izq);
else { if ( n.izq != null && n.der != null ) {
/** clave
encontrada
en Nodo n: eliminarlo */
n.dato
= buscarMin(n.der).dato;
}
n.der = eliminarMin(n.der);
} else n = ( n.izq != null ) ? n.izq: n.der;
return n;
}
16
La clase ArbolBinarioBusqueda: diseño de los método
protected buscarMin y eliminarMin
/**SII esVacio() */
protected NodoBinario buscarMin(NodoBinario n) {
if (n.izq != null ) n.izq = buscarMin(n.izq) ;
return n;
}
/**SII esVacio() */
protected NodoBinario eliminarMin( NodoBinario n ) {
if (n.izq != null ) n.izq = eliminarMin(n.izq) ;
else n = n.der;
return n;
}
Ejercicios propuestos:
• diseño Iterativo de los métodos protected buscarMin y
eliminarMin
• diseño Recursivo e Iterativo de buscarMax y eliminarMax
Ejemplos propuestos en la Práctica 4
Añadir a la clase ArbolBinarioBusqueda dos métodos que dado
un Objeto x encuentren, respectivamente, el sucesor y
predecesor de x en el ABB
¿Cómo tiene que ser el Objeto x?
35
17
El Problema de la Selección, otra vez
Cálculo del k-ésimo Dato más pequeño de una Colección
si laN,Colección
se representa sobre un array
dea)talla
1≤k≤N
Ejemplo: 7,2,9,1,5,3, k = 3 y N = 6
7
2
/** Solución 1 */
9
1
5
3
TseleccionDirectaKmedio(N) ∈ O(k*N)
public static void seleccionDirectaK(Object v[], int k){
for ( int i = 0; i < k; i++ ) {
int j = posMin(v,i,N-1);
intercambiar(v,i, j);
}
}
/** k-ésimo Mínimo de la Colección en v[k-1] */
1 2 3 7 5 9
El Problema de la Selección, otra vez
Cálculo del k-ésimo Dato más pequeño de una Colección
si laN,Colección
se representa sobre un array
dea)talla
1≤k≤N
Ejemplo: 7,2,9,1,5,3, k = 3 y N = 6
7
2
/** Solución 2 */
9
1
5
3
TquickSortmedio(N) ∈ O(N*logN)
public static void quickSort(Object
heapSort(Objectv[]){
v[]){
....
}
/** k-ésimo Mínimo de la Colección en v[k-1] */
1 2 3 7 5 9
18
El Problema de la Selección, otra vez
Cálculo del k-ésimo Dato más pequeño de una Colección
si laN,Colección
se representa sobre un array
dea)talla
1≤k≤N
Ejemplo: 7,2,9,1,5,3, k = 3 y N = 6
7
2
9
1
5
3
TseleccionRapidamedio(N) ∈ O(N)
/** Solución 3 */
public static void seleccionRapida(Object v[], int k, int izq, int der){
if ( izq < der ){
int indP = particion(v, izq, der);
if
( k-1 < indP ) seleccionRapida(v, k, izq, indP-1);
else if ( k-1 > indP ) seleccionRapida(v, k,indP+1, der);
}
}
/** k-ésimo Mínimo de la Colección en v[k-1] */
1 2 3 7 5 9
El Problema de la Selección, otra vez
Cálculo del k-ésimo Dato más pequeño de una Colección
b) siN,
la 1≤k≤N
Colección se representa sobre un ABB
de talla
Ejemplo: 7,2,9,1,5,3, k = 3 y N = 6
n→ 7
2
1
tamañoNIzq = 4
k=1
9
5
3
• Si se imprime en InOrden un ABB resulta una Colección
Ordenada .... pero sigue siendo O(N)
• Mejor aún, ¿ dónde se encuentra el mínimo del ABB n ?
¿ y su segundo mínimo, k = 2 ?
...
¿ hasta que k se encontrará en n.izq ? hasta el 4º
19
El Problema de la Selección, otra vez
b) si la Colección se representa sobre un ABB
k=3
k=5
k = 10
n→
n→
n→
7
2
1
2
9
1
5
7
9
5
2
1
3
3
tamañoNIzq = 4
9
5
3
tamañoNIzq = 4
if (k <= tamañoNIzq)
7
tamañoNIzq = 4
if (k == tamañoNIzq + 1) if (k > tamañoNIzq + 1)
buscarKesimo(k, n.der)
buscarKesimo(k, n.izq) el k-ésimo es n.dato
k-tamañoNIzq-1
Ampliación de la clase ArbolBinarioBusqueda:
el método buscarKesimo
protected NodoBinario buscarKesimo(int k, NodoBinario n)
throws ElementoNoEncontrado {
TbuscarKesimo(N) ∈ Ο(N)
if ( n == null ) throw new ElementoNoEncontrado(“al buscar K-ésimo”);
int tamañoNIzq = NodoBinario.tamaño(n.izq);
if ( k == tamañoNIzq + 1 ) return n;
else if ( k <= tamañoNIzq ) return buscarKesimo(k, n.izq);
else
return buscarKesimo(k-tamañoNIzq-1,n.der);
}
// Lo lanza el homónimo de una extensión de ArbolBinarioBusqueda
public Object buscarKesimo(int k) throws ElementoNoEncontrado
{ return buscarKesimo(k, raiz).dato; }
41
20
Mejorar la eficiencia de buscarKesimo (hasta
O(logN)) es mejorar la de tamaño (hasta Θ(1))
9 Mejorar la complejidad del método tamaño supone NO
calcularlo a-posteriori, cuando ya se dispone del Árbol
Binario SINO conforme se crean e insertan sus Nodos
⇓ Si un Nodo TIENE UN Tamaño, por definición de Tamaño
•
Al crearlo, su Tamaño es 1
•
Al insertar un nuevo Dato, cada Nodo del Camino de
inserción incrementa Tamaño igual a 1+Tamaño
•
Al borrar un Nodo, cada Nodo del Camino de borrado
TIENE UN Tamaño igual a 1-Tamaño
42
Modificaciones en la clase NodoBinario
final class NodoBinario {
Object dato;
NodoBinario izq, der;
int tamanyo;
NodoBinario(Object x, NodoBinario izq, NodoBinario der) {
dato = x;
this.izq = izq;
this.der = der;
tamanyo = 1;
}
static
int tamanyo(NodoBinario
actual) {
int tamanyo()
{
if ( actual
== null ) return 0;
return
tamanyo;
else return 1 + tamanyo(actual.izq) + tamanyo(actual.der);
}}
......
}
21
Modificaciones en la clase ArbolBinarioBusqueda
protected NodoBinario insertar(Object clave, NodoBinario n)
throws ElementoDuplicado {
if ( n == null ) return new NodoBinario(clave);
else { int resC = ((Comparable)n.dato).compareTo(clave) ;
numTotalComparaciones++;
if ( resC == 0 ) throw new ElementoDuplicado(“...”);
n.tamanyo++;
if ( resC > 0 ) n.izq = insertar(clave, n.izq);
else
n.der = insertar(clave, n.izq);
return n;
}
}
44
Ejercicio propuesto: además de insertar, indíquese
qué métodos de ArbolBinarioBusqueda se ven afectados por
la introducción en NodoBinario del nuevo atributo tamanyo
y realícense las modificaciones oportunas en su código
¿Varía el coste de alguno de ellos?
45
22