Hallo Leute,
also nach einiger Recherche kam ich (mit euer Hilfe :)) zu folgendem
Lösungsvorschlag des oben angeführten Problems:
Das Rezept :)
Man implememntiere eine Klasse HashTabelle, welche ein Array von
NodeAVL-Elementen speichert. Zusätzlich implementiert man die
benötigten Methoden: hashFunktion()-soll den Hashwert zu einem String
liefern, dieser soll dann als Index in der Hashtabelle benutzt werden
beim Einfügen, Suchen, Löschen, dann Methoden wie search(), insert(),
delete(), etc...
Dabei speichert NodeAVL einen Namen z.B. (String), die Baumhöhe (für
die Balancierung), zwei Zeiger vom Typ NodeAVL und die Wurzel, auch vom
Typ AVLNode. Dann werden noch entsprechende Methoden, die ein AVLBaum
so halt braucht, implementiert: searchInTree(), insertInTree(),
deleteInTree(), Methoden für die Rotation, und andere...
So dann geht man meiner Meinung so vor wie jemand hier vorgeschlagen
hat, nämlich bei Kollisionen in der Hashtabelle, als Lösung Seperate
Chaining zu benutzen und halt dann als AVLBaum weiter verzweigen.
Vorgehensweise:
Einfügen
- Nehme den zu speichernden String und berechne den hashIndex mittels
hashFunktion()
- Nun überprüfe ob an der Stelle hashTabelleArray[hashIndex] etwas
steht, wenn nichts steht, füge dort ein, ansonsten, dh. es ensteht
eine Kollision, weil ein NodeAVL schon an der Stelle eingefügt ist,
dann fahre fort mit einfügen wie bei einem AVLBaum, also benutze dann
insertInTree(denKnoten) der Klasse AVLNode.
- Suchen
Beim Suchen, eines Elements, nehme ich den zu suchenden String,
berechne den hashIndex mittels der Funktion hashFunktion() und gucke im
hashTabelleArray[hashIndex] ob da das gesuchte Element steht, ist da
nix, kann ich false liefern, wenn das Element übereinstimmt dann true,
ansonsten suche ich weiter im AVLBaum, also searchInTree(denKnoten)
-Löschen
wäre dann Suchen und dann halt Löschen und die Bedingungen des
AVLBaums prüfen, etc...
Sooo damit entsteht dann ein Array von NodeAVL-Elementen, genaugesagt
sind es dann die Wurzeln der AVLBäume. Wie jemand schon gesagt
hat(Sorry das ich nicht nachgucke wer das wahr :)), habe ich im
arraybereich O(1) als average sowieso, wegen der
HashTabellenEigenschaft, weil ich den Index berechne beim Einfügen,
Löschen und beim Suchen, dh. hier brauch ich ja keine Sortierung, weil
ich weiß ich finde mein Element wenn ich mittels hashFunktion() den
indexwert habe, also greife ich sofort darauf zu.
Andernfalls suche ich ja weiter im Baum. Da dass aber sehrviele KLEINE
Bäume sind, es sei denn man wählt eine gute SträuFunktion
(hashFunktion()), die nicht so viele Kollisionen entstehen lässt, kann
ich davon ausgehen dass ich den Kontakt mit den Elementenmit wenig
Schritten, 2,3,4,5... erreiche, also dann auch in O(1) (glaube ich :))
Ansonsten im schlimmsten Fall muss ich den ganzen Baum an der Stelle
hashTabelleArray[hashIndex] durchlaufen, und das ist in dem Fall der
worst case der im AVLBaum gilt, also O(log n).
Also ich hoffe ich konnte das erläutern, hab das auch versprochen
falls ich darauf kommen sollte, und hoffe dass es auch stimmt. Bedanke
mich bei euch allen, und wünsche euch schöne Feiertage.
mfg
Tarik