Inhaltsverzeichnis
Digitales Suchen / Digitale Suchbäume
Die Hauptvorteile sind, dass
Die Nachteile sind, dass
Digitale Suchbäume
unsigned bits ( unsigned x, int k, int j )
Datenstruktur: die gleiche wie die für elementare binäre Suchbäume
Annahme: der i-te Buchstabe des Alphabets wird durch die aus fünf Bits bestehende Binärdarstellung von i repräsentiert.
Ein digitaler Suchbaum
Prozedur für das Einfügen in digitale Suchbäume
Beispiel: Einfügen eines neuen Knotens,
Eigenschaften eines digitalen Suchbaumes:
Digitale Such-Tries
Neue Idee:
Suchen eines Schlüssels in einer solchen Struktur:
Interessante Eigenschaften eines digitalen Such-Trie
Weitere Eigenschaften von digitalen Such-Tries
Ein digitaler Such-Trie, der aus N zufälligen Schlüsseln mit b Bits erzeugt wurde, besitzt im Durchschnitt ungefähr N/ln2 = 1,44 N Knoten.
Digitales Mehrwege-Suchen
Beispiel:
Um z. B. in dem abgebildeten Trie nach T = 10100 zu suchen,
Ein sinnvoller Kompromiss zwischen der Zeiteffizienz von
Interessant ist, dass „Hybrid“-Suchmethoden der Art und
Patricia
Hier werden Fragen untersucht, in denen mit Patricia
Ein Patricia-Baum
Um in diesem Baum zu suchen, beginnt man bei der Wurzel
Somit ist die Suche erfolgreich, wenn der Schlüssel bei dem
Suchprogramm für Patricia
Diese Funktion realisiert das Auffinden des eindeutig
Äußeres Einfügen in einen Patricia-Baum
Das Einfügen von T = 10100 veranschaulicht einen
Inneres Einfügen in einen Patricia-Baum
Implementation zum Einfügen in einen Patricia-Baum
Bei diesem Programm wird vorausgesetzt, dass head mit dem
Patricia stellt die Quintessenz der digitalen Suchmethoden dar:
Patricia würde mit einer Schlüsselmenge der Art
Bei allen anderen Suchmethoden ist die Länge der Schlüssel
|