Baeume

[Back]    [AVL Baeume]   
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 - Baeume]   [AVL - Baeume in Haskell]


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. 

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 : tree = self.linksrechts (tree)
03       else                                                                   : tree = self.rechtsrot (tree)
 
[ Source ]


Weitere Methoden wie zum Beispiel delete sind vom Ansatz her ähnlich durchzuführen.