Benutzer-Werkzeuge
se:algorithmendatenstrukturen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
|
se:algorithmendatenstrukturen [2009-01-11 17:51] stefan |
se:algorithmendatenstrukturen [2009-01-17 14:33] stefan |
||
|---|---|---|---|
| Zeile 42: | Zeile 42: | ||
| * Operatoren auf den Stack legen | * Operatoren auf den Stack legen | ||
| * bei schließender Klammer den obersten Operator ausgeben | * bei schließender Klammer den obersten Operator ausgeben | ||
| + | |||
| + | ===== Bäume ===== | ||
| + | * Ein Baum ist eine nicht-leere Menge von Knoten und Kanten, die gewisse Bedingungen erfüllen. | ||
| + | * Ein Knoten ist ein Objekt, das einen Namen haben und weitere Informationen beinhalten kann. | ||
| + | * Eine Kante ist eine Verbindung zwischen zwei Knoten. | ||
| + | * Ein Pfad ist eine Folge von unterschiedlichen Knoten, die durch Kanten im Baum miteinander verbunden sind. | ||
| + | * Die Wurzel eines Baums ist ein besonderer Knoten, der den Ursprung des Baums kennzeichnet. Es gilt immer, dass es zwischen der Wurzel und jedem beliebigen anderen Knoten eines Baums genau einen Pfad gibt. | ||
| + | * Jeder Knoten (außer der Wurzel) hat genau einen Vorgänger, der sich direkt über ihm befindet und als sein direkter Vorgänger (parent) bezeichnet wird. Knoten, die sich direkt unter einem Knoten befinden, werden als seine direkten Nachfolger (children) bezeichnet. | ||
| + | * Entsprechend eines Familienstammbaums spricht man auch von einem Großelterknoten oder von Geschwisterknoten. | ||
| + | * Blätter, Endknoten und äußere Knoten sind Knoten ohne Nachfolger. | ||
| + | * Innere Knoten sind Knoten mit mindestens einem Nachfolger. | ||
| + | * Jeder Knoten ist die Wurzel eines Unterbaums, der aus ihm und den Knoten unter ihm besteht. | ||
| + | * Die Ebene eines Knotens ist die Anzahl der Knoten auf dem Pfad von diesem Knoten zur Wurzel, wobei der Knoten selbst nicht mitgezählt wird und die Höhe eines Baums ist seine höchste Ebenennummer. Die Pfadlänge eines Baums ist die Summe der Ebenen aller Knoten. | ||
| + | * Ein Wald ist ein Menge von Bäumen. | ||
| + | * Geordnete Bäume sind Bäume, bei denen die Reihenfolge der direkten Nachfolger bei jedem Knoten festgelegt ist. Ist diese Reihenfolge nicht fest vorgeschrieben, spricht man von ungeordneten Bäumen. | ||
| + | * Falls jeder Knoten nur eine bestimmte Anzahl n von direkten Nachfolgern haben darf, die in einer bestimmten Reihenfolge vorliegen müssen, spricht man von einem n-ären Baum. | ||
| + | |||
| + | ==== Binärbäume ==== | ||
| + | * Der einfachste Typ eines n-ären Baums ist der binäre Baum, für den Folgendes gilt: | ||
| + | * Es ist ein geordneter Baum mit zwei Typen von Knoten: inneren und äußeren Knoten. Innere Knoten haben immer maximal zwei direkte geordnete Nachfolger, die man auch als linker und rechter Nachfolger bezeichnet. Äußere Knoten sind Knoten ohne Nachfolger. | ||
| + | * Ein binärer Baum ist leer, wenn er nur aus einem äußeren Knoten besteht und keinen inneren Knoten besitzt. | ||
| + | * Ein voller binärer Baum ist ein binärer Baum, in dem sich in keiner Ebene, außer in der vorletzten, äußere Knoten befinden. | ||
| + | * Ein vollständiger binärer Baum ist ein voller binärer Baum, bei dem sich in der letzten Ebene nur äußere Knoten befinden. | ||
| + | * Für zwei Knoten in einem binären Baum gibt es immer nur genau einen Pfad, der sie verbindet. | ||
| + | * Ein binärer Baum mit n inneren Knoten hat n+1 äußere Knoten. | ||
| + | * Die äußere Pfadlänge eines binären Baums mit n inneren Knoten ist immer um 2n größer als die innere Pfadlänge. | ||
| + | * Ein Baum mit n Knoten hat immer n-1 Kanten. | ||
| + | * Die Höhe eines vollen binären Baums mit n inneren Knoten ist die nächste ganze Zahl zu log2(n). | ||
| + | * Binärbäume vereinen die Vorteile von Arrays (schneller Zugriff auf ein Element) mit den Vorteilen von Listen (leichtes Einfügen/Löschen eines Elements). | ||
| + | * Sie lassen sich am Besten mittels Rekursion verwalten. | ||
| + | * nicht-binäre Bäume können einfach als binäre Bäume implementiert werden, indem jeder Knoten zwei Zeiger bekommt: einen auf sein erstes Kind (verkettete Liste aller Kinder) und einen auf seinen nächsten Geschwisterknoten | ||
| + | * in balancierten Binärbäumen haben alle Knoten in etwa die gleiche Tiefe: bei n Knoten ist die Höhe log<sub>2</sub>(n+1) | ||
| + | * bei einem balancierten Binärbaum sind somit maximal log<sub>2</sub>(n+1) Vergleiche (=Höhe des Binärbaums) notwendig, um ein Element in einem solchen balancierten Binärbaum zu finden | ||
| + | |||
| + | ==== Traversierung ==== | ||
| + | * Preorder: Bearbeite zuerst die Wurzel, dann bearbeite den vollständigen linken Unterbaum und anschließend den vollständigen rechten Unterbaum zu dieser Wurzel. | ||
| + | * Inorder: Bearbeite zuerst den vollständigen linken Unterbaum, dann die Wurzel und anschließend den vollständigen rechten Unterbaum zu dieser Wurzel. | ||
| + | * Postorder: Bearbeite zuerst den vollständigen linken Unterbaum, dann den vollständigen rechten Unterbaum und schließlich zuletzt die Wurzel zu diesen Unterbäumen. | ||
| + | * Levelorder: Bei dieser Art der Traversierung wird von oben nach unten jede einzelne Ebene des binären Baums durchlaufen, wobei die einzelnen Ebenen von links nach rechts traversiert werden. | ||
| ===== Lineare Rekursion ===== | ===== Lineare Rekursion ===== | ||
| * eine Funktion heißt rekursiv, wenn sie sich selbst oder ein von ihr aufgerufenes Programm sie selbst wieder aufruft | * eine Funktion heißt rekursiv, wenn sie sich selbst oder ein von ihr aufgerufenes Programm sie selbst wieder aufruft | ||
| + | * Rekursion ist eine Wiederholung durch Schachtelung -> Schachtelmodell | ||
| * jede Rekursion kann durch entsprechende Wiederholungen ausgedrückt werden und umgekehrt | * jede Rekursion kann durch entsprechende Wiederholungen ausgedrückt werden und umgekehrt | ||
| * Beispiele für Anwendung von Rekursion | * Beispiele für Anwendung von Rekursion | ||
| Zeile 54: | Zeile 94: | ||
| * Fibonacci-Zahlen: ''F(0) = 1; F(1) = 1; F(n) = F(n - 2) + F(n - 1)'' | * Fibonacci-Zahlen: ''F(0) = 1; F(1) = 1; F(n) = F(n - 2) + F(n - 1)'' | ||
| * Binomialkoeffizient: ''n über k = 1, wenn n oder k = 0, sonst (n - 1 über k) + (n - 1 über k - 1)'' | * Binomialkoeffizient: ''n über k = 1, wenn n oder k = 0, sonst (n - 1 über k) + (n - 1 über k - 1)'' | ||
| - | * Pascal'sches Dreieck | + | * Pascal'sches Dreieck |
| + | |||
| + | ===== ToDo ===== | ||
| + | * Wichtige Bereiche im Skript mit Klebi kennzeichnen | ||
| + | * <del>Umwandlung Postfix/Infix</del> | ||
| + | * <del>Lineare Rekursion</del> | ||
| + | * <del>Binärbäume</del> | ||
| + | * <del>Traversierung von Binärbäumen implementieren </del> | ||
| + | * Komplexität von Algorithmen bestimmen, Laufzeitanalyse (quadratisch, kubisch etc.) | ||
| + | * Codeoptimierung | ||
| + | * Arrays mit Quicksort sortieren (C: qsort) | ||
| + | * Heapsort, Countingsort, Radixsort | ||
| + | * Backtracking (Was gibt vorgegebenes Programm aus?) | ||
se/algorithmendatenstrukturen.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
