Bäume |
| 09.05.2015, 13:43 | Auf diesen Beitrag antworten » | ||
| Batista | 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? |
||
|
|
|||
| 09.05.2015, 14:02 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | 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.
Kapier ich nicht. Wenn sich die Frage nicht geklärt hat, bitte ich um bessere Beschreibung. |
||
| 09.05.2015, 14:15 | Auf diesen Beitrag antworten » | ||
| Batista | Ich habe immer noch Schwierigkeiten das zuverstehen. Jeder Knoten hat insgesamt k Nachfolgeknoten, damit für n Knoten n*k insgesamt Zeigern ?
Also besitzt man n*k-(n-1) Zeiger, die auf Null zeigern? |
||
| 09.05.2015, 14:20 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | Richtig. Die Formel hast du übrigens auch im Script stehen. |
||
| Anzeige | |||
|
|
|||
| 09.05.2015, 14:43 | Auf diesen Beitrag antworten » | ||
| Batista | 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, 15:01 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | Ich wei0 nicht, was mit einem "Entscheidungsbaum für n Elemente" gemeint ist. |
||
| 09.05.2015, 15:03 | Auf diesen Beitrag antworten » | ||
| Batista | directupload.net/file/d/3982/rv628iaj_jpg.htm |
||
| 09.05.2015, 15:07 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | 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
Nein, du brauchst du 6 Blätter. |
||
| 09.05.2015, 15:19 | Auf diesen Beitrag antworten » | ||
| Batista | Gibt eine Formel für die Maximalanzahl Höhe, die sich aus den Elementen errechnen lässt? |
||
| 09.05.2015, 15:22 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | 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. |
||
| 09.05.2015, 15:27 | Auf diesen Beitrag antworten » | ||
| Batista | 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:32 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | Das kommt auf den Algorithmus an. Mergesort geht immer in |
||
| 09.05.2015, 15:34 | Auf diesen Beitrag antworten » | ||
| Batista | Top erklärt 
Ich meld mich wieder wenn was unklar ist. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
