In: Computer Science
PYTHON CODING
Create a method for the Binary Search Tree (deleteNode) that deletes a specified node identified by its value, and rearranges the descendants of the deleted node to ensure the resulting Tree meets the requirements of a Binary Search Tree.
a) Discuss and justify your approach to address each possible case.
b) Is the new tree (with the deleted node removed) unique? Discuss your answer.
Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.
Illustrate the performance of the deleteNode method. For the BST of datalist delete 71, 400, 271 938, and 69 from the tree in the same order. For all illustrated examples, enumerate the trees (before and after deletion) using your orderTraversal and justify the correctness of your delete method
Discuss and justify your approach to address each possible case.
BST Deletion
Delete function is used to delete the specified node from a binary search tree. However, we must delete a node from a binary search tree in such a way, that the property of binary search tree doesn't violate. There are three situations of deleting a node from binary search tree.
The node to be deleted is a leaf node
It is the simplest case, in this case, replace the leaf node with the NULL and simple free the allocated space.
In the following image, we are deleting the node 85, since the node is a leaf node, therefore the node will be replaced with NULL and allocated space will be freed.
fig
The node to be deleted has only one child.
In this case, replace the node with its child and delete the child node, which now contains the value which is to be deleted. Simply replace it with the NULL and free the allocated space.
In the following image, the node 12 is to be deleted. It has only one child. The node will be replaced with its child node and the replaced node 12 (which is now leaf node) will simply be deleted.
fig
The node to be deleted has two children.
It is a bit complexed case compare to other two cases. However, the node which is to be deleted, is replaced with its in-order successor or predecessor recursively until the node value (to be deleted) is placed on the leaf of the tree. After the procedure, replace the node with NULL and free the allocated space.
In the following image, the node 50 is to be deleted which is the root node of the tree. The in-order traversal of the tree given below.
6, 25, 30, 50, 52, 60, 70, 75.
replace 50 with its in-order successor 52. Now, 50 will be moved to the leaf of the tree, which will simply be deleted.
fig
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
b) Is the new tree (with the deleted node removed) unique? Discuss your answer.
Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.
yes the new tree with the deleted nod removed is unique.
For deleting a Node there are three scenarios possible..
Before knowing the concept of deletion, we should understand the concept of successor and predecessors
Successor: In a binary tree successor of a node is the smallest node of the tree that is strictly greater then this node.
There are two possible cases with a node
A node has right children: In this case the leftmost child of the right sub-tree will be successor.
A node has no children: Go to the parent node and find a node for which this node is part of left sub-tree.
Discuss method's Big-O notation.
The worst case time complexity for search, insert and delete operations in a general Binary Search Tree is O(n)..
Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose
Algorithm
Delete (TREE, ITEM)
Illustrate the performance of the deleteNode method. For the BST of datalist delete 71, 400, 271 938, and 69 from the tree in the same order. For all illustrated examples, enumerate the trees (before and after deletion) using your orderTraversal and justify the correctness of your delete method
# Python program to demonstrate delete operation
# in binary search tree
# A Binary Tree Node
class Node:
# Constructor to create a new node
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# A utility function to do inorder traversal of BST
def inorder(root):
if root is not None:
inorder(root.left)
print root.key,
inorder(root.right)
# A utility function to insert a new node with given key in
BST
def insert( node, key):
# If the tree is empty, return a new node
if node is None:
return Node(key)
# Otherwise recur down the tree
if key < node.key:
node.left = insert(node.left,
key)
else:
node.right = insert(node.right,
key)
# return the (unchanged) node pointer
return node
# Given a non-empty binary search tree, return the node
# with minum key value found in that tree. Note that the
# entire tree does not need to be searched
def minValueNode( node):
current = node
# loop down to find the leftmost leaf
while(current.left is not None):
current = current.left
return current
# Given a binary search tree and a key, this function
# delete the key and returns the new root
def deleteNode(root, key):
# Base Case
if root is None:
return root
# If the key to be deleted is smaller than the
root's
# key then it lies in left subtree
if key < root.key:
root.left = deleteNode(root.left,
key)
# If the kye to be delete is greater than the
root's key
# then it lies in right subtree
elif(key > root.key):
root.right = deleteNode(root.right,
key)
# If key is same as root's key, then this is the
node
# to be deleted
else:
# Node with only one child or no
child
if root.left is None :
temp =
root.right
root =
None
return
temp
elif root.right is None :
temp =
root.left
root =
None
return temp
# Node with two children: Get
the inorder successor
# (smallest in the right
subtree)
temp = minValueNode(root.right)
# Copy the inorder successor's
content to this node
root.key = temp.key
# Delete the inorder
successor
root.right = deleteNode(root.right
, temp.key)
return root
for illustration run this code in python and insert binary tree containing 71, 400, 271 938, 69 and other values then delete it as above mentioned.For all illustrated examples, enumerate the trees (before and after deletion) using your orderTraversal and justify the correctness of your delete method