Fragen aller Art

[jeanorwin]

---

Stimmt, da war ja was. Danke dir!

[Kuno_See]

---

Bis wann wird bekannt gegeben wer die Klausur in welchem Hörsaal schreibt? Oder steht das schon irgendwo?

[Volschaf]

---

@Kuno_See

Bis wann wird bekannt gegeben wer die Klausur in welchem Hörsaal schreibt? Oder steht das schon irgendwo?

Hier.
Die Seite ist auch auf mein campus verlinkt.

[Kuno_See]

---

Implementieren Sie die Methode getNext(), die beim Aufruf f¨ur einen Knoten r des
Suchbaums mitWert r.value den n¨achst-gr¨oßeren, im Baum gespeichertenWert liefert.
Sie k¨onnen zur Vereinfachung davon ausgehen, dass es einen solchen Wert gibt.

Aus der Lösungsseite:

Gesucht ist vom aktuellen Knoten ausgehend das linkeste Kind des rechten Teilbaums Nicht der rechte Knoten von der Wurzel, sondern das linkeste Kind vom rechten Kind der Wurzel !

static int getNext(BinTree r) {
// Annahme der Aufgabenstellung, dass es einen nächsten Wert gibt
r = r.right;

while(r.left != null) {
	r = r.left;
}

return r.value;

}

Ich hätte hier gedacht dass man vielleicht auch doch noch mal rechts abbiegen muss. Angenommen obige Methode liefert uns den Knoten 10,
vielleicht hat der keinen linken Teilbaum, aber noch einen rechten im dem die 12 drin steht. Vielleicht hat dann die 12 wieder linke Teilbäume
so dass man dann vielleicht noch zur 5 oder so kommt. Was meint ihr?

[_hedgehogs_dilemma_4]

---

kann nicht passieren, weil man hier von einem SearchTree ausgeht.

Dabei werden immer alle Werte die größer sind als ein Knoten rechts von ihm eingefügt alle anderen links.

=> wenn du bei der 10 rechts auf die 12 abbiegst sind alle werte im Linken Teilbaum von 12 größer als 10.

als Beispiel siehe Anhang anbei - in Orange habe ich den Pfad markiert in dem der Algo ablaufen würde.

Attachment:
searchTree_eg.jpg: https://fsi.cs.fau.de/unb-attachments/post_129755/searchTree_eg.jpg

[Kuno_See]

---

Von der Seite

https://fsi.informatik.uni-erlangen.de/dw/pruefungen/bachelor/aud/loesungws09

wp(“if (x < 0 || x > 7) {x = 7 - x;} else {x = 8 + x;}”, x != 7) =
[(x < 0 ∨ x > 7) ∧ wp(“x = 7 - x;”, x = 7)] ∨ [¬(x < 0 ∨ x > 7) ∧ wp(“x = 8 + x;”, x != 7)]

Müsste links auch x UNGLEICH 7 sein oder ?

NACHTRAG in Richtung [hedgehogs dilemma = 42]: Oh, danke, danke, ich hatte es aber auch schon bei deiner Nur-Text-Erklärung verstanden =)

[ferdi0807]

---

@Kuno_See

Bis wann wird bekannt gegeben wer die Klausur in welchem Hörsaal schreibt? Oder steht das schon irgendwo?

https://www2.cs.fau.de/teaching/WS2013/AuD/klausur.html

[Volschaf]

---

@Kuno_See

Von der Seite

FSI Informatik/pruefungen/bachelor/aud/loesungws09

wp(„if (x < 0 || x > 7) {x = 7 - x;} else {x = 8 + x;}“, x != 7) =
[(x < 0 ∨ x > 7) ∧ wp(„x = 7 - x;“, x = 7)] ∨ [¬(x < 0 ∨ x > 7) ∧ wp(„x = 8 + x;“, x != 7)]

Müsste links auch x UNGLEICH 7 sein oder ?

Ja, scheint nur ein Tippfehler zu sein. Taucht auch in der naechsten Zeile nicht mehr auf.

[Kuno_See]

---

Ist ausgebessert.

[Cybergy]

---

Um nochmal auf die 1g) der Klausur vom 21.02.2013 zurückzukommen. Woher weiß man in der Klausur, wie die Höhe eines Baumes, der nur aus der Wurzel besteht, definiert ist. Ich finde in den Vorlesungsfolien nur die folgende Definition: “Die Höhe h eines Knotens entspricht der Anzahl der Kanten des längsten Pfades zu einem von diesem Knoten aus erreichbaren Blatt”.
Das heißt, dass ein Baum, der nur aus der Wurzel besteht, die Höhe 0 hat, womit bei der 1g) alle vier Antwortmöglichkeiten falsch sind. Kann es also auch passieren, dass man bei den Multiple-Choice Aufgaben mal nichts ankreuzen muss?

[_hedgehogs_dilemma_4]

---

Da meine Antwort falsch war hab ich Sie mal gelöscht^^

[Volschaf]

---

log_2(2) = 0.6?

Und ceil() ist übrigens die Aufrundungsfunktion, floor() die Abrundungsfunktion.

Davon abgesehen beantwortest nicht die Frage, wieso ein Baum, der nur aus einer Wurzel besteht laut Vorlesung die Höhe 0 hat, dies aber sich in keiner Antwortmöglichkeit widerspiegelt.

[Cybergy]

---

Wenn man mal etwas anders argumentiert und sich überlegt, dass man abgesehen von der 1g) in der Aufgabe 1 schon 14 Kreuze gesetzt hat, dann merkt man, dass nur noch 1 Kreuz zu setzen ist und zwar bei der 1g).
Da bei der 1g) nach der “Mindesthöhe” gefragt ist und die 1., 3. und 4. Antwortmöglichkeit größer gleich 1 angeben, müsste die 2. Antwortmöglichkeit auch stimmen, wenn eine der 1., 3. oder 4. richtig wäre. Da man dann aber mindestens 16 Kreuze gesetzt hat, es aber nur 15 Punkte auf die Aufgabe gibt, kann man daraus schließen, dass nur die Antwort “mindestens 1” richtig sein kann.
Ich weiß, dass man jetzt davon ausgeht, dass die anderen 14 Kreuze mit Sicherheit richtig sind, aber da kann man sich meiner Meinung nach sicher sein
Also behaupte ich, dass die Lösung “mindestens 1” lautet, da alles andere für mich keinen Sinn machen würde, solange man den Fall (Baum = Wurzel) nicht beachtet und die Definition der Höhe eines Baumes aus der Vorlesung verwendet.

[nici]

---

Hätte da auch mal ne kurze frage zum O-kalkül…
in einer klasur lösung stand die lösung von:
log_16(n^3)=log(n)
bedeutet das:
(wenn a und b Konstanten sind)
log_a(n^b)=O(log(n)???
MfG

EDIT: Bei obiger Klausurlösung stand unsicher dabei.

[meisterT]

---

http://de.wikipedia.org/wiki/Logarithmus#Basisumrechnung

[Volschaf]

---

Bzw. auch http://de.wikipedia.org/wiki/Logarithmus#Potenzen

[hjk]

AVL-Frage
Hallo zusammen!

Ich weiß, ich bin recht früh dran mit meiner Vorbereitung/meinen Fragen.
Aber ich hätte eine kleine Frage zum Blatt 12 Aufgabe 4b) (siehe Anhang).

Kann mir jemand sagen, wie der Endzustand des AVL-Baumes nach der Reorganisation aussieht?
Meine Lösung ist falsch (laut Korrektur).

Attachment:
AVL.png: https://fsi.cs.fau.de/unb-attachments/post_129892/AVL.png

[_hedgehogs_dilemma_4]

---

siehe anbei - sollte laut korrektur stimmen

EDIT: zwei kugeln sind mir von links nach rechts verrutscht - ist korregiert anbei

Attachment:
avl_trees.jpg: https://fsi.cs.fau.de/unb-attachments/post_129894/avl_trees.jpg

[meisterT]

---

Probier’s doch selbst aus: http://www.qmatica.com/DataStructures/Trees/AVL/AVLTree.html

[meisterT]

---

[quote=[hedgehogs dilemma = 42]]
siehe anbei - sollte laut korrektur stimmen
[/quote]

nein, dein AVL-Baum ist kein Suchbaum mehr.