Suche in baumstruktur optimieren

Computer: Software & Programmierung Delphi & Pascal
#1

moin jungs,

ich habe eine wichtige frage und hoffe, dass mir einer darauf eine antwort geben kann:

ich habe einen datenträger 1:1 ausgelesen und in eine baumstruktur (extern) bzw. listentruktur (intern) umgewandelt. nun möchte ich darauf ein suche ausführen. klappt auch, nur leider ist diese ziemlich lahm, sprich bei 50000 elementen kanns dann doch mal 10 sekunden und länger in anspruch nehmen (auf einem schnellen rechner!).

kann ich die suche irgendwie optimieren? momentan gehe ich von der wurzel rekursiv alle elemente im baum durch, was in meinen augen auch notwendig ist, weil ich ja eine 1:1 kopie habe und nicht schon von vorherein die eingelesenen elemente geordnet in den baum geschrieben habe…

weiß irgendjemand rat? wäre euch zutiefst verbunden,

burn

#2

Hallo erstmal,

ahh, Bäume, meine lieblings Struktur *sentimental*.
Und nun zur Hilfe:
Man muss nicht alle Elemente in einem Baum durchgehen um einen bestimmten Knotenpunkt zu finden, z.B. kannst du jedem Knoten eine bestimmte ID (bei 50.000 empfehle ich WORD) zuordnen oder wenn es Namen hat Strings, z.B. so, dass links die kleineren ID/Strings und rechts die größeren oder gleichen vom jetzigen Knoten sind.
Aber es sollte einer gewissen Struktur folgen.
Dann muss man nur noch nach dem Namen/ID suchen, und das geht ganz einfach:

  1. Setzt das Ergebnis der Suche auf false/nil/0 (was dir so passt).
  2. Guckst ob der Knoten mit dem Gesuchten übereinstimmt?
    Wenn ja; dann gibt du ihn zurück und beendest die Suche
    Wenn Nein; dann zu 2.
  3. Ist der Name/ID kleiner als die gesuchte?
    Wenn ja; dann untersuchst du den Linken-Teilbaum
    Wenn Nein; dann den Rechten-Teilbaum.

So einfach ist das, damit hast du minimal „ln(n)“ Schritte bis zum Knoten. Bei 50.000 sind es dann ca. 16! Ein kleiner aber feiner unterschied zu 50.000, oder? Natürlich kann es durch gegebenheiten des Baumes auch bis 100 oder mehr gehen.

Bei einer Zuordnung solltest du darauf achten, dass das 1. Element nicht die 1 bekommt, das zweite nicht die 2 usw., denn dann hast du eine einfache Liste und die Suche wäre wieder umsonst.

Ich hoffe, ich hab dir helfen können.

Gruß Thomas

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#3

moin,

danke erstmal für die antwort, nur leider kann ich damit nicht wirklich viel anfangen, weil ich keinen binären baum habe =) naja, hab auch schon nen lösungsansatz und meld mich sonst nochmal, sollte der auch nicht funzen,

thnx,

burn

#4

Auf einem völlig unsortierten Datenbestand zu suchen ist wahnsinn. Die Zugriffszeiten sind nicht berechenbar - man kann nur sagen 1 Schritt bis 50000 Schritte können es sein.

Lösung: Es muß Ordung her!
Wie: Ein so großer Datenbestand wird nicht mehr im Hausptspeicher stehen können also kann man Binärbäume vergessen. Unter Umständen könnte man einen AVL-Baum erzeugen, aber sollte das ganze auf einem Hintergrundspeicher wie einer Festplatte liegen, dann empfehle ich einen B-Baum zu erstellen. Das dauert ein paar Minuten, aber die suche ist danach zuverlässig schnell, determiniert und berechenbar ==> Alles was ein Informatiker wie ich will!!!

GVT

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]