Durchlaufen eines Binärbaumes

G.Heyer Algorithmen und Datenstrukturen1

Durchlaufen eines Binärbaumes- Baumdurchlauf (tree traversal): Verarbeitung aller

Baumknoten gemäß vorgegebener Strukturierung

- Rekursiv anzuwendende Schritte

1) Verarbeitete Wurzel: W

2) Durchlaufe linken UB: L

3) Durchlaufe rechten UB: R

- Durchlaufprinzip impliziert sequentielle, lineare Ordnung auf der

Menge der Knoten.

6 Möglichkeiten1 2 3 4 5 6

W L L W R R

L W R R W L

R R W L L W

Konvention:

linker UB vor rechten UB


3 Strategien

1) Vorordnung ( preorder ): WLR

2) Zwischenordnung (inorder): LWR

3) Nachordnung (postorder): LRW

Preorder: besuche Wurzel, traversiere linken Teilbaum, traversiere rechten Teilbaum

Postorder: traversiere linken Teilbaum, traversiere rechtenTeilbaum, besuche Wurzel

Inorder : traversiere linken Teilbaum, besuche Wurzel, traversiere rechten Teilbaum

Inorder heißt auch symmetrische Ordnung.


Beispiel:

28

12

3416

19 49

8 2915

31

Preorder: 28, 16, 12, 8, 15, 19, 34, 31, 29, 49Postorder: 8, 15, 12, 19, 16, 29, 31, 49, 34, 28Inorder: 8, 12, 15, 16, 19, 28, 29, 31, 34, 49

Hinweise: wenn man Baum von der Wurzel aus umfährt, erhält manPreorder durch Besuch aller Knoten, an deren linker Seite man

vorbeikommtPostorder durch Besuch aller Knoten, an deren rechter Seite man

vorbeikommtInorder durch Besuch aller Knoten, an deren unterer Seite man

vorbeikommt


Rekursive und Iterative Version: LWR

- Rekursive Version : LWR

LWR(Knotenzeiger Wurzel)

{

if (Wurzel != NULL)

{ LWR (Wurzel --> Lsohn);

Verarbeite (Wurzel --> Info);

LWR (Wurzel --> Rsohn);

}

} /* End LWR */


- Iterative Version: LWRZiel: effizientere Ausführung durch eigene

Stapelverarbeitung

Vorgehensweise:

Nimm, solange wie möglich linke Abzweigung und speichere den

zurückgelegten Weg auf einen Stapel.

Aktion 1: PUSH (S , Current);

Current = Current --> Lsohn ;

Wenn es links nicht mehr weiter geht, wird der oberste Knoten des Stapels ausgegeben und vom Stapel entfernt. Der Durchlauf wird mit dem rechten Unterbaum des entfernten Knotens fortgesetzt.

Aktion 2: WriteString (TOP(S) --> Info) ; /*Verarbeite Info */

Current = TOP(S) --> Rsohn;

POP(S);


Gefädelte Binärbäume

- Weitere Verbesserung von iterativen Durchlaufalgorithmen

- Methode benutzt einen „Faden“, der die Baumknoten in der

Folge der Durchlaufordnung verknüpft.

Zwei Typen von Fäden

• Rechtsfaden verbindet jeden Knoten mit seinem

Nachfolgerknoten in Durchlaufordnung.

• Linksfaden stellt die Verbindung zum

Vorgängerknoten in Durchlaufordnung her.


Einfügen• Neue Knoten werden immer als Blätter eingefügt• Aussehen des Baumes wird durch die Folge der Einfügungen bestimmt (Reihenfolge der Eingabeelemente!)

Einfügen in binären Suchbäumen

typedef struct Knoten {struct Knoten *Lsohn;Schluesseltyp Key;struct Knoten *Rsohn;} ;

typedef struct Knoten *Kptr;

Kptr Wurzel;


void Einfuegen (Knotenzeiger p, int k){

if ( p == NULL ) /* Leerer Baum */

{

p = (struct Knoten *) malloc (sizeof *p);

p --> leftson = NULL;

p --> rightson = NULL;

p --> key = k;

}

else if (k < p --> key) Einfuegen( p --> leftson, k ) ;

else if (k > p --> key ) Einfuegen ( p --> rightson, k ) ;

else printf („Schluessel bereits vorhanden \n“);

}


Problem: es können "degenerierte" Bäume entstehen (etwa Listen).

Entfernen eines Knotens:Sehr einfach: Entfernen eines BlattesEinfach: Entfernen eines Knotens p mit 1

Nachfolger:Knoten einfach durch Nachfolger ersetzen

Schwieriger: Entfernen eines Knotens p mit 2 Nachfolgern: Suche am weitesten links stehenden Knoten q im rechten Teilbaum (symmetrischen Nachfolger).

Ersetze p durch q, streiche q aus seiner ursprünglichen Position.


Knotenzeiger vatersymnach ( Knotenzeiger p)/* Liefert Zeiger auf Vater des symmetrischen */

/* Nachfolgers von p --> */

{

if ( p --> rightson --> leftson == NULL)

{

p = p --> rightson;

while ( p --> leftson --> leftson == NULL)

p = p --> leftson;

}

vatersymnach = p;

return vatersymnach;

}


void Entfernen (Knotenzeiger p, int k)/* Entfernt Knoten mit Schluessel k aus Baum mit Wurzel p */

Knotenzeiger q ;

{ if (p == NULL) printf („Schluessel nicht im Baum \n“);

if (k < p-->key) Entfernen ( p--> leftson, k);

else if ( (k > p --> key) Entfernen (p --> rightson, k );

else if ( p --> leftson == NULL) p = p --> rightson ;

else if (p --> rightson == NULL) p = p --> leftson ;

else /* zwei Nachfolger */

{ q = vatersymnach (p);

if ( q == p )

{ p --> key = q --> rightson.key ;

q --> rightson = q --> rightson.rightson; }

else { p --> key = q --> leftson.key;

q --> leftson = q --> leftson.rightson ; }

}

}


Suche in binären Suchbäumen

Direkte Suche:

(Vorgehensweise wie bei Suche nach Einfügeposition

Suchen eines Knotens (rekursive Version)

Suche ( Kptr Wurzel, Schluesseltyp Skey)

{

if (Wurzel == NULL) return NULL;

else if (Wurzel --> Skey < Key) return Suche(Lsohn, Skey);

else if (Wurzel --> Skey > Key) return Suche(Rsohn, Skey);

else return Wurzel;

}


Suchen eines Knotens (iterative Version)Finde (Ktpr Wurzel, Schluesseltyp Skey)

{ int Gefunden;

Gefunden = FALSE;

do {

if (Wurzel == NULL) Gefunden = TRUE;

else if(Wurzel --> Skey < Key) Wurzel = Lsohn;

else if (Wurzel --> Skey > Key) Wurzel = Rsohn;

else Gefunden = FALSE;

} while (Gefunden = TRUE);

return Wurzel;

} Sequentielle Suche

Einsatz eines Durchlauf-Algorithmus (Zwischenordnung)


Binäre Suchbäume: ZugriffskostenKostenmaß: Anzahl der aufgesuchten Knoten bzw. Anzahl der benötigten Suchschritte oder Schlüsselvergleiche.

• sequentielle Suche

• direkte Suche

Mittlere Zugriffskosten z eines Baumes B erhält man durch Berechnung seiner gesamten Pfadlänge PL als Summe der Längen der Pfade von der Wurzel bis zu jedem Knoten Ki.

PL ( B )= Stufe (Ki) i = 1

n


Die mittlere Pfadlänge ergibt sich zu l = PL / n .

Maximale Zugriffskosten

Die längsten Suchpfade und damit die maximalen Zugriffskosten ergeben sich, wenn der binäre Suchbaum zu einer linearen Liste entartet.

Höhe: h = lmax + 1 = n


i = 0

(n + 1)

2n

( n + 1)

2

Minimale ( mittlere ) Zugriffskosten

Sie können in einer fast vollständigen oder ausgeglichenen Baumstruktur erwartet werden.

• Gesamtzahl der Knoten: 2 h-1 -1 < n 2 h -1

• Höhe h = [ log 2 n ] + 1

• Minimale mittlere Zugriffskosten: z min log 2 n - 1

n-1

Maximale mittlere Zugriffskosten:

zmax = 1/n * ( i + 1 ) * 1 = n * -------- = -------- = O (n)


Durchschnittliche ZugriffskostenExtremfälle der mittleren Zugriffskosten sind wenig aussagekräftig.

Differenz der mittleren zu den minimalen Zugriffskosten ist ein Maß für die Dringlichkeit von Balancierungen.

Bestimmung der mittleren Zugriffskosten

i

i - 1 Knoten

n - i Knoten

B l B r

zn

zn - izi-1


n verschiedene Schlüssel mit den Werten 1, 2, ..., n

seien in zufälliger Reihenfolge gegeben. Die Wahrscheinlichkeit, dass der erste Schlüssel den Wert i besitzt, ist 1/n.

(Annahme: gleiche Zugriffswahrscheinlichkeit auf alle Knoten)

Für den Baum mit i als Wurzel erhalten wir

zn ( i ) = 1/n * ( ( zi-1 + 1 ) * ( i - 1) + 1 + ( zn-1 + 1) * ( n - i ) )

Die Rekursions-Gleichung lässt sich in nicht-rekursiver, geschlossener Form mit Hilfe der harmonischen Funktion

Hn = n

i =1

1 i

darstellen.


Es ergibt sich:

zn = 2 * ----------* Hn - 3 = 2 ln ( n) - c .( n + 1 )n

--------- = --------------- --------------- = 2 ln ( 2 ) = 1.386...

Relative Mehrkosten:

z n

z min log 2 ( n ) - 1

2 ln ( n ) - c 2 ln ( n ) - c

log 2 ( n )

Der ausgeglichene binäre Suchbaum verursacht für alle Grundoperationen die geringsten Kosten.

Perfekte Balancierung zu jeder Zeit kommt jedoch sehr teuer.

Documents

Durchlaufen eines Binärbaumes