i need to implement remove() part belove code, and it is in python. remove() sho
ID: 3726320 • Letter: I
Question
i need to implement remove() part belove code, and it is in python.
remove() should implement removing node frome BST without changing property of the tree.
removing nodes has following cases. but i am having problen with incorpating and implementing it.
leaf no child
node with left child
node with right child
node with leftor right child
maybe node is root /no child
class BST: class Node: def init self, item, left, right): self. itemitem self. left = left self-right right def init_ _(self): self. root None def isEmpty(self): return self._root is def clear (self) self. root = None # def remove (self, item): To Do: def insert (self, item): self'-root self-insert (self..-root, item) = def insert (self, root, item): if root is None: elif itemExplanation / Answer
#try to understand this code i hope this may help
def remove(self, item):
""" remove the node with the given item and return the
root node of the tree """
if self.item == item:
# found the node we need to delete
if self.right and self.left:
# get the successor node and its parent
[psucc, succ] = self.right._findMin(self)
# splice out the successor
# (we need the parent to do this)
if psucc.left == succ:
psucc.left = succ.right
else:
psucc.right = succ.right
# reset the left and right children of the successor
succ.left = self.left
succ.right = self.right
return succ
else:
# "easier" case
if self.left:
return self.left
# promote the left subtree
else:
return self.right
# promote the right subtree
else:
if self.item > item:
# item should be in the left subtree
if self.left:
self.left = self.left.remove(item)
# else the item is not in the tree
else:
# item should be in the right subtree
if self.right:
self.right = self.right.remove(item)
return self
def _findMin(self, parent):
""" return the minimum node in the current tree and its parent """
if self.left:
return self.left._findMin(self)
else:
return [parent, self]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.