[Python-de] binaerer Baum in Python

Gerhard Häring haering_python at gmx.de
Sat Oct 27 18:17:30 EDT 2001


On Sat, Oct 27, 2001 at 02:42:31PM +0200, Albert Hermeling wrote:
> > class Node:
> >     def __init__(self, data=None):
> >         self.data = data
> >         self.left = None
> >         self.right = None
> Gut bis dahin komme ich noch mit.

Trotzdem noch ein paar Bemerkungen.  Das Wichtigste, was man wissen
muss, ist dass Zuweisungen in Python immer nur neue Referenzen erzeugen.
Ebenso sind Funktions-/Methodenaufrufe immer "call-by-reference".
Wirkliche Kopien kann man, wenn man das mal braucht, mit dem copy-Modul
erzeugen.

Eine Node-Instanz hat eine Referenz auf einen linken und einen rechten
Nachfolger. Das Attribut "data" ist beliebig, muss aber das
"Komparator-Interface" (weiss nicht, wie das wirklich heisst)
implementieren, also eine __cmp__ Methode haben. Typen wie int und
String sind auch comparable.

(Hab gerade ausprobiert, Vergleiche mit ==, <, > funktionieren scheinbar
fast immer, aber wenn sie auch sinnvoll sein sollen, muss eine Klasse
eben doch __cmp__ implementieren; man könnte z. B. bei einer Klasse
Person das __cmp__ so implementieren, dass das Alter verglichen wird).

> >     def __repr__(self):
> >         return "{%s, %i, %i}" % (str(self.data), id(self.left),
> > id(self.right))
> 
> Mit dieser Methode weist Du der Variabel (z. B.) und den Zeigern ihre Werte 
> zu . Das ist mir auch noch klar.

Scheinbar nicht ;-) __repr__ dient dazu, das Objekt als String zu
repräsentieren und wird weiter unten von print aufgerufen.

> So was jetzt kommt verstehe ich nicht. Trotz meines großen Kopfes ;-(( 
> 
> > class BTree:
> >     def __init__(self):
> >         self.root = None
> Das ist soweit klar.
> >

Das folgende war eine quick-and-dirty Einfüge-Methode. Wenn es noch
keine Root-Node im BTree gibt, wird eine angelegt. Schwieriger wird der
else-Fall, wo die richtige Einfüge-Position gesucht werden muss.

Das Sortierkriterium ist, dass kleinere Nodes links, größere oder gleich
große Nodes rechts eingefügt werden.

Die Idee ist, dass ich mich im Baum so lange nach unten hangle, bis ich
einen leeren Platz gefunden habe. Dabei gehe ich nach links, wenn das
einzufügende Objekt kleiner als das Objekt an der aktuellen Node
(curnode.data) ist, nach rechts, wenn es größer ist. Ich merke mir auch,
in welche Richtung ich zuletzt abgezweigt bin (in direction). Ausserdem
merke ich mir, von wo ich die Abzweigung genommen habe (in lastnode).

Irgendwann habe ich einen leeren Platz gefunden, das merke ich, da
curnode == None ist. Ich erzeuge eine neue Node und hänge diese an der
Vorgänger-Node an. Und zwar links (lastnode.left), wenn ich zuletzt
links abgebogen bin oder rechts (lastnode.right), wenn ich zuletzt
rechts abgebogen bin.

> >     def add(self, data):
> >         if self.root == None:
> >             self.root = Node(data)
> >         else:
> >             curnode = self.root
> >             lastnode = self.root
> >             while curnode != None:
> >                 lastnode = curnode
> >                 if data < curnode.data:
> >                     curnode = curnode.left
> >                     direction = -1      # links einfügen
> >                 else:
> >                     curnode = curnode.right
> >                     direction = +1      # rechts einfügen
> >             if direction == -1:
> >                 lastnode.left = Node(data)
> >             else:
> >                 lastnode.right = Node(data)
> >

Das ist nur zur Darstellungs des BTree:

> >     def _prchilds(self, node):
> >         if node != None:
> >             return "(%s, %s %s)" % (self._prchilds(node.left), node,
> > self._prchilds(node.right)) else:
> >             return "nil"
> >
> >     def __repr__(self):
> >         return self._prchilds(self.root)

> Was ich nicht verstehe ist
> 
> 1. Was meinst Du mit curnode und lastnode?

s. o.

> 2.  Wo ist der Name des Referenzelementes gespeichert das auf den nächste 
> Knoten zeigt?

Die Knoten haben keine Namen. Die Attribute left und right sind einfach
Referenzen auf die nächsten Knoten.

> 3. musst Du den ganzen Baum durchsuchen um ein Element einzufügen oder zu 
> finden?

    o
 /     \
 o     o
 /\   /\
...  ...

Um ein Element einzufügen, muss ich so lange suchen, bis ich einen
leeren Platz gefunden habe. Die Suche erfolgt nach dem oben
beschriebenen Algorithmus. Ich muss also nicht den gesamnten Baum
durchsuchen, denn ich gehe immer nur von oben (Wurzel) nach unten, aber
nicht wieder zurück.

Zum Suchen muss ich auch von der Wurzel aus nach unten gehen, aber
niemals zurück.

Der Aufwand zum Einfügen und Suchen ist, wenn mich nicht alles täuscht,
logarithmisch.

Gerhard
-- 
mail:   gerhard <at> bigfoot <dot> de       registered Linux user #64239
web:    http://www.cs.fhm.edu/~ifw00065/    OpenPGP public key id 86AB43C0
public key fingerprint: DEC1 1D02 5743 1159 CD20  A4B6 7B22 6575 86AB 43C0
reduce(lambda x,y:x+y,map(lambda x:chr(ord(x)^42),tuple('zS^BED\nX_FOY\x0b')))



More information about the Python-de mailing list