-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinarySearchTree.sc
153 lines (131 loc) · 3.55 KB
/
BinarySearchTree.sc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//sealed trait Tree[+T]
//case object Leaf extends Tree[Nothing]
//case class Branch[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]
sealed trait Expr[A]
case class Value[A](v: A)
case class Sum[A](v: Value[A], v_1: Value[A],f: (A,A)=>A)
case class Neg[A](v: Value[A],f: A=>A)
sealed trait Tree[+T]
case object Leaf extends Tree[Nothing]
case class Branch[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]
def add[A]()
type BST[T] = (Tree[T], (T,T) => Boolean)
def insert[T](a: T, bst: BST[T]): BST[T] = {
val(tr, isLower) = bst
def insertTree(tree: Tree[T]): Tree[T] = tree match {
case Leaf => Branch(a, Leaf, Leaf)
case Branch(v,l,r) => if(v==a) tree else if(isLower(a, v)) Branch(v, insertTree(l), r) else Branch(v, l, insertTree(r))
}
(insertTree(tr), isLower)
}
def build[T](list: List[T],isLower: (T,T)=>Boolean): BST[T] = {
list.foldLeft((Leaf: Tree[T], isLower))((tree:BST[T], element)=>insert(element, tree))
}
def contains[T](bst: BST[T], a: T): Boolean = {
var found = false;
def iterate(tree: Tree[T]): Unit = tree match {
case Leaf =>
case Branch(v,l,r) => {
iterate(l)
if(a==v) found=true;
iterate(r)
}
}
iterate(bst._1)
found
}
def show[T](bst: BST[T]): Unit = {
def iterate(tree: Tree[T]): Unit = tree match {
case Leaf =>
case Branch(v,l,r) => {
iterate(l)
println(v)
iterate(r)
}
}
iterate(bst._1)
}
val tre2 = build(List(1,2,3,8,4), (a: Int, b: Int) => a<b)
var tre3: BST[Int] = (Leaf, (a: Int, b: Int) => a<b)
tre3 = insert(1, tre3)
tre3 = insert(2, tre3)
tre3 = insert(2, tre3)
tre3 = insert(3, tre3)
tre3 = insert(8, tre3)
tre3 = insert(4, tre3)
show(tre3)
show(tre2)
contains(tre3, 2)
contains(tre3, 11)
contains(tre2, 9)
contains(tre2, 3)
//object BSTTree{
// def isGreater(branch: Branch[Int], b: Int): Tree[Int] ={
// if(b>=branch.value) branch.right else branch.left
// }
// def insert(a: Int, tree: Tree[Int]): Tree[Int] = tree match {
// case Leaf => Branch(a, Leaf, Leaf)
// case Branch(v,l,r) => if(a>v) Branch(v, l, insert(a, r)) else if(a<v) Branch(v, insert(a,l), r) else tree
// }
// def apply[A](): Tree[A] = Leaf
//
//
// def show(tree: Tree[Int]): Unit = tree match {
// case Leaf =>
// case Branch(v, l, r) => {
// print(v)
// show(l)
// show(r)
//
// }
// }
// def contains(ele: Int, tree: Tree[Int]): Boolean = {
// var isFound = false;
// def helper(tr: Tree[Int]): Unit = tr match {
// case Leaf =>
// case Branch(v, l, r) => {
// if (v == ele) {print(isFound)
// if (!isFound) isFound = true
// print(isFound)
// }
// helper(l)
// helper(r)
// }
// }
// helper(tree)
// isFound
// }
//}
//
//
//var tree2: Tree[Int] = BSTTree()
//tree2 = BSTTree.insert(1,tree2)
//tree2 = BSTTree.insert(2,tree2)
//tree2 = BSTTree.insert(2,tree2)
//tree2 = BSTTree.insert(8,tree2)
//tree2 = BSTTree.insert(7,tree2)
//BSTTree.contains(7, tree2)
//
//BSTTree.show(tree2)
//List(1,2,3,4).foldRight(Leaf)((x: Int, branch: Branch[Int]) => {
// if (x >= branch.value)
// else
//
//}
//val BST = (tree: Tree[Int]) => {
// def isGreater(a: Int, b: Int): Boolean ={
// a>b
// }
// def insert[Int](t: Tree[Int], ele: Int): Unit = t match {
// case Leaf =>
// case Branch(value, l, r) => {
// if(isGreater(ele,value))
// }
// }
//}
//case class BST2(tree: Tree[Int], )
//def size[A](t: Tree[A]): Boolean = t match {
// case Leaf(_) =>
// case Branch(l, r) => 1 + size(l) + size(r)
//}
// whether first element is lower than second on