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)
source https://stackoverflow.com/questions/69781406/deleting-the-leaf-node-in-a-binary-tree
Comments
Post a Comment