Binäre Bäume

I.1.) Binäre Bäume

Binäre Bäume sind geordnete Bäume bei denen jeder Knoten maximal 2 Kinder hat und die Ordnung der Knoten mit links und rechts festgelegt ist. Die Ordnung der Knoten bezieht sich auf die Position der Knoten im Baum (d.h.: Knoten A links von Knoten B) und nicht auf die Werte der Knotenelemente.

I.1.1.) Möglichkeiten für einen binärer Baum hat:

A.) Binärer Baum mit zwei Kindern:

B.) Binärer Baum mit rechtem Kind(right child):

C.) Binärer Baum mit linkem Kind (left child):

D.) Binärer Baum ohne Kind (leaf):

I.1.2.)Eigenschaften:

A.) Häufigster Einsatz findet in Algorithmen statt. z.B.: Effiziente Manipulationsalgorithmen

B.) Zusammenhang zwichen der Anzahl der Elemente und er Höhe:

Höhe 0 Höhe 1 Höhe 2

1 Knoten 3 Knoten 7 Knoten

1 Blatt 2 Blätter 4 Blätter

Schlußfolgerung: In jeder neuen Ebene wird im optimalen Fall die Anzahl der Blätter verdoppelt.

C.) Entartung ist möglich:

z.B.: Jeder Knoten hat genau einen Nachfolger: entspricht verketteter Liste

I.2.) Formen binärer Bäume

I.2.1) Leerer binärer Baum

Ein leerer Baum ist ein Baum ohne Knoten.

I.2.2.) Voller binärer Baum (Full binary tree)

Jeder Knoten im Baum hat keine oder genau 2 Kinder. Mit anderen Worten, kein Kind besitzt nur 1 Kind.

I.2.3.) Perfekter binärer Baum (perfect binary tree)

Jeder Knoten im Baum hat keine oder genau 2 Kinder.Außerdem besitzen alle Blätter dieselbe Tiefe.

Eigenschaften:

Ein perfekter binärer Baum der Höhe h besitzt ((2 hoch (h+1)) -1) Knoten davon sind 2 hoch h Blätter.

I.2.4.) Kompletter binärer Baum

Ein kompletter binärer Baum ist ein perfekter binärer Baum mit der Ausnahme, dass die Blattebene nicht vollständig, dafür aber von links nach rechts, gefüllt ist.

Eigenschaften:

Ein kompletter binärer Baum mit n Knoten hat eine Höhe von maximal h = /log2 n)

I.2.5.) Höhen-balanzierter binärer Baum

Für jeden Knoten ist der Unterschied in der Höhe zwischen dem linken und dem rechten Kind maximal 1.

Diese Eigenschaft garantiert, dass lokal für jedes Kind die Balanzierungseigenschaft gut erfüllt ist, global aber die gesamten Baumdifferenzen größer sein können.

II.) Binäre Suchbäume

Für den binären Suchbaum gilt folgende Regel:

Für jeden Knoten gilt, dass alle Werte der Nachfolger im linken Unterbaum kleiner oder gleich dem Knotenwert sind und die Werte der Nachfolger im rechten Unterbaum größer als der Knotenwert sind.

II.1.) Eigenschaften binärer Suchbäume

A.)Sie dienen zur Verwaltung von beliebig großen Datenbeständen: dynamische Struktur.

B.) Zugriff auf Elemente in sortierter Reihenfolge durch inorder Traversierung.

C.) Aufwand proportional zur Höhe des Baumes und nicht zur Anzahl der Elemente.

II.2.) Operationen

Es gibt 5 Funktionen die jeder binäre Suchbaum enthält:

II.2.1.) Erstellen

Erzeugen eines leeren Suchbaumes.

II.2.2.) Einfügen

Einfügen eines Elementes in den Baum unter Berücksichtigung der Ordnungseigenschaft.

II.2.3.) Abfrage

Abfragen wo eingefügt werden soll

II.2.4.) Löschen

Entfernen eines Elementes aus dem Baum unter Erhaltung der Ordnungseigenschaft.

II.2.5.)Ausgabe

Ausgabe aller Elemente in sortierter Reihenfolge.

463 Worte in "deutsch"  als "hilfreich"  bewertet