D a t e n s t r u k t u r    H e a p

HMO,   Warendorf,   Januar 1998




Aufgabe g)
Ein Binärbaum mit 50 Knoten ist in einem passendem Array gespeichert. Wenn i der Index eines Knotens im Array ist, geben Sie den Index von Vater und Söhnen an, falls diese existieren. i = 1, 12, 13, 24, 25, 30


Knoten: i   Vater: i DIV 2   linker Sohn: i*2   rechter Sohn: i*2+1  Blatt wenn 2*i > 50
        1          -                      2                   3                 nein
       12          6                     24                  25                 nein
       13          6                     26                  27                 nein
       24         12                     48                  49                 nein
       25         12                     50                   -                 nein
       30         15                      -                   -                 ja


Aufgabe h)
i)    Ist es möglich n-Bäume im Array darzustellen ?
ii)   Können auch nicht vollständige Bäume im Array dargestellt werden ?


i)   Ja das ist möglich. Wenn es sich um vollständige Bäume mit einem beliebigem, aber festem n handelt, dann brauchen die Formeln für Vater und Blatt nur entsprechend angepaßt werden.

ii)   Grundsätzlich ja, aber wenn die Bäume nicht mehr vollständig sind, dann funktioniert das einfache Modell der schichtweisen Speicherung nicht mehr direkt. Man müßte einen Mechanismus einfügen, um Leerstellen in den Schichten zu behandeln. Es sind aber noch andere Wege denkbar, die dann aber noch weiter von der schichtweisen Speicherung entfernt sind und hier nicht diskutiert werden sollen.


Aufgabe i)
Wägen Sie Vor- und Nachteile der Realisierung von Bäumen im Array gegenüber einer Realisierung mit Zeigern ab.


Schichtweise Speicherung im Array hat den Vorteil, daß jedes Element direkt im Zugriff ist, wenn man seinen Index kennt. Das führt bei bestimmten Prozessen zu Vorteilen. Für einen Heap ist das offensichtlich eine vorteilhafte Lösung. Man kann sowohl die Wurzel (bei Index 1) als auch das letzte Element direkt ansprechen.

Nachteil der schichtweise Speicherung im Array ist die fehlende Dynamik. Zur Kompilationszeit (in Pascal) muß bereits die Größe festgelegt werden und die kennt man meistens nicht exakt. So hat man entweder zu viel Platz reserviert oder aber das Programm scheitert, weil man zuwenig Platz vorgesehen hat.

Bei einer Speicherung in einem aus Zeigern aufgebautem Baum gewinnt man die Dynamik. Da jedes Element aber jetzt auch noch zwei Zeiger haben muß, kann es durchaus sein, daß man gar keinen Gewinn an Speicherplatz hat. Dennoch ist die Dynamik generell ein erheblicher Vorteil.

Die Algorithmen müßten neu entworfen werden, was vielleicht ein lästiger Nachteil ist, aber wohl kein entscheidender Nachteil. Der wichtige Algorithmus "sift" wird weiter O(log n) sein, weil hier die Höhe des Baumes entscheidend ist.




HTML-Texte: ADT Heap HAUPTTEXT

zur Informatik-Leitseite


© HMO, Neubearbeitung Januar 1998