Informatik 11 2.1 Von der Liste zum Baum

 Inhalt des Kurses    
0. Startseite   2.1 Von der Liste zum Baum
1. Die rekursive Datenstruktur Liste     2.2 Suchen in Binärbäumen
2. Die rekursive Datenstruktur Baum   2.3 Einfügen in Binärbäume
3. Die Datenstruktur Graph   2.4 Baum und Kompositum
4. Softwareentwicklung   2.5 Baumdurchlauf
5. Softwareprojekt  
     
   
     
Zurück zur Seite des Werner-von-Siemens-Gymnasiums Regensburg    
     
         

2. Die rekursive Datenstruktur Baum

2.1 Von der Liste zum Baum

liste_1

Abb 2.1_1

In einer sortierten Liste erscheint das Suchen eines bestimmten Elements sehr einfach:

Sucht man beispielsweise das Element 9, wird die Liste durchlaufen und man erhält das Element nach 6 Vergleichen.

Sucht man das Element 10, sind 7 Vergleiche notwendig. Da 11>10 gilt, kann 10 in der sortierten Liste nicht vorhanden sein.

Ist das gesuchte Element jedoch am Ende der Liste sind sehr viele Vergleichsoperationen notwendig, für das Element 30 benötigt man 15 Vergleiche. Bei großen Listen (z.B. ein Wörterbuch) hat eine solche Suche ein sehr schlechtes Zeitverhalten.

Die Laufzeit der Suche ist bei dieser Suche linear von n abhängig. Die durchschnittliche Anzahl von Vergleichen ist (n+1)/2.

Die Suche wird effizienter, wenn man die Liste in der Mitte teilt:

liste_2

Abb 2.1_2

Für das Element 30 benötigt man nur mehr 8 Vergleiche.

Übung
Berechne die durchschnittliche Vergleichsanzahl!

Setzt man die Halbierung der Liste konsequent weiter fort, gelangt man zu folgender Struktur:

liste_3

Abb 2.1_3

Und schließlich:

liste_4

Abb 2.1_4

Übung
Berechne erneut die durchschnittliche Vergleichsanzahl!

Auf diese Weise entsteht die Datenstruktur Baum.

Aus einer einfach verketteten Liste entsteht ein Baum, wenn die Objekte jeweils mehrere Nachfolger haben können und zusätzlich gilt:

  1. Genau ein Objekt wird nicht referenziert. Man nennt es Wurzel des Baumes

  2. Alle anderen Objekte werden genau einmal referenziert. Man nennt sie Knoten. Jeder Knoten lässt sich von der Wurzel auf genau einem Weg erreichen.

 

Gemäß dieser Definition sind also auch die Abbildungen 2.1_1 bis 2.1_3 Bäume.

Bei Abb 2.1_4 hat jeder Knoten höchstens zwei Nachfolger. Ein solcher Baum heißt Binärbaum.

Bei den Knoten unterscheidet man zwischen inneren Knoten (mit Nachfolger) und Blätter (kein Nachfolger).

Die Referenzen zwischen den Knoten nennt man Kanten.

Die Tiefe eines Knotens ist die Anzahl der Kanten, die beim Durchlauf von der Wurzel bis zum Knoten beschritten werden.

Alle Knoten mit der gleichen Tiefe beschreiben eine Ebene des Baumes .

Die Höhe des Baumes ist festgelegt durch die größtmögliche Tiefe.

Anstelle der Begriffe Nachfolger-Vorgänger liest man in der Literatur auch oft Kind-Eltern, Sohn-Vater, Tochter-Mutter o.ä.

Hinweis:
Die obigen Abbildungen sind Beispiele für geordnete Bäume. Selbstverständlich gibt es wie bei den Listen auch ungeordnete Bäume.

Klassendiagramm eines allgemeinen Baumes:

klassendia_baum_allg

Beispiel:

baum_allg

Klassendiagramm eines Binärbaumes

klassendia_binaer

Beispiele:

Ungeordneter Binärbaum:

bin_baum_ungeordnet

Geordneter Binärbaum :

bin_baum_geordnet
Übung

1.  Inwiefern ist ein Baum eine rekursive Datenstruktur?

2.  Beweise, dass ein Baum mit n Knoten genau n-1 Kanten hat.

3.  Starte im Internet das Baum-Visualisierungs-Tool

http://www.bvt.ct-labs.de/

Dort kann man geordnete Binärbäume erzeugen. Vollziehe an einigen Beispielen nach, wie der Baum aus einer geordneten Liste entstanden sein könnte. Beachte, dass die Listenteilung nicht immer in der Mitte erfolgen muss.
Bestimme auch die Tiefen der Knoten und die Baumhöhe.

4.  Erläutere die Strategie des Suchspiels auf der Seite:

http://www.matheprisma.de/Module/BinSuch/index.htm


Übung

Aufgaben aus dem Buch:

S.68 Nr.4

S.69 Nr.6


 

Hefteintrag