56. Bäume IV: Sortierte Bäume

Bäume können gut zum Speichern und Wiederfinden von Information verwendet werden. Beispiel Wörterbuch: Ist ein Wort im Wörterbuch oder nicht?

Technik: Baue einen Baum, so dass in jedem Knoten ein Wort steht. Unter jedem Knoten befinden sich “kleinere” Worter links, die anderen rechts.

Nach dem Lesen von “hier steh ich nun ich armer tor und bin so klug als wie zuvor”:

Problem: Sehr lange Äste brauchen lange zum Durchsuchen; Reorganisation des Baums würde zu viel flacherem Baum führen, da mehr Knoten zwei Kinder hätten.

Lösung: Ausgeglichene Bäume. Häufig verwendete Algorithmen: AVL-Bäume (immer optimal ausgeglichen, dafür komplizierte Rotationen), Rot-Schwarz-Bäume (Pfade können schlimmstenfalls um einen Faktor zwei verschieden lang sein, dafür konzeptionell einfacher; Ableitung über quartäre Bäume).

Zu diesen Themen werdet ihr in der Vorlesung Algorithmen und Datenstrukturen mehr hören.

Eine Implementation auf der Basis unserer Tree-Klasse:

class SortedTree(BinaryTree):
  """
  def insert(self, item):
    if self.getValue()>item:
      setMeth, getMeth = self.setLeft, self.getLeft
    elif self.getValue()==item:
      return
    else:
      setMeth, getMeth = self.setRight, self.getRight
    if not getMeth() is None:
      getMeth().insert(item)
    else:
      setMeth(SortedTree(item))

Lassen wirs laufen:

>>> import tree
>>> print tree.SortedTree("hier steh ich nun ich armer tor und bin"
...   " so klug als wie zuvor".split())
hier
        armer
                als
                bin
        steh
                ich
                        nun
                                klug
                                so
                tor
                        und
                                wie
                                        zuvor

Übungen zu diesem Abschnitt

Ihr solltet euch wenigstens an den rötlich unterlegten Aufgaben versuchen

(1)

Vollzieht anhand des tree.py-Moduls auf der Webseite alle Beispiele der letzten Seiten nach.

(2)

Schreibt eine Methode has node für den SortedTree, die nachsieht, ob ein Wort schon mal gesehen wurde.

(3)

SortedTree braucht eigentlich nicht mehr viel Arbeit, um als eine Art Ersatz-Dictionary arbeiten zu können, also Schlüssel-Wert-Paare zu speichern und einen (halbwegs) schnellen Zugriff darauf zu ermöglichen.

Weil unser SortedTree etwas zu schlicht ist, um sowas problemlos zu unterstützen, solltet ihr dabei direkt von BinaryTree ableiten. Lästigerweise ist das, was darin value heißt, in jetzt unser Schlüssel (key), und das, was wir jetzt Wert (value) nennen, gar nicht vorhanden.

Wir werden value intern nicht umbenennen wollen – definiert also zunächst im Konstruktor (der jetzt die Argumente key und value nehmen soll) einfach ein weiteres Attribut, meinetwegen nodeValue.

Danach solltet ihr insert(self, node) -> None und retrieve(self, key) -> val-Methoden schreiben, die ziemlich analog zu insert und has_node von SortedTree gestrickt sind, nur eben jeweils ein Argument mehr nehmen und ggf. alte nodeValues überschreiben. Beim retrieval sollten ein KeyError ausgelöst werden, wenn der angefragte Schlüssel nicht im Baum steht.

Um diese Funktionen klarer schreiben zu können, lohnt es sich wahrscheinlich, die alte getValue-Methode zu getKey umzutaufen (denkt scharf nach, in welchem Namespace das gut gehen könnte – wir haben eine solche Operation bisher noch nicht gemacht). Dazu sollte dann eine neue setValue-Methode kommen, während das neue getValue jetzt nodeValue zurückgeben sollte.

Als Sahnehäubchen könnt ihr dann noch Methoden __setitem__(self, key, val) -> None und __getitem__(self, key) -> val definieren. Python wird sie aufrufen, wenn ihr euer Objekt mit eckigen Klammern traktiert, also etwa so:

>>> t = tree.KeyValTree()
>>> t["l"] = "b"
>>> t["a"] = 1
>>> t["z"] = ['a', 'b', 'c']
>>> print t
None
        b
                ['a', 'b', 'c']
                1
>>> t["z"]
['a', 'b', 'c']
>>> t["gibtsnicht"]
Traceback (most recent call last):
<...irgendwas...>
KeyError: 'gibtsnicht'

(Zusatzaufgabe: Sorgt dafür, dass die Exception nicht einen kilometerlangen Traceback verursacht)

Antwort

Dateien zu diesem Abschnitt

tree.py -- Ein Modul mit unserem Baumcode – braucht noch etwas Arbeit

Zurück: Bäume III: Rechnen