Binärer Suchbaum erzeugen bzw. unorderable types: int() < No

[Butterblum]

Hallo zusammen,
als erstes möchte ich anmerken, daß ich Foren-Neuling bin und nach meinem Thema das Forum, leider ohne Erfolg,
durchsucht habe. Sollte es doch schon irgendwo behandelt worden sein, bitte ich um Entschuldigugn und freue mich
über einen Link
Ansonsten hau ich mal meine Frage raus, vlt weiss ja jemand Rat:

Und zwar bin ich dabei einen Binären Suchbaum zu implementieren:

Code: Alles auswählen

class BST(object): #Klasse Binary Search Tree
    
    def __init__(self, key=None, leftTree=None, rightTree=None, value=None):
        self.key = key
        self.leftTree = leftTree
        self.rightTree = rightTree
        self.value = value

    def insert(self, key):
        if key < self.key:
            if self.leftTree == None:
                self.leftTree = BST(key)
            else:
                self.leftTree.insert(key)
        elif key > self.key:
            if self.rightTree == None:
                self.rightTree = BST(key)
            else:
                self.rightTree.insert(key)

Die Klasse hat noch andere Funktionen aber nur die insert macht mir Probleme.
Den key in der Parameter liste habe ich mit Absicht auf None gesetzt damit ich einen leeren Baum erzeugen kann.

Code: Alles auswählen

binaryTree = BST()

Um den Baum mit Testdaten zu füllen habe ich eine Random Liste geschrieben und will in einer Schleife alle Elemente
der Liste an den Baum anhängen. Leider bekomme ich dabei eine Fehlermeldung

Code: Alles auswählen

liste = [random.randrange(1, 100) for _ in range(100)]
for i in range(0, len(liste)-1):
    binaryTree.insert(liste[i])

endet in: TypeError: unorderable types: int() < NoneType()

Wenn ich allerdings einen neuen Baum mit z.B.

Code: Alles auswählen

binaryTree = BST(5)

erzeuge, also direkt die Wurzel des Baums mitliefere klappt der Code. Es gibt also anscheined eine Typ Kollision.
Weiss jemand wie ich den Code ändern muss, um einen leeren Baum zu erzeugen den ich mit der beschriebenen
insert Methode füllen kann?

Wäre toll wenn jemand ne Idee hätte.
Vielen Dank schonmal

[/me]

Was erwartest du denn sonst was passieren soll? In deiner insert-Methode vergleichst du den übergebenen key mit dem key des aktuellen Knotens (self.key). Da dieser aber None ist wenn du dem Root-Node keinen expliziten key mitgibst kommt es natürlich zum Vergleich von None mit einem anderen Wert.

Du könntest den key des Root-Nodes auf irgendeinen sinnvollen Wert initialisieren.

Code: Alles auswählen

    def __init__(self, key=None, leftTree=None, rightTree=None, value=None):
        self.key = key if key is not None else 50
        self.leftTree = leftTree
        self.rightTree = rightTree
        self.value = value

Ob jetzt die 50 ein geeigneter Wert ist oder ob du den Parameter doch lieber explizit mitgibst kannst nur du anhand deiner Daten entscheiden. Ich persönlich würde erst gar keinen Default-Wert für den Key vorsehen. Der Root-Node steht nicht alleine im Raum. Du brauchst einen Wert um zu entscheiden ob du links oder rechts weitermachen möchtest.

[BlackJack]

@Butterblum: Du müsstest den Sonderfall `None` halt noch mal extra behandeln in der `insert()`. Ich würde mich da aber /me anschliessen und gar nicht erst Wurzeln ohne Wert erzeugen wollen, denn diesen Sonderfall muss man dann in der Folge überall mit herum schleppen und in jeder Methode durch extra Code berücksichtigen. Das macht alles nur unnötig komplexer.

[/me]

Zwei weitere Hinweise fehlen noch.

1. Vergleiche mit Singletons wie None sollte man immer mit is oder is not durchführen, nicht mit ==.
2. Die Namensgebung entspricht nicht den Namenskonventionen aus dem Style Guide for Python Code. leftTree sollte beispielsweise left_tree heißen. Selbst wenn dir deine Schreibweise (bisher) besser gefällt, so ist doch spätestens beim Austausch mit anderen Entwicklern eine standardisierte Namensvergabe sinnvoll.

[Butterblum]

Danke für eure Antworten, ich habe es jetzt folgendermaßen gelöst

Code: Alles auswählen

liste = [random.randrange(1, 100) for _ in range(100)]

binaryTree = BST(liste[0])

def fillTree(l):
    for i in range(1, len(liste)-1):
        binaryTree.insert(liste[i])

ich nehme einfach den ersten Wert der erzeugten Liste als Wurzel und beginne später in der Schleife bei Indexposition 1 statt 0.
Das ist bestimmt nicht die sauberste Lösung aber für meine Zwecke reicht das aus. Ich mache momentan ein Laufzeitvergleich
verschiedener Datenstrukturen und da muss ich immer wieder die DS mit Zufallsdaten füllen. Also vielen Dank nochmal für Eure
Hilfe.

@/me
Du hast Recht mit der Namensgebung, da kenn ich mich in Python noch nicht so gut aus. Ich komm aus der Java Ecke da würde man
leftTree genauso schreiben
Werds ändern

Gruß

[BlackJack]

@Butterblum: Schleifen über Zahlen um die dann als Indizes zu verwenden ist in Python ein Anti-Pattern. Man würde hier eher einen Iterator erzeugen, sich mit `next()` das erste Element holen, und dann über den Rest iterieren. Wenn man das so löst kann man sich die Liste auch ganz sparen und stattdessen einen Generatorausdruck verwenden. Ansonsten könnte man auch mit `pop()` das letzte Element aus der Liste für die Wurzel nehmen und dann über die Liste iterieren um die anderen Werte hinzuzufügen.

Das die Funktion den Baum nicht als Argument übergeben bekommt ist auch sehr unschön. Und das Argument `l` (sehr schlechter Name) wird auch nicht verwendet, stattdessen die modulglobale `liste`.

Edit:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf-8
from __future__ import absolute_import, division, print_function
from random import randrange


class BinarySearchTree(object):
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

    def __iter__(self):
        if self.left:
            for key in self.left:
                yield key
        yield self.key
        if self.right:
            for key in self.right:
                yield key

    def insert(self, key):
        if key < self.key:
            if self.left is None:
                self.left = BinarySearchTree(key)
            else:
                self.left.insert(key)
        elif key > self.key:
            if self.right is None:
                self.right = BinarySearchTree(key)
            else:
                self.right.insert(key)
        else:
            pass  # Keys are equal - ignore.
    
    @classmethod
    def from_keys(cls, keys):
        keys = iter(keys)
        root = cls(next(keys))
        for key in keys:
            root.insert(key)
        return root


def main():
    tree = BinarySearchTree.from_keys(randrange(1, 100) for _ in xrange(100))
    print(list(tree))


if __name__ == '__main__':
    main()

[Sirius3]

@Butterblum: ist es eigentlich Absicht, dass das letzte Element der Liste nicht in den Baum aufgenommen wird?
Um BlackJacks Worte in Code zu kleiden:

Code: Alles auswählen

def create_tree(items):
    items = iter(items)
    result = BST(next(items))
    for item in items:
        result.insert(item)
    return result

tree = create_tree(random.randrange(1, 100) for _ in range(100))