Code: Select all
1. Implementeer het ADT tabel met behulp van een 2-3 boom. Volgende operaties dienen voorzien te worden:
a. Creëer een lege tabel.
b. Wis een tabel.
c. Voeg een nieuw element aan de tabel toe.
d. Verwijder een element.
e. Doorloop de elementen van de tabel, gesorteerd volgens search key, en geef de inhoud weer.
2. Zorg voor een uitgebreide test waarin wordt aangetoond dat voor alle operaties alle mogelijke gevallen behandeld worden zoals voorzien. Denk bv. aan insert in een blad waar nog plaats is, insert in een blad dat een “split” tot gevolg heeft, “split” van een interne knoop, “split” van de root, …
3. Schrijf een tweede implementatie voor het ADT tabel, dit maal gebaseerd op hashing. Maak gebruik van seperate chaining om collisions op te vangen. Om de items op te vangen, worden er 2-3 bomen gebruikt. Zorg voor een dynamische allocatie van de hash table: van zodra er een 2-3 boom van hoogte 4 voorkomt, moet de grootte van de hash table vergroot worden tot het eerste priemgetal groter dan 2 * tableSize.
4. Voorzie ook voor deze tweede implementatie een uitgebreide test.Ik maak dus een array aan (hashtable) waarvan elk element een 2-3 boom is. als ik dan een element wil toevoegen, dan bereken ik eerst volgens de zoeksleutel de plaats in mijn hashtabel en als dan voeg ik gewoon dat element op die plaats toe aan mijn 2-3 boom. van zodra er dan een boom in mijn hashtabel voorkomt met grootte >= 4 dan moet ik dus mijn hashtabel gaan vergroten, dus geowon mijn array langer maken. Nu was mijn vraag, hoe groot zou ik mijn hashtabel maken als ik start en als ik mijn hashtabel vergroot dan gaat mijn hash calculator toch een andere waarde geven voor de element die ik er dan op dat moment al heb insteken, dus die ga ik dan nooit meer terugvinden toch?
. Je maakt gewoon in je ADT 2-3 boom een methode calculateheight of dergelijke.
