Drzewo BST z łączem do rodzica - pętla

0

Siema. Słuchajcie - naskrobałem takie sobie drzewo w pythonie. Niby wszystko git przy małych drzewach,ale przy drzewach generowanych losowo (np. 5000 nodeów) operacja usuwania się zapętla... Prawdopodobnie źle przepinam wskaźniki przy usuwaniu (np. parent.left=node.left etc). Ktoś mógłby mi pomóc przy lokalizacji buga? Nie mam już siły i pomysłów. Cały kod przestudiowałem już z kilkanaście/kilkadziesiąt razy.


```import random


class Node:
    def __init__(self, val):
        self.val = val
        self.parent = None
        self.right = None
        self.left = None
        # Class of node.
    def str(self):
        return str(self.val)


class MyTree:
    def __init__(self, node):
        self.root = node

    def insert(self, node):
        current = self.root
        a = True
        while a:
            if node.val > current.val:
                if current.right is not None:
                    current = current.right
                    continue
                else:
                    current.right = node
                    node.parent = current
                    a = False
            if node.val <= current.val:
                if current.left is not None:
                    current = current.left
                    continue
                else:
                    current.left = node
                    node.parent = current
                    a = False

    def search(self, node):
        current = self.root

        while node.val != current.val:
            if node.val > current.val:
                current = current.right
                continue
            elif node.val <= current.val:
                current = current.left
                continue
        if node.val == current.val:
            return current
        else:
            print("There is no such node!")

    def delete(self, node):

        if isinstance(node, (float, int)):
            node = self.search(node)

        if node is self.root:
            self.__deleteRoot()
            return
        else:
            if node.right is None and node.left is None:
                self.__deleteNN(node)
                return
            if node.right is None and node.left is not None:
                self.__deleteLN(node)
                return
            if node.right is not None and node.left is None:
                self.__deleteNR(node)
                return
            if node.right is not None and node.left is not None:
                self.__deleteLR(node)
                return

    def __deleteNN(self, node):
        if node.parent.left is node:
            node.parent.left = None
        if node.parent.right is node:
            node.parent.right = None

    def __deleteLN(self, node):
        parent = node.parent
        son = node.left
        # parent replaced
        if parent.left is node:
            parent.left = son
        if parent.right is node:
            parent.right = son
        son.parent = parent


    def __deleteNR(self,node):
        parent = node.parent
        son = node.right
        # replace parent
        if parent.left is node:
            parent.left = son
        if parent.right is node:
            parent.right = son
        son.parent = parent
    def __deleteLR(self, node):

        minimal = self.getMinimal(node.right)
        if minimal.parent.left is minimal:
            minimal.parent.left = None
        if minimal.parent.right is minimal:
            minimal.parent.right = None
        # parent of minimal done..
        if node.parent.left is node:
            node.parent.left = minimal
        if node.parent.right is node:
            node.parent.right = minimal
        minimal.right = node.right
        minimal.left = node.left

    def getMinimal(self, node):
        k = node
        while k.left is not None:
            k = k.left
        return k

    def getMax(self):
        current = self.root
        while current.right:
            current = current.right
        return current

    def __trav(self, node):
        if not node:
            return
        print(node.val)
        self.__trav(node.left)
        self.__trav(node.right)

    def printTrav(self):
        self.__trav(self.root)

    def __deleteRoot(self):
        if self.root.left is None and self.root.right is None:
            self.root = None
            return
        if self.root.left is None and self.root.right is not None:
            # left empty,right full
            self.root.right.parent = None
            self.root = self.root.right
            return
        if self.root.left is not None and self.root.right is None:
            # right empty, left full
            self.root.left.parent = None
            self.root = self.root.left
            return
        # node has both children
        if self.root.left is not None and self.root.right is not None:
            temp = self.getMinimal(self.root.right)  # minimal from right subtree
            # sometimes it could be like this..
            # r
            #   \
            #    x
            if temp.parent.left is temp:
                temp.parent.left = None
            else:
                temp.parent.right = None

            self.root.left.parent = temp
            self.root.right.parent = temp
            temp.right = self.root.right
            temp.left = self.root.left
            self.root = temp
            self.root.parent = None

            return

    def search(self, val):
        node = self.root
        if node.val == val:
            return node
        if val > node.val and node.right is not None:
            node = node.right
        if val < node.val and node.left is not None:
            node = node.left
        else:
            print("There's no such value!")
            return
    def printMax(self):
        print(self.getMax().val)
    def printMin(self):
        print(self.getMinimal(self.root).val)

arr=[None]*2500
for x in range(2500):
    arr[x]=Node(random.randint(0,10000))

myTree = MyTree(arr[0])
for x in range(1,2500):
    myTree.insert(arr[x])
for x in range(2500):
    print(arr[x].val)
    myTree.delete(arr[x])
0

Nie wiem co jest Twoim problemem, ale w trakcie uruchamiania natrafiłem także na taki błąd, różny od Twojego

Traceback (most recent call last):
  File "a.py", line 194, in <module>
    myTree.delete(arr[x])
  File "a.py", line 57, in delete
    self.__deleteRoot()
  File "a.py", line 162, in __deleteRoot
    self.root.right.parent = temp
AttributeError: 'NoneType' object has no attribute 'parent'

Gdzieś nie ustawiasz parenta. Btw, BST to jest raczej prosta struktura, mocno przekombinowany kod.

0
enedil napisał(a):

Nie wiem co jest Twoim problemem, ale w trakcie uruchamiania natrafiłem także na taki błąd, różny od Twojego

Traceback (most recent call last):
  File "a.py", line 194, in <module>
    myTree.delete(arr[x])
  File "a.py", line 57, in delete
    self.__deleteRoot()
  File "a.py", line 162, in __deleteRoot
    self.root.right.parent = temp
AttributeError: 'NoneType' object has no attribute 'parent'

Gdzieś nie ustawiasz parenta. Btw, BST to jest raczej prosta struktura, mocno przekombinowany kod.

Yup. BST jest banalne, ale tutaj pododawałem operacje usuwania - stąd problemy. Dziwne, nie dostałem takiego błędu nigdy. Chyba brakuje jakiegoś ifa,albo się coś nie przekopiowalo. A mój problem jest taki że w pewnym momencie funkcja getMinimal() która wyszukuje minimalnego nodea z prawego podrzewa wpada w pętlę. Albo robi się coś takiego : a.left = a (wskazuje sam na siebie), albo coś takiego a.left = b, b.left = c, c.left =a - i tak w kółko.

0

Sorry mate:) ale dupa debugging za Ciebie nie zrobimy:) pdb do ręki i Szukaj tych nullpointerów.

0
lion137 napisał(a):

Sorry mate:) ale dupa debugging za Ciebie nie zrobimy:) pdb do ręki i Szukaj tych nullpointerów.

Okeya bro, ale myślałem że ktoś rzuci okiem - bo ja błędu nie widzę. Przepinanie wskażników działa gites..

0

No, jeśli gdzieś "się" nie przepięło, to bym na to spojrzał, bo być może też pomoże w Twoim błędzie. My też błędu nie widzimy w tym, bo w tym nic nie da się zobaczyć, bo to jest niesamowity bałagan z kodu, kod spaghetti. Uporządkuj go, pomyśl jeszcze raz nad zgrabnym zapisaniem warunków, wtedy można będzie patrzeć.

0

"BST jest banalne", być może, ale implementacja jest trochę skomplikowana. Ja bym sobie w tej pętli testowej zapamiętał dane dla których się wysypuje i zdebugował dla nich (jest szansa, że będzie do sprawdzenia tylko jedna z metod usuwających).
Poza tym tu jest, imo, sporo WTF - ów:
ściśle rzecz biorąc to nie jest BST - nie ma par klucz: wartość, tylko klucze (które dla odmiany Nazywasz val:));
Inicjalizujesz obiekt obiektem typu node??? Czemu nie val, to samo w insert;
po co isinstance, Python jest Duck Typing, więc sam sobie znajdzie odpowiednie metody: <, ==, etc.;
nie wiem czy Wiesz, ale Masz dwie metody search:)

0
lion137 napisał(a):

"BST jest banalne", być może, ale implementacja jest trochę skomplikowana. Ja bym sobie w tej pętli testowej zapamiętał dane dla których się wysypuje i zdebugował dla nich (jest szansa, że będzie do sprawdzenia tylko jedna z metod usuwających).
Poza tym tu jest, imo, sporo WTF - ów:
ściśle rzecz biorąc to nie jest BST - nie ma par klucz: wartość, tylko klucze (które dla odmiany Nazywasz val:));
Inicjalizujesz obiekt obiektem typu node??? Czemu nie val, to samo w insert;
po co isinstance, Python jest Duck Typing, więc sam sobie znajdzie odpowiednie metody: <, ==, etc.;
nie wiem czy Wiesz, ale Masz dwie metody search:)

-Dwie metody search - to błąd, wczoraj przeczytałem że w pytongu przeciążanie nie działa tak jak w javie ;)
-Wysypuje się w różnych deletach. To jest uzależnione od poprzednich operacji - np.sypie operacja delete LR, ale wcześniej grzebała przy tym nodzie inna operacja :/
-To taka luźna implementacja - tak jak wiele grafów zaimplementowanych nie spełnia warunku że graf to dwa zbiory.
-inicjalizuję obiekt Drzewa obiektem Node - czyli kontruktor przyjmuje roota.
-isInstance - jeżeli user podał obiekt nodea,to usuwamy tego nodea, jezeli podał inta,floata to znaczy że chce usunąć nodea z taką wartością - program wyszukuje pierwsze wystąpienie w/w nodea.

0

np.sypie operacja delete LR, ale wcześniej grzebała przy tym nodzie inna operacja

To znaczy, że Masz zły design, przypadki powinne być rozdzielone.

inicjalizuję obiekt Drzewa obiektem Node - czyli kontruktor przyjmuje roota.
-isInstance - jeżeli user podał obiekt nodea,to usuwamy tego nodea, jezeli podał inta,floata to znaczy że chce usunąć nodea z taką wartością - program wyszukuje pierwsze wystąpienie w/w nodea.

Znowu zły design; ADT polega na tym, że wewnętrzna struktura jest całkowicie niewidoczna dla klienta.

0
lion137 napisał(a):

np.sypie operacja delete LR, ale wcześniej grzebała przy tym nodzie inna operacja

To znaczy, że Masz zły design, przypadki powinne być rozdzielone.

inicjalizuję obiekt Drzewa obiektem Node - czyli kontruktor przyjmuje roota.
-isInstance - jeżeli user podał obiekt nodea,to usuwamy tego nodea, jezeli podał inta,floata to znaczy że chce usunąć nodea z taką wartością - program wyszukuje pierwsze wystąpienie w/w nodea.

Znowu zły design; ADT polega na tym, że wewnętrzna struktura jest całkowicie niewidoczna dla klienta.

Trochę nie rozumiesz,albo ja nie umiem Ci tego wytłumaczyć.Przypadki są rozdzielone - ale to na tej zasadzie typu: lakiernik zwraca polakierowane auto z uszkodzonym błotnikiem, bo wcześniej ten błotnik klepał blacharz. Czaisz? Mamy drzewo - usuwamy jakiegoś nodea i LR modyfikuje to drzewo przestawiając jakieś nody. Potem idzie znowu jakaś operacja delete np. NR, ona modyfikuje to drzewo "dotykając" np.jakiegos nodea przy którym 4 operacja wcześniej grzebała inna operacja. Przejrzałeś ten kod?

Struktura jest niewidoczna, user tworzy tylko node'y - tak sobie wymyśliłem. Żeby działało na obiektach a nie wartościach.

0

Popraw błąd o którym mówiłem. Nie natrafisz na niego, bo pojawia się jak usuwasz korzeń. Ja uruchamiałem z 3 wierzchołkami, a nie 2500cioma, i wyskakiwał nader często.

0
enedil napisał(a):

Popraw błąd o którym mówiłem. Nie natrafisz na niego, bo pojawia się jak usuwasz korzeń. Ja uruchamiałem z 3 wierzchołkami, a nie 2500cioma, i wyskakiwał nader często.

Powiesz mi z jakimi wartościami? Mam dla 6 i działa ok - podaj wartości, bo może to mnie naprowadzi na błąd.

0

Masz tam, domyślam się, od cholery błędów, nie tylko przy usuwaniu korzenia (znaczy ten przy korzeniu też jest: line 165, in __deleteRoot self.root.right.parent = temp AttributeError: 'NoneType' object has no attribute 'parent'). A to przy usuwaniu liścia:

tree = MyTree(Node(5))
tree.insert(Node(3))
tree.insert(Node(7))

tree.printTrav()  # -> 3 5 7 zmiana na inorder, posortowane
tree.delete(3)  # -> line 62, in delete if node.right is None and node.left is None:
                # -> AttributeError: 'NoneType' object has no attribute 'right'
tree.printTrav()

Tu Masz w miarę (moją) implementacji BST: https://github.com/lion137/Python-Data-Structures/blob/master/binary_search_tree_map.py

0
lion137 napisał(a):

Masz tam, domyślam się, od cholery błędów, nie tylko przy usuwaniu korzenia (znaczy ten przy korzeniu też jest: line 165, in __deleteRoot self.root.right.parent = temp AttributeError: 'NoneType' object has no attribute 'parent'). A to przy usuwaniu liścia:

tree = MyTree(Node(5))
tree.insert(Node(3))
tree.insert(Node(7))

tree.printTrav()  # -> 3 5 7 zmiana na inorder, posortowane
tree.delete(3)  # -> line 62, in delete if node.right is None and node.left is None:
                # -> AttributeError: 'NoneType' object has no attribute 'right'
tree.printTrav()

Tu Masz w miarę (moją) implementacji BST: https://github.com/lion137/Python-Data-Structures/blob/master/binary_search_tree_map.py

Błąd był w searchu - nie wyszukiwało nodea. Napisałem tą metodę,ale jej nie przetestowałem bo miałem ważniejsze błędy. Testowałem tak jak pokazuje - tworzyłem nodey,trzymałęm referencje do nich i wrzucałem w drzewo. Mniejsza o to. Poprawiony search,teraz działa:


```    def search(self, val):
        node = self.root
        while True:
            if node.val == val:
                return node
            if val > node.val and node.right is not None:
                node = node.right
            if val < node.val and node.left is not None:
                node = node.left
        else:
            print("There's no such value!")
            return
0

Czytałeś mój post? Błąd jest w metodzie delete, search znajduje mi właściwy node, 3; node jest None - nie można na nim wywołać right, czy left.

0
CoffeBreaker napisał(a):
enedil napisał(a):

Popraw błąd o którym mówiłem. Nie natrafisz na niego, bo pojawia się jak usuwasz korzeń. Ja uruchamiałem z 3 wierzchołkami, a nie 2500cioma, i wyskakiwał nader często.

Powiesz mi z jakimi wartościami? Mam dla 6 i działa ok - podaj wartości, bo może to mnie naprowadzi na błąd.

Uruchom ten sam program co wcześniej, tylko że zastąp 2500 przez 3.

0

I taka ogólna uwaga - Twój kod to kaszanka, jest tam z pewnością mnóstwo bugów. Nie brnij w zaparte, nie pozwalaj sobie na błąd "gdzieś indziej" - wydłużasz sobie tylko pracę. Jak widzisz błąd - napraw go, może inne znikną.

0

Dobra. Nie odpisuje sam sobie - spokojnie Pan @lion137 ;) Kodzik poprawiony - były 2 błędy (takie mocne) w deleteLR oraz to samo przy roocie. Brakło głupiego przepięcia jednego wskażnika... Czyli tak jak się spodziewałem. Dla 10k nodeów przeszło już 30 prób więc myślę że jest git. Ale puszczę jeszcze kilka razy testy. Kod z pierwszego posta jest raczej do wyrzucenia (zmiany w końcowym są dosyć znaczne).

1 użytkowników online, w tym zalogowanych: 0, gości: 1