Skúška 17.1.2020 - Utriedené množiny


Zapíš metódy triedy SortedSet:

class SortedSet:
    class _Node:
        def __init__(self, value):
            self._value = value
            self._lsize = 0
            self._left = None
            self._right = None

    def __init__(self):
        self._root = None

    def __repr__(self):
        return 'SortedSet{' + ', '.join(map(repr, self)) + '}'

    def add(self, value):
        ...

    def __contains__(self, value):
        ...

    def __len__(self):
        ...

    def __iter__(self):
        ...

    def __getitem__(self, index):
        ...

    def index(self, value):
        ...

ktoré realizujú dátový typ množina pomocou binárneho vyhľadávacieho stromu BST. Vďaka tomu sú všetky prvky takejto množiny usporiadané od najmenšieho po najväčší (ak by sme ich vypísali pomocou inorder). V každom vrchole BST sa uchováva informácia o počte vrcholov v ľavom podstrome (atribút _lsize). Zrejme v koreni je počet vrcholov v ľavom podstrome, v listoch sú 0. Vďaka tejto informácii sa dá veľmi efektívne zistiť poradové číslo ľubovoľného prvku v množine.

Metódy (kde h je výška BST, často je to blízko log n):

  • add(value) - hodnotu value pridá do množiny (ak tam táto hodnota ešte nebola); pritom aktualizuje atribút _lsize vo všetkých vrcholoch BST; zložitosť operácie je O(h)

  • __contains__(value) - zistí, či je hodnota value prvkom množiny (vráti True alebo False); zložitosť operácie je O(h)

  • __len__() - vráti počet prvkov v množine; zložitosť operácie je O(h), lebo využije informáciu o počte vrcholov v ľavých podstromoch v atribúte _lsize a teda stačí zisťovať počet prvkov len v pravých podstromoch

  • __iter__() - vráti generátor prvkov množiny v usporiadanom poradí (zrejme je to inorder), napr. list(množina) by vytvoril usporiadaný zoznam hodnôt; zložitosť operácie je O(n)

  • __getitem__(index) - vráti hodnotu s daným indexom v množine, pri chybnom indexe vyvolá IndexError; je to tá istá hodnota, ako by vrátil list(množina)[index], len by to malo byť so zložitosťou O(h)

    • metóda využije informáciu o počte vrcholov v ľavých podstromoch v atribúte _lsize

  • index(value) - vráti index hodnoty value v množine, pri neexistujúcej hodnote vyvolá ValueError; je to tá istá hodnota, ako by vrátil list(množina).index(value), len by to malo byť so zložitosťou O(h)

    • aj táto metóda využije informáciu o počte vrcholov v ľavých podstromoch v atribúte _lsize

Z úlohového servera L.I.S.T. si stiahni kostru programu skuska.py. Mal by si dodržať tieto vlastnosti programu:

  • Nemeň podtriedu _Node ani metódu __init__.

  • Nemeň mená už zadaných atribútov (metód a premenných).

  • Nepridávaj žiadne vlastné atribúty, môžeš pridávať vlastné metódy.

  • Metódy realizuj bez rekurzie, lebo by mohli na niektorých dátach spadnúť na pretečení zásobníka.

  • Pri testovaní riešenia sa bude kontrolovať tebou vytvorený binárny vyhľadávací strom (s koreňom v atribúte _root).

Aby si mohol spúšťať skúškové testy, riešenie (bez ďalších súborov) odovzdaj na úlohový server L.I.S.T.. Testy postupne preverujú vlastnosti tvojich algoritmov, pri prvej chybe sa testovanie preruší a ďalšie časti sa netestujú:

  • 40% bodov za metódy add, __contains__ a __len__

  • 20% bodov za generátor __iter__

  • 40% bodov za metódy __getitem__ a index

Aby si mohol spúšťať skúškové testy, program ulož do súboru skuska.py. Riešenie odovzdaj na úlohový server https://list.fmph.uniba.sk/.

Praktická časť končí o 11:00 a skúška pokračuje od 12:00 vyhodnotením v kancelárii m162.