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-02 19:50
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.

Pozostało 580 znaków

2019-12-02 20:31
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/Py[...]ter/binary_search_tree_map.py


Pozostało 580 znaków

2019-12-02 20:49
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/Py[...]ter/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

Pozostało 580 znaków

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


edytowany 1x, ostatnio: lion137, 2019-12-02 21:05

Pozostało 580 znaków

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

Pozostało 580 znaków

2019-12-02 21:07
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ą.

Tak, a najgorsze, że z nim się ciężko się porozumieć, pisze, jakby rozmawiał sam ze sobą. - lion137 2019-12-02 22:00

Pozostało 580 znaków

2019-12-03 01:59

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).

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