Conjunt ordenat P42980
Heu d’implementar una classe ConjuntOrdenat per a manternir un conjunt ordenat d’enters utilitzant arbres binaris de cerca. Les operacions que ha de suportar són:
- init() — inicialitza el conjunt buit.
- inserir(x) — insereix l’element x al conjunt. Si x ja hi és, no fa res.
- conte(x) — retorna True si és el conjunt conté l’element x i False en cas contrari.
- esborrar(x) — esborra l’element x del conjunt. Si x no hi és, no fa res.
- entre(x, y) — retorna un iterador que permet recórrer els elements entre x i y (inclosos) del conjunt en ordre ascendent.
- len() — retorna el nombre d’elements al conjunt.
Descarregueu-vos el fitxer code.py i anomeneu-lo conjunt.py. Aquest ja conté la interfície de la classe i un programa principal de proves que la fa servir.
Doneu el cost asimptòtic de cadascuna de les operacions públiques en funció d’n on n és el nombre d’elements al conjunt. Comproveu els possibles errors amb assercions. La vostra implementació ha de ser eficient. Documenteu el vostre codi adequadament (ni poc, ni massa).
No podeu utilitzar sort() ni sorted().
Public test cases
Input
inserir 4 inserir 2 inserir 8 inserir 2 mida entre 0 10
Output
3 2, 4, 8
Input
inserir 10 inserir 30 inserir 20 inserir 50 inserir 60 inserir 80 mida entre 30 100 entre 25 100 entre 100 200 entre 0 100
Output
6 30, 50, 60, 80 30, 50, 60, 80 10, 20, 30, 50, 60, 80
Input
esborrar 42 inserir -6 esborrar -6 esborrar -6 inserir 9 esborrar 9 mida entre -100 100 inserir 42 mida entre -100 100
Output
0 1 42
Information
- Author
- Jordi Petit
- Language
- Catalan
- Official solutions
- Python
- User solutions
- Python