H 10.7

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: H 10.7

Beitrag von mister_tt »

Sorry ivoch, aber das mit den Radix-Bäumen ist mir immer noch nicht klar geworden... Wenn ich das soweit jetzt richtig verfolgt habe und das Beispiel im Skript stimmt, gibt man relativ von seiner aktuellen Position das Bit an, welches geprüft werden soll, wie in folgendem Beispiel:

A = 1100
B = 1001
C = 1010

A einfügen:
A

B einfügen:

Code: Alles auswählen

    2
  /   \
 B     A
C einfügen:

Code: Alles auswählen

    2
  /  \
  1    A
/  \
B  C
Richtig so?

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: H 10.7

Beitrag von ivoch »

Stell dir am besten vor, die Bits einer Buchstabe wären in einem Array (oder Vektor oder sowas) gespeichert. Im Knoten musst du also immer den Index des entsprechenden Bit IM Array angeben. Also bei deinem Beispiel, nach dem Einfügen von B, müsstest du in der Wurzel eine 1 schreiben, denn es wird dort das Bit auf Index "1" verglichen, also A=1100 und B=1001

Beim Einfügen von C musst du dann im linken Teilbaum wieder von 0 anfangen, da man jetzt nur B und C vergleicht, also musst du hier eine 2 schreiben, denn bei B und C sind die Bits auf Index 2 unterschiedlich, also B=1001 und C = 1010

Der Baum wird dann so aussehen:

Code: Alles auswählen

        1
      /  \
      2    A
    /  \
    B  C

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: H 10.7

Beitrag von mister_tt »

Also doch die absolute Angabe, welches Bit geprüft werden muss (wie ich es vorher schon einmal gesagt hatte)...

In meinem Beispiel habe ich das zu prüfende Bit relativ zur aktuellen Position angegeben...

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: H 10.7

Beitrag von ivoch »

Sorry, ich meinte relativ im Bezug auf die gerade aktuelle Buchstabe - also wenn du schon mal auf dem Knoten einen Präfix geschrieben hast, dann fängst du im Knoten selbst ab der nächsten Buchstabe zu zählen, also die erste, die nicht im Präfix steht. Also wenn du den Schlüssel "AABBABA" mit "AABCD" vergleichst, dann wirst du so einen Baum haben, neben dessen Wurzel "AAB" steht, IN der Wurzel eine 2 (denn du vergleichst die jeweils vierte Buchstabe der beiden Strings, also AABBABA und AABCD und bei diesen zwei Buchstaben ist das Bit an Position 2 unterschiedlich (wenn man die Kodierungen von deinem vorigem Beitrag nimmt). Und das linke Kind wird dann ein Blatt mit dem Wert "BABA" sein, während das rechte ein Blatt mit dem Wert "CD" sein.

Ich hoffe jetzt ist es verständlicher? :)

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: H 10.7

Beitrag von mister_tt »

Oha, das ist aber auch tricky... Ich hoffe und denke, dass ich es jetzt verstanden habe und richtig mache...

Danke für deine Hilfe...

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: H 10.7

Beitrag von Trillium »

Eine kleine Frage zum PATRICIA Baum habe ich da noch.

Müssen denn alle Bits von einem Wort „verbraucht“ werden? Ich brauche beispielsweise zum Finden des Wortes „ULM“ und „MUSE“ nur die ersten 3 Bit Wortes.

Ist das so richtig?

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: H 10.7

Beitrag von ivoch »

Du brauchst nur soviele Bits, wie es nötig ist, alle Vergleiche zu machen (oder mit anderen Worten, den ganzen Baum bis zum entsprechenden Blatt entlang zu durchgehen). "Alle" Bits eines Schlüssels sind ja schliesslich auch im Blatt selbst gespeichert - also wenn du bis dorthin gelangt bist, dann kannst du auch das ganze Wort ablesen.

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: H 10.7

Beitrag von Trillium »

Danke! Damit hoffe ich, den PATRICIA Baum verstanden zu haben :) .

Antworten

Zurück zu „Archiv“