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

2019-12-01 23:08
##### CoffeBreaker
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
##### lion137
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
##### lion137
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
##### 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
##### enedil
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
##### CoffeBreaker

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

Liczba odpowiedzi na stronę