I am implementing a BST and everything works, even the deletion with two children.The only bug is in the deletion of a leaf which seems such a trivial task. There seem to be still a reference to the leaf node but I can’t get on top of this issue.Putting node = None doesn’t remove the entire Node.I have also tried del node without any luck.If you could spot the problem it would be nice.
import random
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.parent = None
self.left_child = None
self.right_child = None
self.level = None
class Tree:
def __init__(self):
self.root = None
self.size = 0
self.height = 0
def _insertion(self, root, data):
new_node = Node(data)
if root.data < data:
if root.right:
return self._insertion(root.right, data)
root.right = new_node
root.right.parent = root
root.right_child = root.right
return
if root.data > data:
if root.left:
return self._insertion(root.left, data)
root.left = new_node
root.left.parent = root
root.left_child = root.left
return
def insertion(self, data):
new_node = Node(data)
if not self.root:
self.root = new_node
return
return self._insertion(self.root, data)
def _get_height(self, root):
if not root:
return -1
left_height = self._get_height(root.left)
right_height = self._get_height(root.right)
return 1 max(left_height, right_height)
def get_height(self):
if not self.root:
return 0
return self._get_height(self.root)
def fill_random(self, num_nodes):
for i in range(num_nodes):
random_num = int(random.random()*100)
self.insertion(random_num)
def _inorder(self, root):
if root:
self._inorder(root.left)
print(root.data)
self._inorder(root.right)
def inorder(self):
root = self.root
return self._inorder(root)
def get_max(self, node):
while node.right:
node = node.right
return node.data
def search(self, data):
root = self.root
while root.right or root.left:
if root.data < data:
root = root.right
if root.data > data:
root = root.right
if root.data == data:
return root
return None
def _delete_node(self, root, data):
if root:
if root.data < data:
return self._delete_node(root.right, data)
if root.data > data:
return self._delete_node(root.left, data)
if root.data == data:
if not root.left and not root.right:
root = None
return
if not root.left and root.right:
root = root.right
root.right = None
return
if not root.right and root.left:
root = root.left
root.left = None
return
if root.right and root.left:
value = self.get_max(root)
print(f"This is the value: {value}")
root.data = value
self._delete_node(root.right, value)
def delete_node(self, data):
if not self.root:
return None
return self._delete_node(self.root, data)
if __name__ == '__main__':
my_tree = Tree()
my_tree.insertion(33)
my_tree.insertion(36)
my_tree.insertion(25)
my_tree.insertion(20)
my_tree.insertion(27)
my_tree.insertion(35)
my_tree.insertion(39)
my_tree.delete_node(33)
my_tree.inorder()
my_tree.search(35)
CodePudding user response：
In your _delete_node function, it doesn't help to set root to None. That only affects the variable, but does not bring any change to the tree.
A common "trick" is to return root to the caller -- who is then responsible to assign that returned value back to where it is referenced in the tree. For instance, if the recursive call was made with root.left as argument, and the recursive call wants to delete that node, it will return None, and the caller must then assign (whatever it gets back) to root.left. So now the tree is mutated as intended.
Here are your delete_node functions adapted along that principle:
def _delete_node(self, root, data):
if root:
if root.data < data:
root.right = self._delete_node(root.right, data)
elif root.data > data:
root.left = self._delete_node(root.left, data)
elif not root.left:
return root.right
elif not root.right:
return root.left
else:
value = self.get_max(root)
print(f"This is the value: {value}")
root.data = value
root.right = self._delete_node(root.right, value)
return root
def delete_node(self, data):
if self.root:
self.root = self._delete_node(self.root, data)
Another remark
Your search function has some issues:
The
whilecondition should check whetherrootisNonebefore accessing any of its attributes.The
ifblocks should be tied together withelif, otherwise the execution may fall into a secondifblock which is not the intension.
Here is the corrected version:
def search(self, data):
root = self.root
while root:
if root.data < data:
root = root.right
elif root.data > data:
root = root.right
else:
return root
return None
Little improvement
To help debug this code, I altered the inorder method with a little change, so that the tree is printed with indentations:
def _inorder(self, root, indent=""):
if root:
self._inorder(root.left, indent " ")
print(indent str(root.data))
self._inorder(root.right, indent " ")
This helps to quickly see the structure of the tree. You might even want to switch left and right, so that it looks like a rotated tree.
CodePudding user response：
This block of code doesn't do anything:
if root.data == data:
if not root.left and not root.right:
root = None
return
because root is a local variable; reassigning it to None doesn't affect the tree.
What you need to do is change the parent node's right or left pointer. I'd suggest doing this before you recurse, but you could also solve it by passing the parent node into this function.