Binärbäume, n-äre Bäume, AVL-Bäume, Rot-Schwarz-Bäume, B-Bäume (Mehrwegbäume)
Idee: Man ersetzt mit dem größten (rechtesten) Element aus dem linken Teilbaum (oder umgekehrt).
Lässt sich die Idee nicht sauber implementieren, kann es besser sein, den rechten Teilbaum einfach an das größte Element aus dem linken anzuhängen und dann den Baum wieder auszugleichen.
Höhe ist logarithmisch, aber warum? → s. gprot18
Die mittlere Weglänge im Baum ist die Summe der Weglängen zu den Knoten durch die Anzahl der Knoten.
Die Höhe eines vollständigen binären Baumes wächst nur logarithmisch mit der Knotenzahl.
B-Bäume sind Mehrweg-Suchbäume. Alle Blätter eines B-Baums haben die gleiche Tiefe. (Baum ist vollständig.)
2-3-Bäume bzw. 2-4-Bäume sind B-Bäume der Ordnung 3 bzw. 4. Die 2 gibt die minimale Anzahl der Kinder pro Knoten an.
Nein, es handelt sich ja um Mehrwegbäume. Ein B-Baum kann aber den Aufbau eines Binärbaums haben → jeder Knoten hat höchstens zwei Kinder.
Adjazenzliste (Knotenliste), Adjazenzmatrix
Abstrakte Datentypen beschreiben Wertemengen ausschließlich durch die darauf zulässigen Operationen.
Datenabstraktion ist die Anwendung des Geheimnisprinzips auf Datenstrukturen. Bestimmte Programmteile sind für den Benutzer nicht sichtbar, bzw. der Zugriff nicht gestattet. Man abstrahiert von der Implementierung und charakterisiert die Datenstruktur über die Operationen auf ihr. (Der Zugriff erfolgt dann nur noch über eine Schittstelle.)
Man unterscheidet Universelle Polymorphie (mit Inklusions- und Parametrischer Polymorpie) und Ad-hoc-Polymorphie (→ gleiche Funktionsnamen mit verschiedenen formalen Parametern).
Können, müssen aber nicht. (→ s. 1.)
Call-by-value, Call-by-reference, Call-by-result (=Call-by-value-return), Call-by-name. (+Erklärung)
Call-by-value für primitive Datentypen, Call-by-reference für Objekte.
Bei der verzögerten Auswertung wird ein Ausdruck erst dann durch seinen Wert ersetzt, wenn er gebraucht wird. Dadurch lassen sich z.B. in Haskell unendlich große Datenstrukturen definieren (liste = 'a':liste). → s. gprot40
Dynamische Typzuordnung zur Laufzeit (→ Polymorphie)
Ein design pattern zur Entkoppelung von der Implementierung - nur die Funktionalität ist wichtig.
Das Prinzip des Greedy-Algorithmus ist es, in jedem Teilschritt so viel wie möglich zu erreichen (lokales Optimum). Unter Umständen wird dadurch jedoch das globale Optimum nicht erreicht.(Bsp.: Wechselgeld)
Algorithmus zum finden kürzester Wege in Graphen. (+Erklärung)
Algorithmus zum finden des kleinsten aufspannenden Baums. (+Erklärung)
Auch ein Algorithmus zum finden des kleinsten aufspannenden Baums. (+Erklärung)
Ein Algorithmus zum finden einer optimalen Binärcodierung von Zeichen. Erzeugt wird ein sog. kommafreier Präfixcode. (+Erklärung)
Linare Rekursion und nicht lineare Rekursion. Bei der linearen Rekursion unterscheidet man noch endrekursive und nicht endrekursive Funktionen.
Modellierende / algebraische Spezifikation
Man legt sich bereits auf eine Implementierung fest.
Verifikation mit Hoare Kalkül → Vorbedingung {P} wird in Nachbedingung {Q} überführt.
{P} S {Q} mit Zuweisungsaxiom {P}x = e{P[e/x]} → alles was vorher für e galt, gilt jetzt für x
...partielle Korrektheit nachgewiesen, totale Korrektheit mit Terminierungsfunktion...
Die Invariante