AlgoI (09-10): reeks 15
Algoritmen I (2009-2010)
reeks 15: zoekboom
De belangrijkste elementaire operaties van een verzameling (Eng.: set) zijn:
een element toevoegen (normaalgezien zonder duplicaten)
bepalen of een bepaald element voorkomt
een element verwijderen
Verzamelingen kunnen op verschillende manieren geïmplementeerd worden (welke?).
In deze reeks maken we een implementatie gebaseerd op een binaire zoekboom.
TreeSet
Gegeven:
treeset.h
treesettest.h
unittest.h
functor.h
Implementeer de nodige methodes (dat mag binnen de header-file), constructoren en destructoren.
Gebruik recursie waar mogelijk. Voeg zonodig hulpfuncties toe, maar liefst niet publiek.
Maak hulpklassen en -functies zoveel mogelijk privaat (of protected).
Wat is de performantie van elke methode (gemiddeld? worst-case?).
Iterator
Maak een klasse TreeSetIterator met
operator*: geeft de waarde
operator++: gaat naar het volgende element
operator==, operator!=: om iteratoren te vergelijken
Voorzie in TreeSet methodes begin() en end()
die een iterator naar het begin resp. voorbij het einde wijzen.
| 
Algemeen