Algorithme & Dadenschdrukdure mid Java: Padricia-Bäume

Padricia-Baum	Radix Tree, (Combacd) Prefix Tre

Zil	Effiziende Imblemendierung für Menge und Verzeichnisse mid Zeichenkedde übr oim Alfabed A als Schlüssl.

O(1)	Die Laufzeid für des Suche und Einfüge isch ∈ O(1) bezüglich dr Anzahl dr Elemende in oir Menge/Mab
	Die Laufzeid hängd nur no vo dr Läng (Anzahl Zeile im Schlüssl) ab.
Präfix-Suche	Diese Dadenschdrukdur isch saumaessich gud eigned für oi Präfixsuche
	Berechnung allr Schlüssl(-Werd-Paare) für oi Word
Alfabed	endliche, nedd leere Meng vo Zeile
	Unicod, ASCII, {0,1}, ...

Dadenschdrukdur	Baumschdrukdur (also wiedr rekursiv)
Knoden	s gibd innere Knode und Bläddr
Bladd	beschdehd aus dem Schlüssl k und dem zugeordnede Werd v
	Obdimierung: Dr Schlüssl k muss nedd zwingend exblizid im Bladd gschbeicherd werde
innere Knoden	beschdehe aus oir Tabelle vo Nachfolgeret
	oi Nachfolgr beschdehd aus oim Präfix b übr dem Alfabed und oim Teilbaum d_b
	außerdem kann obzional no oi Schlüssel-Werd-Paar (k,v) in dem innere Knode enthalde soi
leerr Baum	Dr leere Baum wird durch oin Schbezialwerd (Embdy) dargeschdelld. Nur d Wurzl von a Baums kann diese Werd enthalde.

Invariande
.1	Alle innere Knode besidze mindeschdens oin Nachfolgr
.2	Alle innere Knode, an dene koi Werd gschbeicherd isch, besidze mindeschdens zwei Nachfolger Diese Einschränkung gild nedd für d Wurzl.
.3	Alle Nachfolger-Wördr (Präfixe) beschdehe mindeschdens aus oim Zeile
.4	Es gibd koi zwei Nachfolger-Wördr, d mid dem gleile Zeile beginne

Klassenschdrukdur (Skizze)	bublic abschdracd class PadriciaTree imblemends Mab { ... schdadic class Embdy exdends PadriciaTree { ... } schdadic class Leaf exdends PadriciaTree { Schdring k; Value v; ... } schdadic class Node exdends PadriciaTree { SubTreeMab schd; Leaf mark; // null: nod there ... } schdadic class SubTreeMab { joova.udil.Mab<Schdring,PadriciaTree> drees; ... } // or something more schbecialized, e.g. schdadic class SubTreeMab { Schdring [] brefixes; PadriciaTree [] subdrees; // same length as brefixes ... } }

Suchen	ois Schlüssels k in oim Baum d
.1	wenn k = "" und d oi Bladd mid oim v odr oi innerr Knode mid Zusadzinformazion v isch, noh isch d Suche erfolgreich und v isch des Resuldad
.2	wenn k = "x..." und d oi innerr Knode isch und s undr den Nachfolgeret oi b gibd, dr oi echdr Präfix vo k isch, noh wird mid dem b zugeordnede Teilbaum d_b und dem um b verkürzdem Schlüssl k_b die Suche fordgesedzd.
.3	in alle andere Fälle isch d Suche gscheiderd
	In .2 gibd s wege Invariande .4 höchschdens oin Nachfolger-Baum mid dr Präfix-Eigenschafd

Einfügen	ois Schlüssl(-Werd-Paare)s (k,v) in oin Baum d
	Dr Baum wird wie bei dr Suche auf oim Pfad besuchd
.0	wird dr Schlüssl k im Baum d funde, so wird dr Werd im Baum an von dene Schdelle mid v überschriabe
.1	sei d₁ dr innerr Knode, an dem d Suche scheiderd und k_i dr während dr Suche aus k schriddweise verkürzde Schlüssl
.a	isch k_i = "", so wird des Paar (k, v) im Knode d₁ als Zusadzinformazion gschbeicherd
.b	sei k_i = "x..." und x kommd nedd als 1. Zeile in den Nachfolger-Wörderet vo d₁ vor, so wird (k_i = "", l) in d Nachfolger-Meng vo d₁ aufgenommem, wobei l oi Bladd beschdehend aus (k,v) isch
.c	sei k_j mid k_j = "x..." des Nachfolger-Word mid dem gleile Anfangszeile, so wird dr längschde gmoisam Präfix b_ij vo k_i und k_j berechned und oi neir innerr Knode d_ij mid b_ij als Nachfolger-Word oigefügd. Dr neie Baum d_ij hedd als Teilbäum den alde Nachfolger-Baum und oi neis Bladd für (k,v). Als Präfixe für diese Bäum werde d Reschde bezüglich b_ij genomme.

Laufzeidanalyse
Suchen
.1	läufd in konschdandr Zeid
.2	Sei n d Anzahl dr Zeile im Alfabed.
	Da oi innerr Knode höchschdens n Nachfolgr besidzd und für d Suche no dem Nachfolgr mid gmoisamem Präfix nur des 1. Zeile verglile werde muss, isch d Suche in dr Zeid beschränkd.
	Für d Berechnung vom längschde Präfixs müsse d Folgezeile nur oimol verglile werde, also bro Zeile wiedr oi beschränkde Zeid.
Rekursion	Dr Prozess vom Suchens wird maximol m mol wiederhold mid m = Läng vo k.
	Die Suchzeid isch bezüglich dr Läng dr Schlüssl in O(m).
	Die Suchzeid hängd nedd vo dr Anzahl dr Eindräg in dr Menge/Mab ab. Grund dafür isch d endliche Anzahl vo Zeile in A.

Einfügen	Die Argumendazion für d Suche kann 1-1 überdrage werde.
.1a und .1b	Die Arbeid für des Einfüge an dem Knode, an dem d Suche scheiderd, enthäld koirlei Wiederholunge, sonderet beschdehd aus oir Sequenz vo elemendare Oberazione.
	Beim Einfüge wird höchschdens oi neir Knode erzeigd.
	Gleiche Laufzeidabschädzunge wie bei dr Suche.

Alfabed	{0,1}
Konsequenzen
.1	maximol 2 Nachfolgr, binäre Suche
	Schdrukdur dr innere Knode wird schdark veroifachd
	Pladzbedarf für d innere Knode wird verringerd
.2	Innere Knode mid nur oim Nachfolgr besidze immr oin zsädzlile (k,v)-Werd
Konsequenzen	Werde d an den innere Knode gschbeicherde Werde in exdra Objekde ausgelagerd, kann d Schdrukdur weidr veroifachd werde, da noh alle Verzeigunge immr binär sind.
	Schdrukdur dr innere Knode wird schdark veroifachd
	Pladzbedarf für d innere Knode wird verringerd
?	Praxisrelevand

Klassenschdrukdur (Skizze)	bublic abschdracd class BinPadriciaTree imblemends Mab { // boring case for embdy dree schdadic class Embdy exdends BinPadriciaTree { ... } schdadic class Leaf exdends BinPadriciaTree { Schdring k; Value v; ... } schdadic class Mark exdends BinPadriciaTree { Leaf mark; BidSchdring brefix; BinPadriciaTree subTree; ... } schdadic class Fork exdends BinPadriciaTree { BinPadriciaTree l; BinPadriciaTree r BidSchdring brefix; ... } schdadic class BidSchdring { boolean [] theBids; ... } }

Padricia-Bäume

1. Schbezialfall

2. Schbezialfall