a,b-Bäume < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:44 Di 04.10.2011 | | Autor: | volk |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich habe ein Verständnisproblem.
Ich verstehe die Logik hinter den (a,b)-Bäumen nicht. Habe mal eine Skizze angehängt.
![[a]](/images/paperclip.gif "Dateianhänge") [Bild Nr. (fehlt/gelöscht)]
Ob ein Baum ein (a,b)-Baum ist, erkenne ich noch. Aber wie ich in einem (a,b)-Baum suchen muss, verstehe ich schon nicht mehr. Die ganzen Bezeichnungen sind irgendwie verwirrend.
In der Definition steht: Es seinen die Schlüssel [mm] (k_1,...,k_{m-1}) [/mm] mit [mm] k_1<...
Dann muss man einen Datensatz mit Schlüssel [mm] k\in (k_{i-1},k_i) [/mm] im Teilbaum [mm] T_i [/mm] suchen.
Wenn ich jetzt die 6 suchen möchte. Wie komme ich darauf, dass sie in da steht, wo sie steht?
Grüße volk
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:05 Di 04.10.2011 | | Autor: | volk |
Ich habe in meinen Überlegungen völlig verdrängt, dass [mm] k_0=-\infty [/mm] und [mm] k_m=\infty [/mm] ist. Wenn ich einen Schlüssel habe, habe ich quasi drei, nämlich den gegebenen und [mm] k_0 [/mm] und [mm] k_m. [/mm] Wenn der Schlüssel jetzt 5 ist, muss ich die 7 im zweiten Teilbaum suchen, da sie zwischen 5 und [mm] \infty [/mm] liegt. So muss ich mich dann bis zum Schluss durchhangeln.
Kann denn eigentlich jede Zahl nur einmal vorkommen?
Gruß volk
|
|
|
| |
|
> Ich habe in meinen Überlegungen völlig verdrängt, dass
> [mm]k_0=-\infty[/mm] und [mm]k_m=\infty[/mm] ist. Wenn ich einen Schlüssel
> habe, habe ich quasi drei, nämlich den gegebenen und [mm]k_0[/mm]
> und [mm]k_m.[/mm] Wenn der Schlüssel jetzt 5 ist, muss ich die 7 im
> zweiten Teilbaum suchen, da sie zwischen 5 und [mm]\infty[/mm]
> liegt. So muss ich mich dann bis zum Schluss durchhangeln.
Genau.
Also für deine 6, wenn du die suchst, guckst du dir zuerst die Wurzel an.
Es ist $6 [mm] \leq [/mm] 7$, also gehst du nach links.
Dann ist $6 > 3$, also ab nach rechts.
Hier ist [mm] $5<6\leq6$, [/mm] also musst du in den dritten Unterbaum, denn (5,6] ist das dritte Intervall.
Das erste Intervall wäre [mm] ($-\infty$,4], [/mm] das zweite (4,5], das dritte eben (5,6].
Beachte hierbei jeweils, dass links runde Klammern sind und rechts eckige.
Wenn du jetzt die 5 suchst erstmal nach links, da [mm] $5\leq7$.
[/mm]
Dann nach rechts, da 5>3.
Schließlich in den zweiten Unterbaum, da [mm] $4<5\leq5$.
[/mm]
Suchst du jetzt zum Beispiel mal 3,7 (was nicht drinn ist!), dann gehst du auch erstmal nach links, denn [mm] $3,7\leq [/mm] 7$.
Dann nach rechts, denn 3,7>3.
Dann in den ersten Unterbaum, denn [mm] $3,7\leq [/mm] 4.
Dort steht nun die 4, somit weißt du, dass die 3,7 nicht im Baum drinn ist.
> Kann denn eigentlich jede Zahl nur einmal vorkommen?
Ja, denn wenn ein Element a zwei mal in zwei verschiedenen Blättern drinn wäre so müsstest du einen Schlüssel b haben, für den gilt:
1. $a [mm] \leq [/mm] b$
2. a > b
Und das ist so ohne weiteres nicht möglich.^^
Gleiches gilt für die Schlüssel:
gibt es einen Schlüssel a, der zwei mal vorkommt, oBdA steht a das zweite mal links vom ersten a.
Dann gilt für alle Blätter links vom ersten a: $x [mm] \leq [/mm] a$ und für alle Blätter rechts vom zweiten a (und somit aber auch links vom ersten a) x>a.
Auch das geht nicht wirklich gut, du hättest dann also beim zweiten a nur links einen Unterbaum, rechts nicht; und dann hättest du dir das zweite a auch ganz sparen können.
Es kann allerdings passieren, dass in Schlüsseln das gleiche steht wie in Blättern; muss aber nicht unbedingt.
Wenn es noch Fragen gibt immer her damit.
lg
Schadow
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Fr 07.10.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
