• Increase font size
  • Default font size
  • Decrease font size

Baeume

E-Mail Drucken PDF
Baumstruktur Neben den Listen gibt es weitere dynamisch zu implementierende Datentypen. Eine der wichtigsten ist dabei der Baum. Der Baum verfügt über einen rekursiven Aufbau [Skizze]. Er kann entweder leer sein oder ein Knoten, welcher seinerseits mit Bäumen (Unterbäumen) rekursiv verknüpft ist. Die Liste kann somit auch als Baum aufgefasst werden, wobei hier die Knoten jeweils nur maximal einen Teilbaum besitzen (entarteter Baum).

Der oberste Knoten eines Baumes wird als Wurzel bezeichnet. Aufgrund des Aufbaus von oben nach unten, ist jeder Knoten der einen Vorgänger besitzt Nachfolger eines Knotens. Hat ein Knoten keinen Nachfolger bezeichnet man ihn als Blatt. Die Zahl der Kanten, die man erhält, wenn man in den Baum hinabsteigt, bezeichnet man als Weglänge. Die maximale Weglänge, gewissermaßen in die Tiefe des Baumes, ist seine Höhe.

Implementierung der Klasse Knoten

01   class BinNode :
02
03 def __init__(self, value) :
04 self.value = value
05 self.left = None
06 self.right = None
07
08 def get_value (self) :
09 return self.value
10


Die folgende Implementierung bezieht sich auf sogenannte Binärbäume, auf denen eine Ordnung definiert ist. Eine darauf basierende Einordnung in den Baum erfolgt ausgehend von einem Vergleich des Wertes des einzufügenden Elementes mit dem Knotenelement. Ist dieses Element kleiner, wandert das einzufügende Element in den linken Baum im anderen Fall in den rechten. Daraus ergibt sich folgende Implementierung in Python.


01   class Tree :
02
03 def __init__(self) :
04 self.tree = None
05
06 def insert (self, value) :
07 self.tree = self._insert (self.tree, value)
08
09 def _insert (self, tree, value) :
10 if tree is None : return BinNode (value)
11 elif tree.get_value () < value : tree.right = self._insert (tree.right, value)
12 else : tree.left = self._insert (tree.left , value)
13 return tree
14
15 if __name__=="__main__" :
16
17 # Testumgebung
18 pass


[ Source ]



AVL - Bäume haben die Eigenschaft, ausgeglichen zu sein. Dadurch werden Suchalgorithmen und Traversierungen wesentlich effizienter. Ein Einstieg in die Problematik läßt sich über funktionale Sprachen, wie zum Beispiel Haskell finden. Hier werden die notwendigen Operationen, welche die Ausgeglichenheit garantieren, deutlich. Der Ansatz zur Schaffung von AVL - Bäumen in Python ist ähnlich, da auch hier ein rekursives Vorgehen erforderlich ist.

Die eigentlichen Rotationen werden durch Zeigerperationen realisiert. Dargestellt wird im Folgenden die einfache Rechtsrotation. Die Eigenschaften und Schritte der Baumrotationen sind als Script noch einmal im Kontext des Heapsortalgorithmus nachzulesen.

01 def rechtsrot (self, tree):
02
03 links = tree.left
04 tmp = links.right
05 tree.left = tmp
06 tree.right = tree
07 return links

 

Da ein rekursiver Abstieg bis zu den Blättern erfolgt, ist erst beim Aufstieg ein Verwenden der entprechenden Rotationen sinnvoll. Die Logik entspricht dabei dem funktionalen Vorgehen. Ist die Differenz der Unterbäume 2 bzw. - 2, ist klar, in welchem der Teilbäume die Balance verletzt wurde. Es muss nun entschieden werden, ob der Baum im Unterbaum die Balance durch ein Wachsen nach innen oder außen verliert. Eine doppelte if - Abfrage leistet das Verlangte.

01   if self._height (tree.left) - self._height(tree.right) == 2:
02 if self._height (tree.left.right) - self._height (tree.left.left) == 1 :
03 tree = self.linksrechts (tree)
04 else :
05 tree = self.rechtsrot (tree)

[ Source ]


Weitere Methoden wie zum Beispiel delete sind sind vom Ansatz her ähnlich durchzuführen.
Aktualisiert ( Donnerstag, 26. November 2009 um 17:04 Uhr )  

(c) g-ymnasium.de 2006 - 2013 + Administrator