I have been learning data structures and have been trying to implement the delete method in my BST class. What I have noticed is that instead of deleting one node it will delete the whole subtree that the node is a part of.
class BST:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def addchild(self, child):
if child == self.data:
return
if child < self.data:
if self.left:
self.left.addchild(child)
else:
self.left = BST(child)
else:
if self.right:
self.right.addchild(child)
else:
self.right = BST(child)
def search(self, data):
if self.data == data:
return True
if data < self.data:
if self.left:
return self.left.search(data)
else:
return False
else:
if self.right:
return self.right.search(data)
else:
return False
def iot(self):
vals = []
if self.left:
vals = self.left.iot()
vals.append(self.data)
if self.right:
vals = self.right.iot()
return vals
def findmax(self):
if self.right:
return self.right.findmax()
else:
return self.data
def findmin(self):
if self.left:
return self.left.findmin()
else:
return self.data
def delete(self, data):
if data < self.data:
if self.left:
self.left = self.left.delete(data)
elif data > self.data:
if self.right:
self.right = self.right.delete(data)
else:
if self.left is None and self.right is None:
return None
elif self.left is None:
return self.right
elif self.right is None:
return self.left
minval = self.right.findmin()
self.data = minval
self.right = self.right.delete(minval)
def buildtree(arr):
r = BST(arr[0])
for i in range(1, len(arr)):
r.addchild(arr[i])
return r
So when input with these values and deleting the number 1 from the tree it will print this
bst = buildtree([34, 7, 8, 1, 3, 4, 5, 10, 65, 98, 100, 203])
print(bst.iot())
bst.delete(1)
print(bst.iot())
1st print statement output: [1, 3, 4, 5, 7, 8, 10, 34, 65, 98, 100, 203]
2nd print statement output: [34, 65, 98, 100, 203]
When I debug in Pycharm, before leaving the delete method and after all steps are executed the tree will show that the left subtree is intact and everything is how it should be. However once I leave the method the left subtree becomes None.
Any help would be appreciated.
CodePudding user response:
Here's a strong hint:
You are missing a return statement on final block of you code:
minval = self.right.findmin()
self.data = minval
self.right = self.right.delete(minval)
CodePudding user response:
A debug answer: In your example 1 is going to be the leftmost leaf in the tree. So look what’s happening: When you start the method delete you say that
if data < self.data:
if self.left:
self.left = self.left.delete(data)
So basically the left son of the root will hold whatever comes at the end of the process. If you will follow the left branch until you get 1, you will see that you get the the case of
else:
if self.left is None and self.right is None:
return None
This means that the root left son is None, and this explains your bug