Datenstrukturen (Heap, B-Baum, AVL-Baum, F-Baum, CBinTree, Inorder, CountLeaves)

Hallo.

Ich hab da ma wieder ne Hausaufgabe, kann mir da jemand zu einzelnen Aufgaben Tipps geben, wo man die Lösungen nachlesen kann?

Teil 1

1. Gibt es Bäume, die gleichzeitig Heap und binärer Suchbaum sind? Begründen Sie Ihre Antwort!

2. Ihnen sei eine beliebige Permutation (a0, a1, . . . , an−1) : a_i Element N gegeben. Beschreiben Sie eine Möglichkeit, mit der Sie daraus in weniger als O(n²) Vergleichen einen ausgeglichenen Suchbaum erzeugen können!

3. Unter welchen Umständen muss in einem AVL-Baum eine Doppelrotation ausgeführt werden?

4. Geben Sie die minimale Tiefe eines Blattknotens im n-ten Fibonacci-Baum an! Beweisen Sie Ihre Aussage!

Teil 2

1. Aus der Vorlesung kennen Sie die Klasse CBinTree. Schreiben Sie in C++ oder Pseudocode eine Funktion, die eine iterative Inorder-Traversierung auf einem beliebigen Binärbaum realisiert! Erläutern Sie genau, welche Modikationen oder Ergänzungen Sie ggf. an der Datenstruktur vornehmen!

2. Schreiben Sie eine Funktion CBinTree::CountLeaves(), die die Anzahl der Blätter in einem beliebigen Binärbaum zählt und diese zurückgibt.

Danke ma wieder!!!

1.2 Wenn ich die Aufgabe verstanden habe, gehts einfacherweise doch auch indem alle Elemente der Reihe nach in einen AVL-Baum einfügt, dann liegt man mit den Vergleichen in O(n*log(n)).

2.1 Rekursiv geht das sehr sehr sehr einfach (wie so vieles bei Bäumen)

finix

Hey, cool, Hausaufgaben!

Poste mal deine Ansätze, dann kriegen wir das bestimmt hin...

Also

1.1: Heap == bin. Baum? Vielleicht wenn die Eigenschaften vom bin. Baum, Sortierung, gleich dem Heap ist? Spezialfall?

1.2: keine Ahnung

1.3: Doppelrotation ist nötig, wenn Höhenunterschied an inneren Teilbäumen auftritt (nach Rebalancierung). Steht bei wikipedia, keine Ahnung, ob das richtig ist.

1.4: Meinen die da das Blatt das als erstes kommt und der Abstand zur "obersten" Wurzel der kleinste ist? Also im F-Baum "irgendwie" rekursiv runtergehen und dann bei der ersten minimalsten Höhe, wenn Blatt aufhören, wie soll ich das beweisen?

2.1: Inorder-Traversierung: linker Unterbaum, Wurzel, rechter Unterbaum, wees noch ne ma wie man das rekursiv implementiert. (Traversierung durch einen Suchbaum erhält man eine aufsteigend sortierte Folge)

2.2: muss man da jetzt da in dem baum alles durchgehen und gucken, wenn rechter und linke "sohn" nicht vorhanden ist, dann countern?

Hans im Pech schrieb:

1.2 Wenn ich die Aufgabe verstanden habe, gehts einfacherweise doch auch indem alle Elemente der Reihe nach in einen AVL-Baum einfügt, dann liegt man mit den Vergleichen in O(n*log(n)).

2.1 Rekursiv geht das sehr sehr sehr einfach (wie so vieles bei Bäumen)

Bei einem binären Suchbaum im Allgemeinen ist das kleinste/größte Element, aber nicht in der Wurzel. Du hast bei einem Heap ja keine Sortierung vorgegeben, sondern nur, dass das Parent größer/kleiner als seine Kinder ist.
Bei einem Suchbaum ist das im Allgemeinen aber nicht der Fall dort sind die Elemente im linken Kind kleiner/größer und die Elemente im rechten Kind größer/kleiner als das Element im Elternknoten.

Wenn man also keine Einschränkungen auf die Eingabemenge machen darf, dann sehe ich nicht wie man einen Suchbaum erzeugen kann der die Heap-Eigenschaft erfüllt.