-
-
Save jakemmarsh/8273963 to your computer and use it in GitHub Desktop.
class Node: | |
def __init__(self, val): | |
self.val = val | |
self.leftChild = None | |
self.rightChild = None | |
def get(self): | |
return self.val | |
def set(self, val): | |
self.val = val | |
def getChildren(self): | |
children = [] | |
if(self.leftChild != None): | |
children.append(self.leftChild) | |
if(self.rightChild != None): | |
children.append(self.rightChild) | |
return children | |
class BST: | |
def __init__(self): | |
self.root = None | |
def setRoot(self, val): | |
self.root = Node(val) | |
def insert(self, val): | |
if(self.root is None): | |
self.setRoot(val) | |
else: | |
self.insertNode(self.root, val) | |
def insertNode(self, currentNode, val): | |
if(val <= currentNode.val): | |
if(currentNode.leftChild): | |
self.insertNode(currentNode.leftChild, val) | |
else: | |
currentNode.leftChild = Node(val) | |
elif(val > currentNode.val): | |
if(currentNode.rightChild): | |
self.insertNode(currentNode.rightChild, val) | |
else: | |
currentNode.rightChild = Node(val) | |
def find(self, val): | |
return self.findNode(self.root, val) | |
def findNode(self, currentNode, val): | |
if(currentNode is None): | |
return False | |
elif(val == currentNode.val): | |
return True | |
elif(val < currentNode.val): | |
return self.findNode(currentNode.leftChild, val) | |
else: | |
return self.findNode(currentNode.rightChild, val) |
For deletion, the function in Node
class would be
def delete(self):
# cases where the node is a leaf, just remove it
if self.leftNode == None and self.rightNode == None:
if self.parent.value > self.value:
self.parent.rightNode = None
else:
self.parent.leftNode = None
# remove parent's Link
self.parent = None
return
# cases where children are only in one direction, just change the pointers
# where children only in left direction
if self.rightNode == None:
self.parent.leftNode = self.leftNode
self.leftNode.parent = self.parent
self.parent = None
self.leftNode = None
return
# where children only in rightdirection
elif self.leftNode == None:
self.parent.rightNode = self.rightNode
self.rightNode.parent = self.parent
self.parent = None
self.leftNode = None
return
# cases where there are children in both the directions
# swap values between currentNode and its succesorNode
# delete the successor_node(which contains the value to be removed from tree), note that the successor_node is a leaf
successor_node = self.rightNode.find_min_in_sub_tree()
successor_node.value, self.value = self.value, successor_node.value
successor_node.delete()
not easy part: why self.rightNode.find_min_in_sub_tree()
was done. The reason behind doing this is to find its next biggest value(its successor) in the tree
the implementaion of find_min_in_sub_tree. This function finds the minimum element in the tree below it, by continuously looking at the left
def find_min_in_sub_tree(self):
if self.leftNode == None:
return self
if self.leftNode != None:
return self.leftNode.find_min_in_sub_tree()
@shree675, @manjitha27
Do let me know if something is wrong
EDIT- Thanks to @Aniket2ten96 for pointing out the mistake
@rakaar I think the code to find the successor_node might not yield the correct result. Suppose a bst rooted at 69, and its right side nodes are 70,82,84. Now I want to find 69's successor, according to your code i will go to right and i will find the node with maximum key and that will be the successor of 69. In the above example the maximum key is 84, which is not the successor of 69(successor of 69 is 70 in the above example) . I think to find the successor, you have to go right and find the node with minimum key value, which is in the above example 70. Correct me if I am wrong
Thanks a lot @Aniket2ten96 for pointing it out
I have made the changes
You are right, it should be finding out the minimum in the subtree where self.rightNode
acts as the root. Hence replaced the wrong function with find_min_in_sub_tree
along with its implementation
Thank you for the clean example!
Could you please show how deletion is done?