Algorithmen und Datenstrukturen Programmier Aufgabe

[kafa175]

Hallo Allerseits, ich bräuchte eine kleine Hilfe, um eine Methode zu implementieren. Die eigentliche Aufgabe habe ich bereits fertig.
Wäre sehr nett wenn sich jemand bei mir melden könnte, der sich mit Algorithmen und Datenstrukturen auskennt und mir helfen möchte..

 

[kneitzel]

Wenn du deine Problematik beschreiben würdest, dann könnte man dir helfen. Aber so lange du das Problem nicht beschreibst, wirst du kaum Hilfe bekommen.

 

[handshake45]

PN an misch...

 

[kafa175]

Ja das Problem ist halt das ich die Aufgabenstellung nicht posten kann wegen meinem Prof.
Wir haben ein SearchTree mit Autocompleting-Feature implementiert. Die Methoden dazu stehen bereits. Jetz haben wir eine Teilaufgabe, wo wir einen Datensatz hinzufügen sollen, und dabei brauche ich Hilfe.

 

[kafa175]

PN an misch...

Da handshake es doch nicht kann.. hoffe ich noch auf eine Antwort von jemand anderem

 

[kafa175]

Kann denn niemand helfen ? 🙁

 

[kneitzel]

Ich bin sicher, dass hier Leute helfen könnten, nur eben sieht sich hier niemand als PN Trainer oder so. Daher kannst du vielleicht überlegen, wie du mit etwas Transferleistung die Problematik darstellen kannst so dass man Dir im Forum helfen kann.

 

[kafa175]

Okay ich fang mal so an. Ich habe eine txt Datei diese enthält einen Datensatz mit 3 Millionen Queries. Dann hab ich eine Methode gegeben die noch leer ist, da soll ich die txt datei verarbeiten und daraus einen Trie bauen. Also wüsste ich gerne als erstes wie ich die Text Datei verarbeiten soll?

 

[kafa175]

Aktueller Stand: ich hab die Datei ausgelesen bekommen mittels Scanner. Könnte mir jemand eventuell helfen, mit diesen Daten eine Trie zu erstellen? Wie gesagt, die Methoden habe ich. Ich weiß nur nicht, wie ich sie darauf anwenden könnte...

 

[kneitzel]

Also die Frage ist so erst einmal noch nicht ausreichend. In der Regel ist der Code so strukturiert:
- Du erstellst eine Instanz des Baumes
- Du liest die Datei ein, und erzeugst dabei die Instanzen von Deinen Datensatz Objekten. Jede Instanz fügst Du einfach in den Baum ein.

Also in Pseudo-Code sozusagen:

tree = new Tree();
while (Datensätze vorhanden) {
  datensatz = nächster gelesener Datensatz
  tree.insert(datensatz)
}

Das wäre ein genereller Ablauf für das Lesen von Daten und füllen einer Baumstruktur.

Bei dem Einfügen in den Baum, ist dann halt immer die Frage, wie der Baum genau aussehen soll. Der Begriff Baum sagt da erst relativ wenig aus.

So ein Einfüge-Algorithmus sieht in der Regel so aus:
- Neuer Knoten mit Datensatz erstellen.
- Ist der Baum leer / Wurzel leer? -> Wurzel vom Baum = neuer Knoten, fertig
- aktueller Knoten = Wurzel.
- Endlos-Schleife:
-- Entscheidung, welcher Childknoten von aktuellem Knoten verwendet wird.
-- Childknoten in aktuellem Knoten leer? ->childknoten = neuer Knoten, fertig.
-- aktueller Knoten = Childknoten

Oder rekursiv:
- neuen Knoten mit Datensatz erstellen.
- Ist Baum leer? Wurzel = Neuer Datensatz
- insert(wurzel, neuer Knoten)

insert(aktueller Knoten, neuer Knoten)
- Wo beim aktuellen Knoten soll der neue Knoten hin?
- childknoten aussuchen.
- childknoten leer? Ja: ausgesuchter Child = neuer Knoten; Nein: insert(childknoten, neuer Knoten)

Bei einem Binary Search Tree hat man 2 Kindknoten und das es gilt eine Regel wie: Linker Teilbaum hat Werte die kleiner sind als der Wert des Knotens und der rechte Teilbaum hat Werte, die größer sind.

Die Operationen finden sich z.B. auch unter https://www.geeksforgeeks.org/binary-search-tree-data-structure/

 

[mihe7]

Ich glaube, es geht nicht um einen Suchbaum, sondern um eine Präfixbaum (Trie). Im Prinzip gelten dort natürlich die gleichen Regeln wie für alle Bäume bzw. Graphen, so dass sich das Vorgehen nicht großartig von dem unterscheidet, was @JustNobody schon geschrieben hat.

Die Wurzel könnte der leere String sein, der Pfad von der Wurzel zum Blatt beschreibt dann ein Wort. D. h. für jeden Anfangsbuchstaben hat die Wurzel einen Kindknoten, auf die wiederum Knoten für den zweiten Buchstaben folgen usw.

Das lässt sich einfach aber ineffizient aufbauen, indem man für jedes Wort einfach von der Wurzel beginnend den jeweiligen Folgeknoten besucht, sofern dieser existiert, bzw. einfügt, falls dieser nicht existiert. Muss ein Knoten eingefügt werden, kann sofort der ganze Teilbaum (=Rest des Wortes) eingefügt werden.

Für die Speicherung der Kanten auf die Kindknoten böte sich ein sortiertes Array (bzw. eine sortierte Liste) an, da damit in logarithmischer-Zeit der richtige Kindknoten gefunden werden kann.