Lineare Datenstrukturen und Binärbäume: Zusammenfassung – Informatik Leistungskurs

1

Die dynamische Reihung

Eine Reihung, die wächst und schrumpft — Zugriff auf jedes Element über den Index 0 … getLength() − 1.

Einfügen und Anhängen

append hängt hinten an; insertAt schiebt ein, der Rest rückt nach hinten.

append(x) · insertAt(i, x)

Ersetzen und Löschen

setItem ersetzt ohne Verschieben; delete entfernt, der Rest rückt nach vorn.

setItem(i, x) · delete(i)

Durchlaufen

Zählschleife über alle gültigen Indizes, Standardalgorithmen Summe, Maximum, Suche.

for (i = 0; i < getLength(); i++)

Löschen in Schleifen

Rückwärts laufen — sonst wird nach jedem delete ein Element übersprungen.

for (i = getLength() − 1; i ≥ 0; i−−)

DynArray

append · insertAt · setItem · delete · getItem · getLength · isEmpty

Gültige Indizes: 0 ≤ i ≤ getLength() − 1.

Letzter Index

Das letzte Element steht an getLength() − 1. getItem(getLength()) ist ein Laufzeitfehler.

2

Stapel und Schlange

Zwei Strukturen ohne Index: Der Stapel gibt das neueste Element zuerst heraus, die Schlange das älteste.

Stapel: LIFO

push legt oben auf, pop nimmt oben weg und liefert, top schaut nur nach.

push(x) · pop() · top() · isEmpty()

Schlange: FIFO

enqueue stellt hinten an, dequeue entnimmt vorn, head schaut nur nach.

enqueue(x) · dequeue() · head() · isEmpty()

Typische Algorithmen

Klammerprüfung und Postorder-Auswertung mit dem Stapel, Rundlauf und Rotation mit der Schlange.

q.enqueue(q.dequeue())

Struktur wählen

Entscheidend ist, in welcher Reihenfolge Daten wieder gebraucht werden.

beliebig → DynArray · neuestes → Stapel · ältestes → Schlange

Stapel und Schlange

Stapel: LIFO · Schlange: FIFO

Vor pop/top bzw. dequeue/head immer mit isEmpty() prüfen.

Umladen dreht um

Beim Umladen auf einen Hilfsstapel dreht sich die Reihenfolge um; über eine Schlange bleibt sie erhalten.

3

Der Binärbaum

Jeder Knoten hat höchstens zwei Kinder. Ein Binärbaum ist leer oder besteht aus Wurzel, linkem und rechtem Teilbaum.

Begriffe

Wurzel, innerer Knoten, Blatt (beide Teilbäume leer), Kante, Teilbaum, leerer Baum.

isLeaf() ⇔ links und rechts leer

Tiefe und Höhe

Tiefe: Kanten bis zur Wurzel (Wurzel: 0). Höhe: Anzahl der Ebenen (leerer Baum: 0).

n ≤ 2^h − 1

BinTree-Operationen

Ein BinTree-Objekt ist immer ein ganzer Teilbaum; setItem auf einem leeren Baum legt zwei leere Teilbäume an.

isEmpty · getItem · setItem · isLeaf · getLeft · setLeft · getRight · setRight · setEmpty

Rekursiv rechnen

Ergebnis aus Wurzel und den Ergebnissen der beiden Teilbäume; Abbruch beim leeren Baum.

hoehe = 1 + max(hoehe(L), hoehe(R))

Binärbaum

leer — oder Wurzel + linker Teilbaum + rechter Teilbaum

Ein Baum mit n Knoten hat n + 1 leere Teilbäume.

Erst prüfen, dann zugreifen

getItem(), getLeft() und getRight() auf einem leeren Baum sind Laufzeitfehler — isEmpty() kommt immer zuerst.

4

Die Traversierung

Jeden Knoten genau einmal verarbeiten — rekursiv, links immer vor rechts.

Preorder

Wurzel zuerst: Baum kopieren, mit Struktur ausgeben.

W – L – R

Inorder

Wurzel zwischen den Teilbäumen: im Suchbaum sortierte Ausgabe.

L – W – R

Postorder

Wurzel zuletzt: Rechenbaum auswerten (UPN), Baum löschen.

L – R – W

Aufwand und Rekonstruktion

Ein Aufruf je Knoten und je leerem Baum. Preorder + Inorder legen einen Baum eindeutig fest.

A = 2n + 1

Traversierung

Preorder W L R · Inorder L W R · Postorder L R W

Umrundung links herum: Punkt links = Pre, unten = In, rechts = Post.

Nicht ebenenweise

Die Preorder geht nach der Wurzel erst ganz in den linken Teilbaum — sie liest den Baum nicht Zeile für Zeile.

5

Der binäre Suchbaum

Links kleiner, rechts größer — für jeden Knoten und seinen ganzen Teilbaum.

Suchen

x mit der Wurzel vergleichen: gleich → gefunden, kleiner → links, größer → rechts, leer → nicht vorhanden.

höchstens h Vergleiche

Einfügen

Suchen, bis ein leerer Baum erreicht ist; dort wird x als Blatt gesetzt. Vorhandene Werte werden nicht doppelt eingefügt.

b.setItem(x) am Ende des Suchpfads

Ausgeglichen

Alle Ebenen bis auf die letzte voll: kleinste Höhe, schnellste Suche.

h = ⌈log₂(n + 1)⌉

Entartet

Sortiert eingefügt entsteht eine Kette: Suchen wird linear, der Aufbau quadratisch.

h = n · Aufbau n(n − 1)/2

Suchbaum

Suchen und Einfügen folgen demselben Pfad von der Wurzel zum Blatt

Der Aufwand hängt von der Höhe ab — und die von der Einfügereihenfolge.

Ordnung für ganze Teilbäume

Es reicht nicht, nur Eltern und Kinder zu vergleichen: Auch die Enkel im linken Teilbaum müssen kleiner als die Wurzel sein.