Conjunt ordenat P42980


Statement
 

pdf   zip   main.py

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 xx al conjunt. Si xx ja hi és, no fa res.

  • conte(x) — retorna True si és el conjunt conté l’element xx i False en cas contrari.

  • esborrar(x) — esborra l’element xx del conjunt. Si xx no hi és, no fa res.

  • entre(x, y) — retorna un iterador que permet recórrer els elements entre xx i yy (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’nn on nn é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