EINI-I Einführung in die Informatik für Naturwissenschaftler und Ingenieure I

EINI-IEINI-IEinführung in die Informatik Einführung in die Informatik für Naturwissenschaftler und für Naturwissenschaftler und

Ingenieure IIngenieure I

Vorlesung 2 SWS WS ‘99/00

Gisbert Dittrich

FBI Unido

dittrich@cs.uni-dortmund.de

2

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Gliederung Kapitel 8Gliederung Kapitel 8

• Motivation – Suchen in einfach verketteter Liste

+ deren Nachteile

• Binärer Suchbaum– Grobideen: Suchen, Suchstruktur– Idee Baum– Binärer Baum, Knotenmarkierung, Implementierung

knotenmarkierter bin. Bäume, Suchbaum – Suchen– Einfügen– Analyse

3

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Suchen in einer ListeSuchen in einer Liste

bool Suchen (int i, Liste * L) { if (L == NULL) return false; else return

(L->Element == i? true: Suchen(i, L->weiter));}

4

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Suchen in einer ListeSuchen in einer Liste

• Ist L die leere Liste: i kann nicht in L sein.

• Ist L nicht leer– entweder i == L->Element

– oder i wird in L->weiter gesucht

5

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Suchen in einer ListeSuchen in einer Liste

• Problem: langsame Suche– jedes Element muß bei einer erfolglosen Suche

betrachtet werden

– also: Suchzeit proportional zur Anzahl der Elemente in der Liste (lineare Suchzeit)

6

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Suchen in einer ListeSuchen in einer Liste

• Beispiel– erfolglose Suche bei 10 Elementen braucht 10

Vergleiche, also (pro Vergleich 10 sec.) 10 sec = 2,7 h

– Bei geschickter Anordnung der Daten geht´s mit 35 Vergleichen, also in 3.5.10 sec.

7

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Suche „in einer Hälfte“Suche „in einer Hälfte“

• Grobidee: – Suchen in geordneter "Liste" durch Überprüfen des

"mittleren" Elementes + Fortsetzung in einer Hälfte

– Beispiel:

1 2 3 4 5 6 7 8 9

2 4 6 7 8 17 19 36 40

k: 19 k:5OK : nicht vorhanden

8

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Suchstruktur

Aufgabe: Trage die Zahlen 17, 4, 36, 2, 8, 19, 40, 6, 7 in eine baumförmige Struktur so ein:

17

4 36

2 8

6

7

19 40

9

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Ziel: Binärer SuchbaumZiel: Binärer Suchbaum

• Zu diesem Ziel nacheinander definieren:– (Binärer) Baum– Knotenmarkierter binärer Baum– Binärer Suchbaum

10

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Idee von BaumIdee von Baum

KünstlerischAbstrahiert 1Abstrahiert 2Die Informatiksicht:

11

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binärer BaumBinärer Baum

Definition: (Binärer Baum)1.) Der "leere" Baum ist ein binärer Baum mit der

Knotenmenge .

2.) Seien Bi binäre Bäume mit den Knotenmengen Ki ,

i = 1,2. Dann ist auch B = (w, B1, B2) ein binärer Baum mit der Knotenmenge

K = {w} –K1 – K2.

(– bezeichnet disjunkte Vereinigung.)

3.) Jeder binäre Baum B läßt sich durch endlich häufige Anwendung von 1.) oder 2.) erhalten.

12

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binärer BaumBinärer Baum

• Sprech-/Darstellungsweisen (im Falle 2.)):Sei B = (w, B1, B2) binärer Baum

w heißt Wurzel, B1 linker und B2 rechter Unterbaum.

B1 B2

Wurzel

linker Unterbaum

rechter Unterbaum

w

13

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binärer BaumBinärer Baum

• Darstellung eines Beispiels nach Definition: B1 = (k1, , (k2, (k3, , ), )).

k1

k2

k3

14

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Terminologie Terminologie Binäre BäumeBinäre Bäume

Wurzel

innerer Knoten

Blatt

15

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Knotenmarkierter binärer BaumKnotenmarkierter binärer Baum

Definition: Sei M eine Menge. (B, km) ist ein knotenmarkierter binärer Baum

(mit Markierungen aus M)

:¤1.) B ist binärer Baum (mit Knotenmenge K = K(B))

2.) km: K --> M Abbildung.

(Markierung/Beschriftung der Knoten k K mit Elementen m M)

16

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Knotenmarkierter binärer Baum binärer Baum

Beispiel: (M := $, $ := Menge der ganzen Zahlen)

damit existiert auf M eine Ordnung ! Damit: "Übliche" Darstellung der Knotenbeschriftung km durch

"Anschreiben" der Beschriftung an/in die Knoten.

k1

k2

k3

24

18

16

17

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Datentyp Datentyp BinBaumBinBaum

• Implementierung knotenmarkierter binärer Bäume durch eine struct mit Zeigern:– Inhalt, (hier z. B.) ganzzahlig (Später allgemeiner möglich)

– Zeiger jeweils auf den linken und den rechten Unterbaum

struct BinBaum { int Element; BinBaum *Lsohn, *Rsohn; }

18

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binäre SuchbäumeBinäre Suchbäume

Definition: (B, km) ist ein binärer Suchbaum (über $)

:¤1.) (B, km) ist ein binärer, knotenmarkierter Baum.

2.) Ist w die Beschriftung der Wurzel w, so ist die Wurzelmarkierung im linken Unterbaum kleiner als w, die Wurzelmarkierung im rechten Unterbaum größer als w. (Jeweils, sofern diese vorhanden.)

3.) Ist (B, km) mit B , B = (w, B1, B2), so sind (Bi,kmi) mit kmi := km|Bi (i= 1,2) binäre Suchbäume.

19

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binäre SuchbäumeBinäre Suchbäume

Beispiel:

Aufgaben im Zusammenhang mit (binären) Suchbäumen:• Suchen nach Markierungen/Elementen im

Suchbaum• Aufbau solcher Bäume• Abbau, z. B. Entfernen eines Knotens mit

Markierung• Durchlaufen aller Knoten

20

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binäre Suchbäume: SuchenBinäre Suchbäume: Suchen

Gegeben: ein binärer Suchbaum (durch Zeiger B darauf),

ganze Zahl k

Problem:

Ist k in durch B bezeichneten Baum gespeichert?

Lösungsidee: Stimmt B->Element mit k überein: Antwort ja

Gilt B->Element < k: suche in B->Rsohn

Gilt B->Element > k: suche in B->Lsohn

Ist B leer, Antwort nein

21

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binäre Suchbäume: SuchenBinäre Suchbäume: Suchen

17

4 36

2 8

6

7

19 40

Suche nachdem Element 5

Suche nachdem Element 19

22

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binäre Suchbäume: SuchenBinäre Suchbäume: Suchen

bool Suche (BinBaum * B, int k) {if (B == NULL) return false;else {

if (B->Element == k) return true;else if (B->Element < k)

return Suche(B->Rsohn, k);Suche(B->Rsohn, k);else if (B->Element > k)

return Suche(B->Lsohn, k);Suche(B->Lsohn, k);}

}

23

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binäre Suchbäume: EinfügenBinäre Suchbäume: Einfügen

• Aufbau durch wiederholtes Einfügen in einen leeren binären Suchbaum

• Einfügeoperation für binären Suchbaum *B und eine ganze Zahl k– B == NULL: erzeuge neuen Knoten, weise ihn B zu

und setze B->Element = k– B != NULL

• B->Element < k: Einfügen von k in B->RSohn• B->Element > k: Einfügen von k in B->LSohn

24

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binäre Suchbäume: EinfügenBinäre Suchbäume: Einfügen

BinBaum *Einfuegen (BinBaum * B, int k) {

if (B == NULL){

Binbaum *Hilf = new BinBaum;

Hilf->Element = k; Hilf->Lsohn = Hilf->Rsohn = NULL;

return Hilf;

}

else {

if (B->Element < k)

B->Rsohn = Einfuegen(B->Rsohn, k);B->Rsohn = Einfuegen(B->Rsohn, k);

else if (B->Element > k)

B->Lsohn = Einfuegen(B->Lsohn, k);B->Lsohn = Einfuegen(B->Lsohn, k);

return B;

}

}

25

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Binäre Suchbäume: EinfügenBinäre Suchbäume: Einfügen

• Rekursion wichtiger Bestandteil der Funktion• Idee:

– suche den Unterbaum, in den eingefügt werden soll, – füge in den Unterbaum ein,– weise diesem Unterbaum das Resultat der Einfügung

zu.

26

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

weise dem Unterbaum

das Resultat der Einfügung zu

Kommentar: EinfügenKommentar: Einfügen

if (B->Element < k) B->Rsohn = Einfuegen(B->Rsohn, k);B->Rsohn = Einfuegen(B->Rsohn, k);else if (B->Element > k) B->Lsohn = Einfuegen(B->Lsohn, k);B->Lsohn = Einfuegen(B->Lsohn, k);return B;

Suche den Unterbaum, in den eingefügt wird

27

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Analyse: EinfügenAnalyse: Einfügen

• Wie schnell geht das eigentlich?• Maß für die Güte eines Algorithmus:

– Anzahl von Operationen und – Speicherplatz-Verbrauch

• hier: – Speicherplatz: pro Knoten eine Instanz von BinBaum,

also relativ uninteressant.– Operationen sind hier Vergleiche: interessant

28

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Analyse: EinfügenAnalyse: Einfügen

• Frage: wieviele Vergleiche sind beim Einfügen (oder bei der erfolglosen Suche) notwendig?

• Antwort: nicht so leicht zu geben:– ist der günstigste Fall gemeint? (klar: 1)– ist der ungünstigste Fall gemeint? (auch ziemlich

klar: längster Pfad im Baum)– ist der durchschnittliche Fall gemeint? (völlig unklar)

29

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Suchen: ungünstigster FallSuchen: ungünstigster Fall

• Erfolglose Suche: – suche von der Wurzel zu einem Blatt, jeder Knoten

entspricht einem Vergleich.

• Höhe eines Baums: – gibt den längsten Pfad von der Wurzel zu einem Blatt

an. Ist rekursiv definiert• Höhe des leeren Baums ist 0,

• Höhe eines nicht-leeren Baums ist 1 + max{Höhe Lsohn, Höhe Rsohn}

30

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Höhe eines binären BaumsHöhe eines binären Baums

17

4 36

2 8

6

7

19 40

37

Der Baum hat die Höhe 5

31

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Suchen: ungünstigster FallSuchen: ungünstigster Fall

• Es gilt der Satz:

Ein binärer Baum der Höhe n hat zwischen n und 2 n- 1 Knoten.– Daraus folgt: k Knoten können in einem binären

Baum gespeichert werden, der eine Höhe zwischen ~log2 k und k hat

– Also: der schlechteste Fall bei der erfolglosen Suche in einem binären Suchbaum mit k Elementen liegt bei k Vergleichsoperationen

32

Kap 8: Binäre Bäume + Suchen Vorl “EINI-I"Prof. Dr. G. Dittrich

20.1.2000

Suchen: zu erwartender FallSuchen: zu erwartender Fall

• Die erfolglose Suche in einem binären Suchbaum mit k Elementen erfordert im Durchschnitt proportional zu log k Vergleichsoperationen.

• Recht kompliziert herzuleiten.