Create binary search tree class, which supports the following operations: ?1

Subject:Computer SciencePrice:4.86 Bought11

Share With

Create binary search tree class, which supports the following operations:

?1. Insert

?2. Search

?3.Delete

?4.In-order traversal

 

Important

?

1. The implementation should be template based.

 

2. The pointer to parent node should also be included in each node. This means each node should

have 3 pointers: left, right and parent. The insert/search/delete should accordingly.

Insert Algorithm:

 

 

BST_INSERT(node, newNode)
? Input: root node of tree, node to be inserted
? Output: updated tree with newNode
? Steps:
1. If node == null //base case
2. node = newNode
3. Else If newNode.key < node.key
4. node.left = BST_INSERT(node.left, newNode)
5. Else If newNode.key > node.key
6. node.right = BST_INSERT(node.right, newNode)
7. End If
8. Return node

Deletion Algorithm:

 

 

BST_DELETE(node, int key)
? Input: root node of tree, key to be deleted
? Output: updated tree without node that contains key
? Steps:
1. If(node!=null)
2. If key ==node.key
3. If hasLeft(node) and hasRight(node) //case 3
4. successor= INORDER_SUCCESSOR(node)
5. copy(node,successor)
6. node.right= BST_DELETE(node.right, successor.key )
7. Else //case1, case 2, you can break it in 2 if's
8. node=getChildNode(node);
9. End If
9. Else If key < node.key
10. node.left =BST_DELETE(node.left,key)
11. Else // key > node.key
12. node.right =BST_DELETE(node.right,key)
13. End If
14. return node // updated node
15. End If
16. return node // null

getChildNode(node)
1. If hasLeft(node)
2. return node.left
3. Else If hasRight(node)
4. return node.right
5. Else
6. Return NULL// leaf node case
7. End if
copy(node,successor)
1. node.key=successor.key
2. Copy other data attributes if present but
not child links

Search: Algorithm

 

 

? BST_SEARCH(node, key)
? Input: root node of tree, key to be searched
? Output: node which contains value
? Steps:
Start
1. If node== null OR value==node.key //one case for both value found or not found

return node

2. Else If value < node.key
3. return BST_SEARCH( node.left, key)
4. Else // key> node.key
5. return BST_SEARCH( node.right, key)
End

inorder Traversal Algorithm:

Traverse_InOrder(Tree node) If node is not NULL Recursive_InOrder(node.left) print(node) Recursive_InOrder(node.right) End If