![[SOLVED] Cspb 3155: assignment 10](https://assignmentchef.com/wp-content/uploads/2022/08/downloadzip.jpg)
5/5 – (1 vote)
Problem 1: Binary Search Trees in Scala
We will define an inductive datatype of binary search trees in scala to implement a map datatype that associates integer valued key with arbitrary data of type T. The following inductive definition will be used.
sealed trait Node
case object NilNode extends Node
case class TreeNode[T](key: Int, data: T, left: Node, right:Node) extends NodeA: Implement the Find Function
Implement the find function that given a key, yields the corresponding data if present or throws the KeyNotFound Exception.
case class KeyNotFound(key: Int) extends Exception
def find[T](tree: Node, key: Int): T = {
// YOUR CODE HERE
???
}val t1 = new TreeNode(5, "Hello", NilNode, NilNode)
val t2 = new TreeNode(20, "Right", NilNode, NilNode)
val root = new TreeNode(15, 10, t1, t2)
val data1:String = find(root, 20)
assert (data1 == "Right")
val root1 = new TreeNode(22, List(1), root, NilNode)
val data2:Int = find(root1, 15)
assert(data2 == 10)
val data3: List[Int] = find(root1, 22)
passed(10)B: Implement the insertion function
Insert a key key with data data. If key already exists, replace the old data associated with key with the given argument data.
def insertKey[T](tree: Node, key: Int, data:T): Node = {
// YOUR CODE HERE
???
}val t0 = NilNode
val t1 = insertKey(t0, 10, "10")
val t1_c :TreeNode[String] = t1.asInstanceOf[TreeNode[String]]
assert(t1_c.key == 10)
assert(t1_c.data == "10")
val t2 = insertKey(t1, 5, "5")
val t2_c: TreeNode[String] = t2.asInstanceOf[TreeNode[String]]
assert(t2_c.key == 10)
val t3 = insertKey(t2, 15, 15)
val t3_c = t3.asInstanceOf[TreeNode[Int]]
val t3_cc = t3_c.right.asInstanceOf[TreeNode[Int]]
assert (t3_cc.key == 15)
assert (t3_cc.data == 15)
val t4 = insertKey(t3, 25, "25")
val t5 = insertKey(t4, 18, "18")
val t6 = insertKey(t5, 10, 10)
assert(find(t6, 10) == 10)
assert(find(t6, 18) == "18")
assert(find(t6, 5) == "5")
passed(15)C: Implement the Deletion Function
To delete a node with a given key from a BST. Here is what you likely learned in your data structures class.
- First find the node you wish to delete.
- If it has no children or one child, deletion is easy — simply replace the node by Nil or by the subtree of the non-nil child.
- If it has both children, then find the “deletion successor” by going to right child and all the way to the left.
- Replace node by deletion successor key and delete that successor key from the right child.
However, this is not suitable for an immutable functional programming version. Complete the implementation of deletion below.
def deleteKey[T](tree: Node, key: Int):Node = tree match {
case TreeNode(k, d, left, right) if key < k => TreeNode(k, d, deleteKey(left, key), right)
case TreeNode(k, d, left, right) if key > k => {
// YOUR CODE HERE
???
}
case TreeNode(k, d, NilNode, NilNode) if key == k => {
// YOUR CODE HERE
???
}
// Left subtree is not nil but right node is Nil
case TreeNode(k, d, left, NilNode) if key == k => {
// YOUR CODE HERE
???
}
//Left subtree is nil but right is not nil
case TreeNode(k, d,NilNode, right) if key == k => {
// YOUR CODE HERE
???
}
//Both subtrees are not nil
case TreeNode(k, d, left, right) if key == k => {
//Both children are non-nil
// 1. First find/delete "leftmost" node from the right subtree
// 2. We have provided you the helper function below
// This function gets you the left most key and data and the new right subtree with
// the leftmost subtree deleted
def deleteLeftMostNodeInSubtree(tree: Node): (Int, T, Node) = {
tree match {
case TreeNode(k, d:T, NilNode, r) => (k, d, r)
case TreeNode(k, d:T, left, r) => {
val (k1, d1, left1) = deleteLeftMostNodeInSubtree(left)
(k1, d1, TreeNode(k, d, left1, r))
}
}
}
// YOUR CODE HERE
???
}
}val t0 = NilNode
val t1 = insertKey(t0, 10, "10")
val t1_c :TreeNode[String] = t1.asInstanceOf[TreeNode[String]]
assert(t1_c.key == 10)
assert(t1_c.data == "10")
val t2 = insertKey(t1, 5, "5")
val t2_c: TreeNode[String] = t2.asInstanceOf[TreeNode[String]]
assert(t2_c.key == 10)
val t3 = insertKey(t2, 15, 15)
val t3_c = t3.asInstanceOf[TreeNode[Int]]
val t3_cc = t3_c.right.asInstanceOf[TreeNode[Int]]
assert (t3_cc.key == 15)
assert (t3_cc.data == 15)
val t4 = insertKey(t3, 25, "25")
val t5 = insertKey(t4, 18, "18")
val t6 = insertKey(t5, 10, 10)
val t7 = deleteKey(t6, 25)
assert (find(t7, 10) == 10)
assert(find(t7, 18) == "18")
assert(find(t7, 5) == "5")
assert(find(t7, 15) == 15)
try{
find(t7, 25)
assert(false, "key 25 did not get deleted")
} catch {
case KeyNotFound(k) => assert(k == 25)
}
val t8: Node = deleteKey(t6, 10)
assert(find(t8, 18) == "18")
assert(find(t8, 5) == "5")
assert(find(t8, 15) == 15)
assert(find(t8, 25) == "25")
try{
find(t8, 10)
assert(false, "key 10 did not get deleted")
} catch {
case KeyNotFound(k) => assert(k == 10)
}
passed(15)
Reviews
There are no reviews yet.