Auflisten meines AVL führt zu Endlosschleife

[Mirodin]

Hallo Forengemeinde,

ich bin über Computercraft (falls das ein Begriff ist) und Lua zum Programmieren gekommen und habe sehr bald Blut geleckt

Aus diesem Grund wollte ich mich mal etwas anspruchvollerem zuwenden und habe einen simplen Binärbaum zusammengetippt. Soweit scheint auch alles zur funktionieren, jedoch wollte ich das ganze dann zu einem AVL ausweiten, was mir leider nicht so ganz gelingen will:

Die Ausgabe meines kleinen Testskripts stimmt in so fern, als die Höhen- und Balancewerte der einzelnen Knoten korrekt sind, jedoch scheine ich bei der Rotation irgendwo Mist gebaut zu haben, da es, wenn ich die Zeilen 107 und 119 wieder einfüge, zwar einen Baum kriege und er die Rotation auch triggert (Ausgabe: "links"), jedoch in einer Endlosschliefe hängen zu bleiben scheint (zumindest schließe ich dies aus 100% auf einem Kern und fehlender Terminierung des Skripts).

Ich hoffe, jemand kann mir sagen, was genau ich übersehen habe...

Vorweg schon mal Danke für eure Zeit
LG

Hier das BTree Skript (ich hoffe, die Kommentare sind nicht allzu störend, ich musste mir das selbst notieren, was ich da eigentlicht tue ):

Code: Alles auswählen

#!/usr/bin/python3

__all__ = ["BBaum", "BKnoten"]

#------------------------------------------------------------------------------
# B-Tree Klasse
#------------------------------------------------------------------------------
class BBaum:
    """
    Stellt eine B-Tree Instanz bereit. Fuer Informationen zu den Funktionen folgendes
    eingeben:
        baum.[Funktion].__doc__

    Methoden:
        __init__                        - Erstellt eine Instanz des B-Tree
        __del__                         - Loescht die Instanz
        auflisten                       - Listet alle Elemente im Baum auf
        einfuegen                       - Fuegt einen Knoten hinzu
        get_groessten                   - Gibt den groessten Unterknoten zurueck
        get_kleinsten                   - Gibt den kleinste Unterknoten zurueck
        get_root                        - Gibt den Wurzelknoten zurueck
        ist_leer                        - Gibt an, ob der Baum Knoten enthaelt
        loeschen                        - Loescht einen Knoten
        suchen                          - Durchsucht den Baum
    """

    __all__ = ["__del__", "__init__", "einfuegen", "get_groessten",
               "get_kleinsten", "get_root", "ist_leer", "loeschen", "suchen"]
    __name__ = "BBaum"

    #--------------------------------------------------------------------------
    # init
    #--------------------------------------------------------------------------
    def __init__(self, wurzel, pointer = None):
        """
        Verwendung:
                baum = BBaum(wurzel)
            wurzel ist der Wurzelschluessel des Baumes
        """
        self.__root = BKnoten(wurzel, pointer = pointer)

    #--------------------------------------------------------------------------
    # del
    #--------------------------------------------------------------------------
    def __del__(self):
        """
        Verwendung:
           baum.__del__()
        """
        while self.__root.Rechts or self.__root.Links:
            if self.__root.Links:
                self.loeschen(self.__root.Links)
            else:
                self.loeschen(self.__root.Rechts)
        del self.__root

    #--------------------------------------------------------------------------
    # auflisten
    #--------------------------------------------------------------------------
    def auflisten(self):
        """
        Gibt alle Knotenschluessel und die zugehoerigen Pointer im Baum ausgehen
        Verwendung:
            a = baum.auflisten()
        """
        liste = []
        self.__auflisten_recur(self.__root, liste)
        return liste

    #--------------------------------------------------------------------------
    # __auflisten_recur
    #--------------------------------------------------------------------------
    def __auflisten_recur(self, ober, liste):
        if ober.Links:
            self.__auflisten_recur(ober.Links, liste)
        liste.append({ober.Key:{"H":ober.Hoehe, "Bal":ober.Balance}})
        if ober.Rechts:
            self.__auflisten_recur(ober.Rechts, liste)

    #--------------------------------------------------------------------------
    # einfuegen
    #--------------------------------------------------------------------------
    def einfuegen(self, key, pointer):
        """
         Verwendung:
            baum.einfuegen(key, pointer)
        key ist der Schluessel, unter dem der Eintrag abgelegt werden soll, pointer
        enthaelt den Verweis auf die Tabelle.
        """
        if self.__root.Key:
            self.__einfuegen_recur(self.__root, key, pointer)
        else:
            self.__root.Key = key
            self.__root.Pointer = pointer

    #--------------------------------------------------------------------------
    # __einfuegen_recur
    #--------------------------------------------------------------------------
    def __einfuegen_recur(self, ober, key, pointer):
        if key > ober.Key:
            if not ober.Rechts:
                ober.Rechts = BKnoten(key, ober, pointer)
            else:
                self.__einfuegen_recur(ober.Rechts, key, pointer)
                ober.hoehe_errechnen()
                #ober.balance_errechnen()
                if ober.Balance == -2:
                    if ober.Rechts.Balance == -1:
                        print("rechts")
        # hier muss unterschieden werden, damit bereits vorhandene Schluessel
        # nicht erneut eingefuegt werden.
        elif key < ober.Key:
            if not ober.Links:
                ober.Links = BKnoten(key, ober, pointer)
            else:
                self.__einfuegen_recur(ober.Links, key, pointer)
                ober.hoehe_errechnen()
                #ober.balance_errechnen()
                if ober.Balance == 2:
                    if ober.Links.Balance == 1:
                        print("links")
                        tmp = ober.Links
                        ober.Links = tmp.Rechts
                        tmp.Rechts = ober
                        ober = tmp
        ober.hoehe_errechnen()
        ober.balance_errechnen()

    #--------------------------------------------------------------------------
    # get_groessten
    #--------------------------------------------------------------------------
    def get_groessten(self, ober):
        """
        Verwendung:
            baum.get_groessten(ober)
        Gibt den groessten Unterknoten ausgehend von ober zurueck
        """
        while ober.Rechts:
            ober = ober.Rechts
        return ober

    #--------------------------------------------------------------------------
    # get_kleinsten
    #--------------------------------------------------------------------------
    def get_kleinsten(self, ober):
        """
        Verwendung:
            baum.get_kleinsten(ober)
        Gibt den kleinsten Unterknoten ausgehend von ober zurueck
        """
        while ober.Links:
            ober = ober.Links
        return ober

    #--------------------------------------------------------------------------
    # get_leer
    #--------------------------------------------------------------------------
    def get_leer(self):
        """
        Prueft, ob der Baum leer ist und gibt das Ergebnis in die Variable
        Leer aus.
        Verwendung:
            baum.Leer
            False
        """
        if self.__root.Key:
            return False
        else:
            return True

    Leer = property(get_leer)

    #--------------------------------------------------------------------------
    # get_root
    #--------------------------------------------------------------------------
    def get_root(self):
        """
        Gibt den Wurzelknoten in der Variable Root aus.
        Verwendung:
            baum.Root
            <BTree.BKnoten object at xyz>
        """
        return self.__root

    Root = property(get_root)

    #--------------------------------------------------------------------------
    # loeschen
    #--------------------------------------------------------------------------
    def loeschen(self, knoten):
        """
        Verwendung:
            baum.loeschen(knoten)
        knoten muss ein Knoten-Objekt des Baumes sein.
        """
        if knoten.Rechts == None and knoten.Links == None:
            self.__loesche_blatt(knoten)
        elif knoten.Rechts == None or knoten.Links == None:
            self.__loesche_einzeln(knoten)
        else:
            # ersetzt den Knoten durch den niedrigsten Unterknoten ausgehend
            # vom rechten Knoten, da der kleinste rechte Wert grosser, als der
            # groesste linke Wert ist
            minRechts = self.get_kleinsten(knoten.Rechts)
            knoten.Key = minRechts.Key
            knoten.Pointer = minRechts.Pointer
            self.loeschen(minRechts)

    #--------------------------------------------------------------------------
    # __loesche_blatt
    #--------------------------------------------------------------------------
    def __loesche_blatt(self, knoten):
        if knoten is self.__root:
            self.__root.Key = None
            self.__root.Pointer = None
        else:
            if knoten.Eltern.Rechts is knoten:
                knoten.Eltern.Rechts = None
            else:
                knoten.Eltern.Links = None
            del knoten

    #--------------------------------------------------------------------------
    # __loesche_einzeln
    #--------------------------------------------------------------------------
    def __loesche_einzeln(self, knoten):
        kind = None
        if knoten.Links:
            kind = knoten.Links
        else:
            kind = knoten.Rechts

        # loescht die Wurzel und ersetzt sie durch einen Unterknoten
        if knoten is self.__root:
            self.__root = kind
            kind.Eltern = None
            del knoten
        else:
            # schneidet den Knoten aus und verlinkt den ehemaligen
            # Unterknoten mit dem ehemaligen Elternknoten
            eltern = knoten.Eltern
            if knoten is eltern.Links:
                eltern.Links = kind
            else:
                eltern.Rechts = kind
            kind.Eltern = eltern
            del knoten

    #--------------------------------------------------------------------------
    # suchen
    #--------------------------------------------------------------------------
    def suchen(self, key):
        """
        Verwendung:
            baum.suchen(key)
        key ist der Schluessel, nach dem gesucht werden soll. Bei Erfolg wird der
        Knoten zurueck gegeben, andernfalls None.
        """
        ober = self.__root
        while True:
            if key > ober.Key:
                if ober.Rechts:
                    ober = ober.Rechts
                else:
                    return None
            elif key < ober.Key:
                if ober.Links:
                    ober = ober.Links
                else:
                    return None
            else:
                return ober

#------------------------------------------------------------------------------
# B-Knoten Klasse
#------------------------------------------------------------------------------
class BKnoten:
    """
    Klasse der B-Tree Knoten.

    Methoden:
        __init__                        - Erstellt einen neuen Knoten
        __del__                         - Loescht einen Knoten
        get_bal                         - Gibt die Balance am Knoten zurueck
        set_bal                         - Setzt die Balance am Knoten
        get_eltern                      - Gibt den Elternknoten zurueck
        set_eltern                      - Setzt den Elternknoten
        get_key                         - Gibt den Schluessel des Knotens aus
        set_key                         - Setzt den Schluessel des Knotens
        get_links                       - Gibt den kleineren Wert zurueck
        set_links                       - Setzt den kleineren Wert
        get_pointer                     - Gibt den Pointer zurueck
        set_pointer                     - Setzt den Pointer
        get_rechts                      - Gibt den groesseren Wert zurueck
        set_rechts                      - Setzt den groesseren Wert
    """

    __all__ = ["__del__", "__init__", "get_eltern", "get_key", "get_links",
               "get_pointer", "get_rechts", "set_eltern", "set_key",
               "set_links", "set_pointer", "set_rechts"]
    __name__ = "BKnoten"

    #--------------------------------------------------------------------------
    # init
    #--------------------------------------------------------------------------
    def __init__(self, key, eltern = None, pointer = None):
        self.__balance = 0
        self.__eltern = eltern
        self.__hoehe = 1
        self.__key = key
        self.__links = None
        self.__pointer = pointer
        self.__rechts = None

    #--------------------------------------------------------------------------
    # del
    #--------------------------------------------------------------------------
    def __del__(self):
        del self.__balance
        del self.__eltern
        del self.__hoehe
        del self.__key
        del self.__links
        del self.__pointer
        del self.__rechts

    #--------------------------------------------------------------------------
    # balance_errechnen
    #--------------------------------------------------------------------------
    def balance_errechnen(self):
        """
        Gibt die aktuelle Balance des Baumes am Knoten zurueck
        Verwendung:
            knoten.balance_errechnen()
        """
        if self.Links:
            if self.Rechts:
                self.Balance = self.Links.Hoehe - self.Rechts.Hoehe
            else:
                self.Balance = self.Links.Hoehe
        else:
            if self.Rechts:
                self.Balance = -self.Rechts.Hoehe
            else:
                self.Balance = 0

    #--------------------------------------------------------------------------
    # hoehe_errechnen
    #--------------------------------------------------------------------------
    def hoehe_errechnen(self):
        """
        Errechnet die aktuelle Hoehe des Kontens im Baum und speichert diese
        in der Variable Hoehe
        Verwendung:
            knoten.hoehe_errechnen()
        """
        if not self.Links:
            if not self.Rechts:
                self.Hoehe = 1
            else:
                self.Hoehe = 1 + self.Rechts.Hoehe
        else:
            if not self.Rechts:
                self.Hoehe = 1 + self.Links.Hoehe
            else:
                self.Hoehe = max(self.Links.Hoehe, self.Rechts.Hoehe) + 1

    #--------------------------------------------------------------------------
    # get_balance
    #--------------------------------------------------------------------------
    def get_bal(self):
        return self.__balance

    #--------------------------------------------------------------------------
    # get_eltern
    #--------------------------------------------------------------------------
    def get_eltern(self):
        return self.__eltern

    #--------------------------------------------------------------------------
    # get_hoehe
    #--------------------------------------------------------------------------
    def get_hoehe(self):
        return self.__hoehe

    #--------------------------------------------------------------------------
    # get_key
    #--------------------------------------------------------------------------
    def get_key(self):
        return self.__key

    #--------------------------------------------------------------------------
    # get_links
    #--------------------------------------------------------------------------
    def get_links(self):
        return self.__links

    #--------------------------------------------------------------------------
    # get_pointer
    #--------------------------------------------------------------------------
    def get_pointer(self):
        return self.__pointer

    #--------------------------------------------------------------------------
    # get_rechts
    #--------------------------------------------------------------------------
    def get_rechts(self):
        return self.__rechts

    #--------------------------------------------------------------------------
    # set_balance
    #--------------------------------------------------------------------------
    def set_bal(self, bal):
        self.__balance = bal

    #--------------------------------------------------------------------------
    # set_eltern
    #--------------------------------------------------------------------------
    def set_eltern(self, eltern):
        self.__eltern = eltern

    #--------------------------------------------------------------------------
    # set_hoehe
    #--------------------------------------------------------------------------
    def set_hoehe(self, hoehe):
        self.__hoehe = hoehe

    #--------------------------------------------------------------------------
    # set_key
    #--------------------------------------------------------------------------
    def set_key(self, key):
        self.__key = key

    #--------------------------------------------------------------------------
    # set_links
    #--------------------------------------------------------------------------
    def set_links(self, links):
        self.__links = links

    #--------------------------------------------------------------------------
    # set_pointer
    #--------------------------------------------------------------------------
    def set_pointer(self, pointer):
        self.__pointer = pointer

    #--------------------------------------------------------------------------
    # set_rechts
    #--------------------------------------------------------------------------
    def set_rechts(self, rechts):
        self.__rechts = rechts

    #--------------------------------------------------------------------------
    # Propertys
    #--------------------------------------------------------------------------
    Balance = property(get_bal, set_bal)
    Eltern = property(get_eltern, set_eltern)
    Hoehe = property(get_hoehe, set_hoehe)
    Key = property(get_key, set_key)
    Links = property(get_links, set_links)
    Pointer = property(get_pointer, set_pointer)
    Rechts = property(get_rechts, set_rechts)

Und noch das Testskript:

Code: Alles auswählen

#!/usr/bin/python3

import BTree

tree = BTree.BBaum(10, "Root")
liste = [5, 12, 2, 8, 11, 13, 1, 4, 7, 9, 3]

for a in liste:
    tree.einfuegen(a, "k")
for e in tree.auflisten():
    print(e)

[BlackJack]

@Mirodin: Ein paar Anmerkungen zum Quelltext:

Für die Hilfe sollte man ``help(baum.methodenname)`` eingeben und nicht direkt auf das `__doc__`-Attribut zugreifen. Auf die „magischen” Attribute mit den beiden führenden und folgenden Unterstrichen sollte man nur direkt zugreifen wenn es keine andere Möglichkeit gibt.

Die Methoden in der Dokumentation der Klasse alle aufzuführen ist redundant. Die `help()`-Funktion listet wenn man sie auf Klassen anwendet automatisch alle Dokumentierten Methoden auf.

`__all__` und `__name__` als Attribute auf Klassen zu setzen macht keinen Sinn. `__all__` ist grundsätzlich einfach sinnfrei und `__name__` wird schon von der Sprache auf den Namen der Klasse gesetzt.

Kommentare die vor jede Klassen und Methodendefinition noch einmal den Namen setzen der gleich darauf definiert wird, sind unsinnig. Kommentare sollten dem Leser einen Mehrwert bieten. Also Informationen die nicht direkt aus dem Quelltext ersichtlich sind. Wer Klassen- und Methodennamen nicht aus der definierenden Zeile ablesen kann, dem ist auch durch solche Kommentare nicht mehr zu helfen.

Bei den Methodendokumentationen sind die *Verwendung:*-Teile auch durch die Bank unnötig weil sowas von trivial und offensichtlich. Da steht doch eigentlich immer nur noch mal die Methodensignatur die ein paar Zeilen weiter oben schon zu sehen ist.

Die Mischung zwischen Deutsch und Englisch bei den Bezeichnern ist unschön. Insbesondere wenn in *einem* Bezeichner *beide* Sprachen verwendet werden.

Die doppelten führenden Unterstriche sollten jeweils nur einer sein. Doppelte bedeuten nicht „private” — man kann trotzdem noch problemlos von aussen an diese Attribute heran kommen. Ein einfacher führender Unterstrich sagt per Konvention das man das Attribut nicht von aussen verwenden sollte, solange man nicht genau weiss was man da tut. Die doppelten führenden Unterstriche dienen dazu Namenskollisionen bei tiefen Vererbungshierarchien und bei Mehrfachvererbung zu verhindern. Zwei Sachen die man in Python sehr selten bis gar nicht macht. Weshalb doppelte Unterstriche fast nie nötig sind.

`__del__()` sollte man grundsätzlich nicht implementieren. Es gibt keine Garantien wann oder ob diese Methode überhaupt aufgerufen wird, man muss verdammt aufpassen was man in der Methode verwendet, weil im Grunde alles ausserhalb des Exemplars auf dem die Methode aufgerufen wird, schon vorher von der Speicherbereinigung beseitigt worden sein könnte. Und die blosse Existenz der Methode kann unter Umständen dazu führen dass ein Speicherleck entsteht, weil das Objekt niemals freigegeben werden kann (und deshalb die Methode auch nicht aufgerufen wird). Der einzige sinnvolle Einsatzzweck ist das Freigeben von externen Ressourcen von denen die Speicherverwaltung von Python keine Ahnung hat. Und selbst da muss man auf all die Fallstricke achten, die diese Methode mit sich bringt.

Beim Baum ist die Methode auch völlig unssinnig. Da wird irre viel Arbeit verrichtet jeden einzelnen Knoten aus der Baumstruktur zu entfernen und den Baum wieder auszubalancieren, obwohl der Baum zu dem Zeitpunkt ja sowieso *komplett* freigegeben werden soll, es also total unsinnig ist jeden ”Zwischenschritt” balanciert zu halten. Der Baum ist im Programm zu dem Zeitpunkt nicht mehr erreichbar, darum ist es auch völlig Wurst ob dessen Invariante noch stimmt oder nicht. Das entfernen eines Attributs am Ende der Methode ist aus dem selben Grund völlig sinnfrei. Und daraus folgt, dass auch die `__del__()` vom Knoten gefährlicher Unsinn ist.

`pointer` ist ein unpassender Name weil es in Python keine Zeiger als Datentyp gibt, in dem Sinne wie das wohl gemeint ist.

Die Namen halten sich nicht alle an die Namenskonventionen aus dem Style Guide for Python Code. Attribute werden dort als `kleinbuchstaben_mit_unterstrichen` geschrieben.

Bei `__einfuegen_recur()` wird bei einem bereits vorhandenen Schlüssel gar nichts gemacht, wo man eigentlich erwarten würde, das der Wert zum Schlüssel ausgetauscht wird. In dem Zusammenhang würde es sich auch anbieten bei den Bäumen eine `__len__()`-Methode und den Indexoperator anzubieten, so dass man sie als Wörterbuch verwenden kann. Dann kann man auch gleich noch andere Methoden dieses „duck types” anbieten.

In der Methode sind an zwei Stellen verschachtelte ``if``\s die man durch Verknüpfung der Bedingungen jeweils zu einem ``if`` zusammenfassen kann.

Das Suffix `_errechnen` bei `hoehe_errechnen()` und `balance_errechnen()` sagt nicht deutlich genug dass da nichts berechnet und zurückgegeben wird, sondern das die beiden Methoden die Daten in der Baumstruktur manipulieren und nichts zurückgegeben. `_aktualisieren` wäre da eine gebräuchlichere Bezeichnung.

Für Properties verwendet man spätestens seit Python 2.7 besser die Dekoratorsyntax.

`get_leer()` ist Fehlerhaft. Die Zahl 0, None, False, und leere Containertypen sind als Wahrheitswert betrachtet „falsch”. Wenn man also so ein Schlüssel verwendet und der zufällig im Wurzelknoten gespeichert ist, dann behauptet die Methode der Baum sei leer, obwohl da beliebig viele Knoten drin gespeichert sein könnten. An der Stelle ist auch ungünstig das `None` als Markierung für leere Knoten missbraucht werden und man `None` damit nicht mehr als normale Werte verwenden kann. Ich würde ja nicht die Attribute `Key` und `Pointer` für so etwas missbrauchen sondern den Knoten-Wert selber auf `None` setzen.

Bei den `*loesche*()`-Methoden sind ein paar ``del``-Anweisungen die vollkommen sinnfrei sind. Du hast anscheinend den Effekt von ``del`` auf Namen und Attribute nicht verstanden. Damit wird der Name oder das Attribut gelöscht, nicht der Wert der dahinter steht. Man kann in Python nicht explizit selber Objekte löschen. Da kümmert sich die Speicherverwaltung schon selber drum. Einen lokalen Namen explizit mit ``del`` zu löschen macht absolut keinen Sinn, denn der verschwindet nach Ablauf der Methode sowieso. Damit ist nichts gewonnen und man hat eine zusätzliche, überflüssige Anweisung im Programm.

Die ganzen trivialen Getter und Setter beim Knoten sind überflüssig. Wenn man ein Attribut hat, und dafür jeweils einen Getter und einen Setter, und dazu dann auch noch ein Property macht, hätte man auch einfach *direkt* auf das Attribut zugreifen können, ohne diesen ganzen Boilerplate-Zauber.

[Mirodin]

Wow, DAS nenne ich mal eine ausführliche Antwort!
Vielen Dank BlackJack für die hilfreichen Tipps.

Da ich die Variable '__all__' in einigen Modulen gesehen hatte, dachte ich, dies wäre die übliche Verwendung

Zu deiner Anmerkung mit den Pointern (bzw. jetzt Ziel): Ich möchte den BTree als Indizierungswerkzeug für eine Pseudo-Datenbank verwenden und würde unter dieser Variable gerne ein Dictionary speichern, welches einen Verweie auf die Datein enthält, die den gesuchten Wert beinhalten. In diesen Datein wären dann wiederum JSON-Objekte ähnlich wie in MongoDB oder CouchDB gespeichert, aber das ist noch Zukunftsmusik.

Deiner Aussage bezüglich '__einfuegen_recur()' kann ich leider nicht so ganz folgen, würdest du mir das bitte nochmal erklären, was du damit meinst?
Ich haben den Code jetzt mal auf Pastebin gepackt, da ich meinen ersten Beitrag leider nicht mehr editieren kann und nicht jedes mal den Thread mit x Zeilen vollpacken will.

Code: http://pastebin.com/QWfEFRR4

Nochmals Danke und LG

[BlackJack]

@Mirodin: Es gibt `__all__` auf Modulebene. Da kann man alle Namen von Modulebene auflisten die zur öffentlichen API des Moduls gehören sollen. Das hat dann zum Beispiel Einfluss darauf was bei ``from modulname import *`` aus so einem Modul in den Namensraum des importierenden Moduls übernommen wird. Da würde in Deinem Fall dann aber `BKnoten` nicht dazugehören, denn das ist ein Implementierungsdetail und keine öffentliche API. Die Benutzer sollen ja auf dem Baum operieren und nicht selber `BKnoten`-Objekte erstellen.

Dann ist mir noch aufgefallen das Du einen AVL-Baum vielleicht auch so nennen solltest. B-Tree ist etwas anderes, das ist kein Binärbaum mehr.

Gibt es einen Grund warum Du das Rad selbst erfindest? Es gibt zum Beispiel bintrees. Dort sind einfache Binärbäume, AVL-Bäume, und Rot-Schwarzbäume enthalten, jeweils als reine Python-Implementierung und noch mal in C geschrieben und mit Cython angebunden.

Beim Einfügen hatte ich ja zwei Anmerkungen gemacht. Das eine war, dass bei ``tree(schluessel, ziel)`` das `ziel` einfach still ignoriert wird wenn es den `schluessel` schon im Baum gibt. Das finde Ich unerwartet, weil man hier eigentlich erwarten würde, dass bei einem bereits vorhandenen Schlüssel der alte Wert durch den neuen ersetzt wird. Also wenn ich ein Wörterbuch ``mapping = {'answer': 23}`` habe, dann würde ich nach einem ``mapping['answer'] = 42`` erwarten, dass die 23 durch die 42 ausgetauscht wird, und nicht das diese Operation gar keinen Effekt hat.

Und die zweite Anmerkung war, dass sich so ein Baum wie ein Abbildungstyp, also zum Beispiel wie `dict` verhalten sollte, so dass Dein Testquelltext von oben so aussehen kann:

Code: Alles auswählen

#!/usr/bin/env python3
from AVLTree import AVLTree


def main(): 
    tree = AVLTree(10, 'Root')
    keys = [5, 12, 2, 8, 11, 13, 1, 4, 7, 9, 3]
     
    for key in keys:
        tree[key] = 'k'
    # 
    # oder:
    # 
    tree.update((key, 'k') for key in keys)

    for key, value in tree.items():
        print(key, '->', value)


if __name__ == '__main__':
    main()

Die `bintree`-Datentypen bieten eine solche API an. Und es bietet sich irgendwie auch an so eine API anzubieten.

[Mirodin]

Gibt es einen Grund warum Du das Rad selbst erfindest?

Der Grund ist, dass ich Dinge meist besser verstehe, wenn ich sie selbst mal in ähnlicher Weise ausprobiert habe und nicht einfach nur anwende^^
Nenn mich verrückt, aber ich will ja nichts "produzieren" in dem Sinne, dass ich es veröffentlichen möchte, sondern es geht mir vornehmlich darum, zu verstehen, wie ein AVL (oder auch etwas anderes) funktioniert.

Beim Einfügen hatte ich ja zwei Anmerkungen gemacht. Das eine war, dass bei ``tree(schluessel, ziel)`` das `ziel` einfach still ignoriert wird wenn es den `schluessel` schon im Baum gibt. Das finde Ich unerwartet, weil man hier eigentlich erwarten würde, dass bei einem bereits vorhandenen Schlüssel der alte Wert durch den neuen ersetzt wird. Also wenn ich ein Wörterbuch ``mapping = {'answer': 23}`` habe, dann würde ich nach einem ``mapping['answer'] = 42`` erwarten, dass die 23 durch die 42 ausgetauscht wird, und nicht das diese Operation gar keinen Effekt hat.

Ja, da hast du Recht, das habe ich noch nicht bedacht.

Und die zweite Anmerkung war, dass sich so ein Baum wie ein Abbildungstyp, also zum Beispiel wie `dict` verhalten sollte [...]

Ich glaube, ich verstehe, was du meinst, aber ich will ja den Baum idR nicht in einer for-Schleife ausgeben, sondern einen Wert x übergeben, und dann den "Zeiger" auf die Zieldatei zurück bekommen.

Ich hoffe, du kannst meinen Erläuterungen folgen, auch wenn mein Vorgehen sicher nicht ökonomisch ist (ist ja auch nicht der Zweck ).

LG

[BlackJack]

@Mirodin: Natürlich willst Du zum Schlüssel `x` den Wert bekommen. Genau das macht doch so ein Typ, wie zum Beispiel ein Wörterbuch. Ich habe doch nur *Dein* Beispielprogramm umgeschrieben und *da* hattest Du *selbst* diese Schleife. Natürlich sollte der Baum nicht nur die dort gezeigten Operationen unterstützen, sondern auch Schlüsselzugriff, so dass ein ``print(tree[10])`` die Zeichenkette 'Root' ausgibt. Und den ``in``-Operator. Und `len()`. Also alles was die Bäume aus `bintree` schon bieten.

Wobei sich auch die Frage stellt was Du von diesem Baum eigentlich erwartest was ein `dict` nicht erfüllt. Denn das dürfte effizienter sein als ein balancierter Baum wenn man nicht irgendwo auch den Umstand verwendet, dass der Baum zusätzlich zur Abbildung Schlüssel → Wert eine Ordnung der Schlüssel hat. Und da wären wir dann wieder bei einer Schleife über die Elemente im Baum, denn das ist ja die Operation die am naheliegendsten diese Ordnung nutzt.

[Mirodin]

Hallo BlackJack,

ich fürchte, wir schreiben aneinander vorbei
Ich will den AVL nicht als Ersatz für ein Dictionary (dass ich das sicher nicht besser mache, als Leute, die wirklich Ahnung davon haben, ist mir klar), sondern ich möchte verstehen, wie genau so ein AVL funktioniert und wie man das bewerkstelligt. Leider bekomme ich das mit der Rotation nicht so ganz hin, weshalb ich mich hier gemeldet habe. Im Grunde erwarte ich von meinem AVL also nichts weiter, als dass er funktioniert und mir das gute Gefühl bringt, es geschafft zu haben

aktualisierter Code: http://pastebin.com/QWfEFRR4
Die Ausgabe meines Tesskripts endet immerhin nicht mehr in einer Endlosschleife, aber aus irgendeinem Grund bekomme ich es nicht hin, dass der Teilbaum, der zuvor an der '5' hing ausgegeben wird.

[BlackJack]

@Mirodin: Da Du beschrieben hast was als `ziel` später mal verwendet werden soll, klang das schon ziemlich stark danach als sollte der Baum in einem Programm eingesetzt werden. Und zwar nach der Beschreibung als Abbildung von Schlüssel auf dazugehörige Werte. Also als einen „mapping type” wie das auch `dict` ist.

Bei der Effizienz ging es mir nicht darum ob das jemand mit Ahnung umsetzt oder nicht, sondern ganz grundsätzlich haben `dict`\s ein anderes Laufzeitverhalten bei den verschiedenen (vergleichbaren) Operationen als Bäume im allgemeinen und AVL-Bäume im besonderen. Die Grundoperationen Einfügen, Suchen, und Löschen sind bei `dict` in der Regel bei O(1) während sie beim AVL-Baum bei O(log n) liegen. Das ist der Preis den man für die zusätzliche Eigenschaft der Ordnung auf den Elementen bezahlt. Und da war halt meine Argumentation das man diese zusätzliche Eigenschaft auch verwenden sollte wenn man da schon den Preis in Form von zusätzlicher Laufzeit für bezahlt.

[Mirodin]

Ok, jetzt verstehe ich, weshalb du mir immer Alternativen aufzeigen wolltest
Das mit dem Index war nur eine Idee, die ich mir so zusammen gesponnen habe, aber da Dictionarys anscheinend deutlich schneller sind (mit den O-Notationen hatte ich es noch nie so ), ist das ja wieder vom Tisch.

Bleibt leider immer noch das Problem mit der Rotaion, die nicht so will, wie ich. Kannst du mir da vielleicht weiter helfen?
Danke dir nochmal für die Erklärungen (und die vielen Hinweise am Anfang)

LG

[BlackJack]

@Mirodin: Nach welcher Anleitung/Beschreibung bist Du denn vorgegangen? Soweit ich das sehe fehlt da noch einiges. Du rotierst ja nur an einer Stelle. Und das dann auch nur einmal an der Stelle wenn ich das richtig sehe. Eigentlich ist es ja so, dass man einen ganz normalen Binärbaum hat, und dort auch ganz normal einfügt, und dann Richtung Wurzel prüfen muss, ob rotiert werden muss. Also nicht nur dort wo man eingefügt hat, sondern wenn man rotieren musste auch den Elternknoten ob man dort auch rotieren muss, und so weiter. Das sehe ich im Code nicht.

[Mirodin]

Also den ersten BTree habe ich nach diesem Beispiel gebastelt (von dort habe ich auch die ganzen Getter und Setter): http://board.raidrush.ws/showthread.php?t=688494
Die Sache mit der Rotation habe ich dann hier zum Teil abgeschaut: http://www.cse.ohio-state.edu/~sgomori/ ... tions.html
Und die momentane Lösung ist auf dem Papier entstanden, da habe ich mir den Baum aus meinem Beispiel mal aufgezeichnet. Das letzte Print-Statement in einfuegen_recur hat deshalb auch keinen Elternknoten, da es ja der Wert 10 ist.
Meiner Meinung nach habe ich da jedoch irgendwo nen Logikknick drin :K

[BlackJack]

@Mirodin: Also ich würde ja mit einem ordentlichen und selbstentwickelten binärem Baum anfangen. Einer der „pythonisch” ist. Der aus dem Forum ist gruselig wegen der Getter/Setter und weil der Autor bei den `__del__()`-Methoden und ``del``-Anweisungen eindeutig zeigt, dass er von Python nicht viel Ahnung hat.

Man kann dann auch auf dem normalen binären Baum die Knoten auch mit dem jeweiligen Elternknoten verbinden und das traversieren nicht-rekursiv mit einem Cursor-Objekt implementieren. Damit kann man sich dann später zum Beispiel geziehlt in richtung Wurzel bewegen um den/die Knoten zu finden wo rotiert werden muss.

Als Zwischenschritt könnte man auch erst einmal einen Rot-Schwarz-Baum nach dem naiven Binärbaum implementieren. Der ist etwas einfacher zu implemementieren, besser ausgeglichen als der naive Binärbaum aber nicht so gut wie der AVL-Baum, braucht aber auch schon die Rotationen.

Zum AVL-Baum vielleicht eine kleine Anekdote aus dem Studium: Den hatte mal ein Prof als Hausaufgabe aufgegeben. Am nächsten Tag war er total übermüdet und hat die Aufgabe abgewandelt, weil er sich die Nacht um die Ohren geschlagen hatte und es selbst nicht hinbekommen hatte. Er meinte was er nicht an einem Tag/einer Nacht implementiert bekommt, kann er schlecht von seinen Studenten erwarten. Wobei man dazu sagen muss, dass der Ahnung vom Programmieren hatte und auch in der Vorlesung vollständige und funktionierende Codebeispiele sowohl auf den Folien hatte, als auch live entwickeln konnte.

[BlackJack]

In der Dokumentation von `bintree` ist dieses Tutorial zu AVL-Bäumen verlinkt: Eternally Confuzzled - AVL Tree Tutorial.

Man muss C-Quelltext zumindest lesen/verstehen können. Der Trick mit dem Array für die beiden Kindknoten und Wahrheitswerten als Index funktioniert in Python mit `list`- und `bool`-Objekten auch.

[Mirodin]

[...] und das traversieren nicht-rekursiv mit einem Cursor-Objekt implementieren [...]

Ok, auch wenn ich keine Ahnung habe, wie man so ein Objekt zusammentippt, weiß ich doch, was du meinst

Als Zwischenschritt könnte man auch erst einmal einen Rot-Schwarz-Baum nach dem naiven Binärbaum implementieren

Nach deinen obigen Ausführungen denke ich, dass du Recht hast und ich erst mal mit "kleinen" Brötchen, sprich einer neuen BTree Implementierung anfangen sollte. Ich hätte nicht gedacht, dass es derart schwer ist, einen AVL zu implementieren, aber wenn selbst ein Info-Prof daran zu beißen hat, ist es vermutlich für mich noch etwas früh

Danke dir für den Link, das führe ich mir zuhause gleich mal zu Gemüte.
Und danke auch für die Geduld mit mir

LG

[BlackJack]

@Mirodin: Diese Bäume sind kniffelig weil man halt auf die ganzen Sonderfälle achten muss, wie die Wurzel und dass man auch immer alle Informationen oder Verknüpfungen der Knoten beim rotieren richtig aktualisiert.

Auf der anderen Seite braucht man diese Datenstruktur nicht so oft, das heisst die Fälle bei denen eine Hash-Tabelle und gegebenenfalls ein sortieren der Schlüssel nicht ausreichen sind relativ rar. Das motiviert normalerweise auch nicht sich mit der Implementierung zu beschäftigen. Beziehungsweise nimmt man dann lieber etwas fertiges was schon getestet ist.