michbot
Grünschnabel
Dabei seit: 04.06.2011
Beiträge: 1
 |
|
| B-Baum i-tes element ausgeben |
     |
Meine Frage:
In einem B-Baum seien n Elemente gespeichert. In der Klasse für
innere Knoten (class kinn) gebe es ein int blattanzahl, das angibt, wie viele Blätter unterhalb des jeweiligen Knotens folgen.
Implementieren Sie eine Methode int ites_element(int i) in Java oder Java-ähnlicher Notation, die den i.-kleinsten Schlüsselwert im Baum zurückgibt. Die Methode soll dabei Laufzeit O(log n) haben. (Zeigen Sie, dass Ihre Methode diese Laufzeit hat!)
Meine Ideen:
Int ites_element(int i){
Int A;
return f(root, i, A);
}
Int f(bkno root, int i, int A) {
if (root != null) {
A=f(root.lv, i, A);
If (i!=0){
A=root.info;
i--;
else
Return A;
}
A=f(root.rv, i, A);
}
Return A;
}
-------------------------------
Der algo. steigt solange links ab bis er am ende ist und speichert dann das aktuelle element in Temp.--> einen rauf--> ev. links runter...--> Ausgeben des baumes aufsteigend sortierd.
jedes mal wenn ein element gespeichert wird wird i veringert, wenn i auf null runter gezählt wurde muss es sich um das ite element handeln.
bin mir nicht sicher ob das nicht eleganter geht. (int blattanzahl) hab ich ja nicht verwendet.
Aber mein eigentliches problem ist die Laufzeit zu berechnen.
Hat jemand einen tip wie ich wie laufzeit abschätze, oder einen ansatz bei dem der algorytmus leichter ist (hab wie gesagt das gefühl das mein algo. zu komplex ist)
|
|
