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