 Bäume |
Batista
unregistriert
 |
|
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?
|
|
09.05.2015 13:43 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
09.05.2015 14:02 |
|
|
Batista
unregistriert
|
|
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?
|
|
|
09.05.2015 14:15 |
|
|
Batista
unregistriert
|
|
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?
|
|
|
09.05.2015 14:43 |
|
|
Batista
unregistriert
|
|
directupload.net/file/d/3982/rv628iaj_jpg.htm
|
|
|
09.05.2015 15:03 |
|
|
Batista
unregistriert
|
|
Gibt eine Formel für die Maximalanzahl Höhe, die sich aus den Elementen errechnen lässt?
|
|
|
09.05.2015 15:19 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
09.05.2015 15:22 |
|
|
Batista
unregistriert
|
|
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?
|
|
|
09.05.2015 15:27 |
|
|
Batista
unregistriert
|
|
Top erklärt 
Ich meld mich wieder wenn was unklar ist.
|
|
|
09.05.2015 15:34 |
|
|
|
