Assoziative Arrays

Datenstruktur-Dreieck für assoziative Arrays

Assoziative Arrays sind eine der wichtigsten Anwendungen für Suchalgorithmen und Suchbäume. Bevor wir dies im Detail erklären, wollen wir jedoch noch einmal einen Blick auf das Datenstruktur-Dreieck aus der ersten Vorlesung werfen, das am Beispiel der assoziativen Arrays sehr schön illustriert werden kann.

Assoziative Arrays werden genau wie gewöhnliche Arrays benutzt, sie unterstützen also den lesenden und schreibenden Zugriff über einen Index i

   X = a[i]
   a[i] = x

Im Unterschied zum gewöhnlichen Array, wo i ein Integer im Bereich <math> i \in 0 \ldots N-1</math> sein muss, kann der Typ von i jetzt beliebig sein. Eine typische Anwendung ist ein Wörterbuch

   x = toEnglish['Baum']   # ergibt 'tree'

In diesem Fall ist der Typ des Index string, was in der Praxis der häufigste Fall ist, weshalb assoziative Arrays oft als Dictionary bezeichnet werden (so auch in Python, hier heißt der Typ dict). Im allgemeinen kann aber jeder Typ als Index benutzt werden, für den entweder eine Ordnung oder eine Hashfunktion definiert ist. Im ersten Fall realisiert man das assoziative Array mit Hilfe eines Suchbaums, im zweiten Fall mit Hilfe einer Hashtabelle.

Realisierung des assoziativen Arrays als Suchbaum

Wenn für den Indextyp des assoziativen Arrays eine Ordnung definiert ist (wenn also i1 < i2 oder cmp(i1, i2) unterstützt werden), kann man das Indexierungsproblem auf das Suchproblem zurückführen, indem man die Indizes als Suchschlüssel verwendet. Im einfachsten Fall kann dies mit sequentieller Suche realisiert werden: Man verwendet ein gewöhnliches Array, dessen Einträge (Schlüssel, Daten)-Paare sind. Bei der Frage nach einem Schlüssel wird das betreffende Paar gesucht und die darin gespeicherten Daten zurückgegeben. Dies erfordert aber einen Suchaufwand in O(n). Effizienter geht es mit einem Suchbaum. Die Datenstruktur des Suchbaums muss dafür so erweitert werden, dass zu jedem Schlüssel (=Index) weitere Informationen gespeichert werden können (nämlich der Inhalt des indexierten Feldes). Man erweitert die Node-Klasse um ein Feld "data":

   class Node:
       def __init__(self, key, data = None):
           self.key = key
           self.data = data
           self.left = self.right = None

Dann kann man eine Klasse AssociativeArray realisieren, die die Indexoperationen intern mit Hilfe der Baumsuche implementiert. In Python wird der Zugriffsoperator [ ] für eine Datenstruktur (also innerhalb einer Klasse) wie folgt implementiert (vgl. die Python Docs zum Thema):

       def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: a[key] = value (schreibender Zugriff auf a[key]). Analog wird der lesende Zugriff value = a[key] wie folgt umgesetzt:

       def __getitem__(self, key, value)

Der Konstruktor der Klasse AssociativeArray initialisiert einen leeren Suchbaum:

   class AssociativeArray:
       def __init__(self):
           self.root = None
           self.size = 0

Die Funktion __setitem__ schaut nach, ob ein Eintrag mit dem betreffenden Index bereits existiert. Wenn ja, werden seine Daten mit den neuen Daten überschrieben, andernfalls wird ein neuer Eintrag angelegt. Intern werden dazu die bereits bekannten Funktionen treeSearch und treeInsert verwendet (siehe Abschnitt Suchbäume):

       def __setitem__(self, index, data):
            node = treeSearch(self.root, index)
            if node is None:
                self.root = treeInsert(self.root, index)
                self.size += 1
                node = treeSearch(self.root, index) 
            node.data = data

(Eine geschicktere Implementation würde natürlich die wiederholten Aufrufe von treeSearch und treeInsert eliminieren. Dies ändert aber nichts an der Komplexität der Funktion.) Die Funktion __getitem__ sucht ebenfalls einen Eintrag mit dem gegebenen Index. Wenn er gefunden wird, gibt sie die zugehörigen Daten zurück, andernfalls eine Fehlermeldung:

       def __getitem__(self, index):
           node = treeSearch(self.root, index)
           if node is None:
               raise KeyError(index)
           else:
               return node.data

Die Indexoperationen haben bei der Realisierung mit Baumsuche eine Komplexität in O(log n).

Ein wichtiges Beispiel für ein assoziatives Array, das auf diese Weise realisiert wurde, ist die C++ Standardklasse std::map.