I'm currently taking a course where I'm learning data structures and algorithms, and I'm learning about BST's. I already got the code to work and understand most of it, but I got a question for the deletion function. This is what my code looks like:
class BST:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(self, value):
currentNode = self
while True:
if value < currentNode.value:
if currentNode.left is None:
currentNode.left = BST(value)
break
else:
currentNode = currentNode.left
else:
if currentNode.right is None:
currentNode.right = BST(value)
break
else:
currentNode = currentNode.right
return self
def contains(self, value):
currentNode = self
while currentNode is not None:
if value < currentNode.value:
currentNode = currentNode.left
elif value > currentNode.value:
currentNode = currentNode.right
else:
return True
return False
def remove(self, value, parentNode = None):
currentNode = self
while currentNode is not None:
if value < currentNode.value:
parentNode = currentNode
currentNode = currentNode.left
elif value > currentNode.value:
parentNode = currentNode
currentNode = currentNode.right
#Found the node
else:
#two child ondes
if currentNode.left is not None and currentNode.right is not None:
currentNode.value = currentNode.right.getMinValue() #get the left number from the right subtree
currentNode.right.remove(currentNode.value, currentNode) #remove that most left number by using remove()
#on the right currentNode
#root node
elif parentNode is None:
if currentNode.left is not None:
currentNode.value = currentNode.left.value
currentNode.right = currentNode.left.right
currentNode.left = currentNode.left.left
elif currentNode.right is not None:
currentNode.value = currentNode.right.value
currentNode.left = currentNode.right.left
currentNode.right = currentNode.right.right
#only 1 item left in BST
else:
pass
#one child node
elif parentNode.left == currentNode:
parentNode.left = currentNode.left if currentNode.left is not None else currentNode.right
elif parentNode.right == currentNode:
parentNode.right = currentNode.left if currentNode.left is not None else currentNode.right
break
return self
def getMinValue(self):
currentNode = self
while currentNode.left is not None:
currentNode = currentNode.left
return currentNode.value
I understand that, for the delete function:
- The
whileloop will iterate over each node and run until there are no more nodes - The first
ifandelifare used to find the node you are trying to remove. - The
elseworks for the actual deletion, which has 3 differnt options: EithercurrentNodehas two childs, and you just replace it by the leftmost value of the right node and delete this leftmost value from the right noe. The other case is thatparentNodehas no parent, which would be the root Node case. And the last case is when you have only one child node all you have to do is change the value ofcurrentNodeeither to its left node or right node (depending which one it has).
What I don't clearly understand is the logic behind the conditions, and how it works when we want to delete a root node. Isn't the code supposed to also run the first condition, which is the one for two child nodes? I'm almost certain that this isn't supposed to happen, and the condition should only run for its special case. I have seen again and again the video explanation, but I just can't get a hang of it.
#two child ondesand replacing the comment#root nodewith#root node with at most one child node.else: passunderelif parentNode is None:. Silent errors should generally be avoided.