Informatiker Board | Druckvorschau: Bäume

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Bäume (http://www.informatikerboard.de/board/thread.php?threadid=2261)

Geschrieben von Batista am 09.05.2015 um 13:43:

Bäume

directupload.net/file/d/3982/87mq4l75_jpg.htm

Es sind insgesamt n Knoten und wieso sagt man dann, dass es genau n-1 nicht null Zeiger gibt, statt n null nicht Zeiger?

Ich verstehe nicht, wieso ein Knoten auf null zeigt?

Geschrieben von eulerscheZahl am 09.05.2015 um 14:02:

Ein Knoten hat einen Inhalt (z.B. eine Zahl) und k Nachfolgeknoten, auf die er verweist. Irgendwo ist aber der letzte Knoten, der keinen Nachfolger mehr hat. Trotzdem benötigt er den Speicherplatz, mit dem er den Verweis auf seine Nachfolger speichern könnte, das ist der verschenkte Speicherplatz.

Und da auf den Wurzelknoten nicht verwiesen wird und auf jeden anderen genau einmal, gibt es bei n Knoten n-1 Zeiger, die nicht null sind.

Zitat:

statt n null nicht Zeiger

Kapier ich nicht. Wenn sich die Frage nicht geklärt hat, bitte ich um bessere Beschreibung.

Geschrieben von Batista am 09.05.2015 um 14:15:

Ich habe immer noch Schwierigkeiten das zuverstehen.
Jeder Knoten hat insgesamt k Nachfolgeknoten, damit für n Knoten n*k insgesamt Zeigern ?

Zitat:

Original von eulerscheZahl

Und da auf den Wurzelknoten nicht verwiesen wird und auf jeden anderen genau einmal, gibt es bei n Knoten n-1 Zeiger, die nicht null sind.

Also besitzt man n*k-(n-1) Zeiger, die auf Null zeigern?

Geschrieben von eulerscheZahl am 09.05.2015 um 14:20:

Richtig.
Die Formel hast du übrigens auch im Script stehen.

Geschrieben von Batista am 09.05.2015 um 14:43:

Kannst du folgende erklären, vielleicht sogar beweisen?

"Entscheidungsbaum für n Elemente hat eine minimale Höhe von log_2(n!)"(binären Baum)

Mein versuch :
bei n Elementen entspricht ein Blatt eins der Permutationen

Wenn man 3 Elementen haben und mit 3!=6 mögliche Anordnungen der Elementen

Um 3 Elemente miteinander zu vergleichen benötigt man auch 3 Knoten also 2^3=8 Blätter, die dabei entstehen

Wenn es n Elemente gibt dann gilt 2^n<n! ist doch im -wiederspruch zur Aussage?

Geschrieben von eulerscheZahl am 09.05.2015 um 15:01:

Ich wei0 nicht, was mit einem "Entscheidungsbaum für n Elemente" gemeint ist.

Geschrieben von Batista am 09.05.2015 um 15:03:

directupload.net/file/d/3982/rv628iaj_jpg.htm

Geschrieben von eulerscheZahl am 09.05.2015 um 15:07:

Ah, verstehe.
Bei n Elementen gibt es m=n! Anordnungsmöglichkeiten, wie du schon erkannt hast.
Und Die Höhe des Baums mit m Elementen ist $[latex]\lceil\log_2(m)\rceil[/latex]$ , also nach Rücksubstitution $[latex]\lceil\log_2(n!)\rceil[/latex]$

Zitat:

Um 3 Elemente miteinander zu vergleichen benötigt man auch 3 Knoten also 2^3=8 Blätter, die dabei entstehen

Nein, du brauchst du 6 Blätter.

Geschrieben von Batista am 09.05.2015 um 15:19:

Gibt eine Formel für die Maximalanzahl Höhe, die sich aus den Elementen errechnen lässt?

Geschrieben von eulerscheZahl am 09.05.2015 um 15:22:

Meinst du, weil in deinem Script das minimal fett geschrieben ist?
Das liegt eben am balancierten Baum, das andere Extrem wäre eine Liste, also Höhe n!

Ich hoffe, ich habe deine Frage richtig verstanden.

Geschrieben von Batista am 09.05.2015 um 15:27:

Wir haben n-elmente und wir wollen diese sortieren. Was ist worst case? und wie groß ist es?

Die Sortierverfahren haben mindestens eine Laufzeit von O(n *log n), sind doch sehr gute Algorithmen, die das erfüllen?

Geschrieben von eulerscheZahl am 09.05.2015 um 15:32:

Das kommt auf den Algorithmus an.
Mergesort geht immer in $[latex]\mathcal{O}(n\cdot\log(n))[/latex]$ , während es bei Quicksort auch n^2 sein kann.