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

Odpowiedz Nowy wątek
2019-12-01 23:08
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])

Pozostało 580 znaków

2019-12-01 23:31
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.

Pozostało 580 znaków

2019-12-01 23:40
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.

Pozostało 580 znaków

2019-12-01 23:40
0

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


Pozostało 580 znaków

2019-12-01 23:57
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..

Pozostało 580 znaków

2019-12-02 00:26
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ć.

edytowany 1x, ostatnio: enedil, 2019-12-02 00:28

Pozostało 580 znaków

2019-12-02 14:46
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:)


Pozostało 580 znaków

2019-12-02 15:02
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.

Pozostało 580 znaków

2019-12-02 15:44
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.


Pozostało 580 znaków

2019-12-02 16:54
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.

Pozostało 580 znaków

2019-12-02 18:31
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.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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