11. Rekursive Datenstrukturen - Welcome to BSCW … · – Ordnungsfunktion f ist für jedes Elementpaar (e 1, e 2) ... – Das Ende des Arrays erreicht haben ... (Ob wir gleiche

László Böszörményi ESOP Rekursive Datenstrukturen - 1

11. Rekursive Datenstrukturen• Lineare Listen

– Liste = leer | Element Liste1. Die leere Liste ist eine Liste2. Wird einer Liste ein Element angehängt, so erhalten wir

wiederum eine Liste

• Rekursive Implementierung von Listen– Die Klasse Node enthält „sich selbst“: Rekursion– Die Liste wird (über node.next) so lange „reduziert“,

bis wir zur trivialen (leeren) Liste kommen– Die Suche in einer Schleife wird durch den

rekursiven Abstieg ersetzt


Sortierte Listen• Auf den Elementen ist eine Ordnung definiert

– Ordnungsfunktion f ist für jedes Elementpaar (e1, e2) definiert:• f (e1) > f(e2), wenn e1 größer als e2 ist• f (e1) < f(e2), wenn e1 kleiner als e2 ist• f (e1) == f(e2), wenn e1 und e2 gleich sind

• Wir halten die Elemente nach dieser Funktion geordnet in der Liste

– Beim Einfügen müssen wir die richtige Stelle finden– Beim Suchen können wir die Ordnung ausnutzen

• Die Ordnung basiert oft auf einem Alleinmerkmal (einem Schlüsselwert), wie Matrikelnummer oder Name


Operationen auf sortierten Listen

-3keynext

1 4 9

3

previous actual

previous.next = x; x.next = actual;

x

Einfügen(key = 3)

-3keynext

1 4 9

previous actual

previous.next = actual.next;

Löschen(key = 4)

null

null

head

head


Interface Listpublic interface List { // 03.11.2000. LB

public boolean search (int key);// Retourniert true, wenn Knoten mit Schlüssel = key gefunden, sonst false

public void insert (int key); // Fügt einen Knoten mit Schlüssel=key ein// Wenn ein Element (Schlüssel=key) schon existiert: Neue zuerst einfügen

public boolean remove (int key);/* Retourniert false, wenn Knoten mit Schlüssel = key nicht gefunden,

sonst entfernt den Knoten aus der Liste und gibt true zurück */

public String toString (); // Wandelt die Liste in eine Zeichenkette um

} // List


Benutzerklasse sortierter Listenpublic class ListUser { // 03.11.2000. LB

static void useList(List list) {for (int i = 9; i > 0; i -= 2) list.insert(i); // Elemente EinfügenOut.println(list);for (int i = -2; i < 14; i+= 2) list.insert(i);Out.println(list);for (int i = -5; i < 16; i+= 4) {

if (list.remove (i)) Out.println(i + " entfernt ");else Out.println(i+ " nicht enthalten");

} // forOut.println(list);

} // useListstatic void main(String [] args) {

useList(new NonRekList ()); } // main

} // ListUser

( 1 3 5 7 9 )

( -2 0 1 2 3 4 5 6 7 8 9 10 12 )

-5 nicht enthalten-1 nicht enthalten3 entfernt 7 entfernt 11 nicht enthalten15 nicht enthalten

( -2 0 1 2 4 5 6 8 9 10 12 )


Nicht-rekursive Implementierung (1)public class NonRekList implements List { // 03.11.2000. LB

private class Node { // 03.11.2000. LBprivate int info;private Node next;private Node (int info, Node next) { this.info = info; this.next = next;}

} // Node

private Node head = null;

public boolean search (int key) { // Gibt true zurück, wenn gefundenNode actual = head; // „Lazy“ Auswertung ausnützen:while (actual != null && key > actual.info) actual = actual.next;return (actual != null) && (actual.info == key); // true, wenn gefunden

} // search


Nicht-rekursive Implementierung (2)

public String toString () { // Liste in Klammern als String zurückNode actual = head; String listString = "";while (actual != null ) {

listString += actual.info + " "; actual = actual.next;

} // whilereturn "( " + listString + ")";

} // toString


Nicht-rekursive Implementierung (3)public void insert (int key) { // Fügt Knoten mit Schlüssel=key ein

if ( (head == null) || (key <= head.info) ) // Bei Gleichheit wird dashead = new Node(key, head); // Neue zuerst eingefügt

else { // Richtige Stelle suchenNode previous = head, actual = head.next; while (actual != null && key > actual.info) {

previous = actual;actual = actual.next;

} // whileprevious.next = new Node(key, actual);

} // if

} // insert


Nicht-rekursive Implementierung (4)public boolean remove (int key) {// Entfernt Knoten mit key und retourniert true, wenn gefunden, sonst false

if (head == null) return false;else if (head.info == key) {

head = head.next; return true; // Element am Kopf entfernt} // if (head.info == key)else { Node previous = head, actual = head.next; // Suchen

while (actual != null && key > actual.info) {previous = actual; actual = actual.next;

} // whileif (actual == null) || (key != actual.info) return false; // Nicht gef.else { previous.next = actual.next; // Entfernt actual aus der Liste

return true; } // gefunden: true zurück} // if (head == null)

} // remove} // NonRekList


Rekursive Implementierung von Listen (1)public class RekList implements List { // 03.11.2000. LB

private class Node {private int info;private Node next;private Node (int info, Node next) { this.info = info; this.next = next;}

} // Nodeprivate Node head = null;protected Node search (int key, Node node) { // Nur in Subklassen bekannt

if (node == null) return null;else if (node.info == key) return node;else return search(key, node.next);

} // searchpublic boolean search (int key) {

Node n = search(key, head);if (n == null) return false; else return true;

} // search


Rekursive Implementierung von Listen (2)

protected String toString (Node node, String listString) {if (node == null) {

return listString;} else {

return toString (node.next, listString + node.info + " ");} // if

} // toString

public String toString () {return "( " + toString (head, "") + ")";

} // toString


Rekursive Implementierung von Listen (3)

protected Node insert(int key, Node node) {if ( (node == null) || (key <= node.info) )

return new Node(key, node);else {

node.next = insert(key, node.next);return node;

} // if} // insert

public void insert(int key) {head = insert(key, head);

} // insert


Rekursive Implementierung von Listen (4)private class Found { boolean found = false; } // Speichert nur einen Booleanprotected Node remove (int key, Node node, Found f) {

if (node == null) { return null; // Ende der Liste erreicht} else if (node.info == key) { // Gefunden

f.found = true; return node.next; } // if (node == key)

else { // Weitersuchennode.next = remove (key, node.next, f); return node; } // else

} // removepublic boolean remove (int key) {

Found f = new Found();head = remove (key, head, f);return f.found;

} // remove} // RekList


Lineares Suchen in einem Array

static int LinearSearch (int [] arr, int key) { // Iteratives lineares Suchenint i = 0;while ( (i < arr.length) && (arr[i] != key) ) i++;if (i == arr.length) return -1; // nicht gefunden: gibt -1 zurückelse return i; // gefunden an Stelle i

} // LinearSearch

• Wir müssen das Array durchsuchen, solange wir entweder– Das gesuchte Element gefunden haben oder– Das Ende des Arrays erreicht haben

• Implementierung (iterativ bzw. rekursiv)– Suchfunktion retourniert den Index des gefundenen Elementen bzw. -1

static int RekSearch (int [] arr, int key, int start) {// Rekursives lineares Suchenif (start == arr.length) return -1; // nicht gefunden : -1 zurückelse if (arr[start] == key) return start; // gefunden an Stelle startelse return RekSearch(arr, key, start + 1); // weitersuchen ab start+1

} // RekSearch


Bäume („Schnupperkurs“ – Rest in SW2)• Ein Baum ist ein gerichteter Graph, in dem jeder Knoten

außer der Wurzel genau einen Vorgänger („Vater“) hat• Eine Baumstruktur mit Grundtyp T ist entweder

1. Die leere Struktur oder2. Ein Knoten vom Typ T mit einer endlichen Anzahl verknüpfter

Baumstrukturen mit Grundtyp T (die sog. Teilbäume) Wurzel

Höhe = 3

• Bäume sind immer azyklisch• Pfadlänge: Die Anzahl der Kanten zwischen zwei Knoten• Höhe: Maximale Pfadlänge aus der Wurzel heraus

– Höhe des leeren Baumes = 0– Höhe eines Baumes der nur aus Wurzel besteht = 1


Binärbäume• In einem Binärbaum hat jeder Knoten höchstens 2

Nachfolger („Kinder“)• Binärbaum = leer | Knoten Binärbaum Binärbaum• Ein Binärbaum ist entweder leer oder besteht aus einem

Knoten (Wurzelknoten) und 2 Teilbäume

Höhe = 5

Wurzel

Linker „Sohn“ Rechter „Sohn“


Binäre Suchbäume• In einem binären Suchbaum (geordneten Binärbaum) gilt für

jeden Knoten, dass– Alle Schlüsselwerte im linken Teilbaum kleiner– Alle Schlüsselwerte im rechten Teilbaum größer oder gleich

sind, wie der Schlüsselwert im Knoten selbst (Ob wir gleiche Knoten rechts oder links einordnen ist Definitionssache)

50

20 70

10

5 10

35

40

60 90

85 95


Impliziter Suchbaum – Binäres Suchen• Wir suchen in einem geordneten Array

– Wir schauen rekursiv, ob ein Element in der linken oder rechten Hälfte des Arrays enthalten ist

– Ist die Größe des Arrays n, kostet das höchstens log2N Schritte (N ist die kleinste Zweierpotenz > n)

– Es wird implizit ein Suchbaum, der Höhe log2N aufgebaut

30, 71, 92, 233, 284, 315, 326, 357, 478, 559, 6110, 7211Suche von 28

315

92 478

30 233 326 6110

71 284 357 7211559

Höhe = 4 (log216)


Implementierung vom Binären Suchenstatic int BinSearch (int [] arr, int left, int right, int key) {/* Gibt den Index des gefundenen Elementen bzw. -1 (falls nicht gefunden) zurück */

int middle = left + (right - left) / 2; // Wurzel des nächsten TeilbaumsOut.println("arr[" + middle + "] = " + arr[middle]); // Testausgabeif (key == arr[middle]) return middle; // key == arr[middle]: gefundenelse if (key < arr[middle]) // key < arr[middle]: suche links

if (left < middle) return BinSearch(arr, left, middle - 1, key);else return -1; // nicht gefunden

else // key >= arr[middle]: suche rechtsif (middle < right) return BinSearch(arr, middle + 1, right, key);else return -1; // nicht gefunden

} // BinSearch

arr[5] = 3131 gefunden(in 1 Schritt)

arr[5] = 31arr[2] = 9arr[3] = 23arr[4] = 2828 gefunden

arr[5] = 31arr[8] = 47arr[10] = 61arr[11] = 7299 nicht gefunden

int [] q = {3, 7, 9, 23, 28, 31, 32, 35, 47, 55, 61, 72}; int x = BinSearch (q, 0, q.length - 1, 28);

Documents

11. Rekursive Datenstrukturen - Welcome to BSCW … · – Ordnungsfunktion f ist für jedes Elementpaar (e 1, e 2) ... – Das Ende des Arrays erreicht haben ... (Ob wir gleiche