v

1
// Binary Search Tree example by @SleepyRoy
2

3
struct Empty {}
4

5
struct Node[T] {
6
	value T
7
	left  Tree[T]
8
	right Tree[T]
9
}
10

11
type Tree[T] = Empty | Node[T]
12

13
// return size(number of nodes) of BST
14
fn (tree Tree[T]) size[T]() int {
15
	return match tree {
16
		Empty { 0 }
17
		Node[T] { 1 + tree.left.size() + tree.right.size() }
18
	}
19
}
20

21
// insert a value to BST
22
fn (tree Tree[T]) insert[T](x T) Tree[T] {
23
	return match tree {
24
		Empty {
25
			Node[T]{x, tree, tree}
26
		}
27
		Node[T] {
28
			if x == tree.value {
29
				tree
30
			} else if x < tree.value {
31
				Node[T]{
32
					...tree
33
					left: tree.left.insert(x)
34
				}
35
			} else {
36
				Node[T]{
37
					...tree
38
					right: tree.right.insert(x)
39
				}
40
			}
41
		}
42
	}
43
}
44

45
// whether able to find a value in BST
46
fn (tree Tree[T]) search[T](x T) bool {
47
	return match tree {
48
		Empty {
49
			false
50
		}
51
		Node[T] {
52
			if x == tree.value {
53
				true
54
			} else if x < tree.value {
55
				tree.left.search(x)
56
			} else {
57
				tree.right.search(x)
58
			}
59
		}
60
	}
61
}
62

63
// find the minimal value of a BST
64
fn (tree Tree[T]) min[T]() T {
65
	return match tree {
66
		Empty {
67
			T(1e9)
68
		}
69
		Node[T] {
70
			if tree.value < tree.left.min() {
71
				tree.value
72
			} else {
73
				tree.left.min()
74
			}
75
		}
76
	}
77
}
78

79
// delete a value in BST (if nonexistent do nothing)
80
fn (tree Tree[T]) delete[T](x T) Tree[T] {
81
	return match tree {
82
		Empty {
83
			tree
84
		}
85
		Node[T] {
86
			if tree.left !is Empty && tree.right !is Empty {
87
				if x < tree.value {
88
					Node[T]{
89
						...tree
90
						left: tree.left.delete(x)
91
					}
92
				} else if x > tree.value {
93
					Node[T]{
94
						...tree
95
						right: tree.right.delete(x)
96
					}
97
				} else {
98
					Node[T]{
99
						...tree
100
						value: tree.right.min()
101
						right: tree.right.delete(tree.right.min())
102
					}
103
				}
104
			} else if tree.left !is Empty {
105
				if x == tree.value {
106
					tree.left
107
				} else {
108
					Node[T]{
109
						...tree
110
						left: tree.left.delete(x)
111
					}
112
				}
113
			} else {
114
				if x == tree.value {
115
					tree.right
116
				} else {
117
					Node[T]{
118
						...tree
119
						right: tree.right.delete(x)
120
					}
121
				}
122
			}
123
		}
124
	}
125
}
126

127
fn main() {
128
	mut tree := Tree[f64](Empty{})
129
	vals := [0.2, 0.0, 0.5, 0.3, 0.6, 0.8, 0.9, 1.0, 0.1, 0.4, 0.7]
130
	for i in vals {
131
		tree = tree.insert(i)
132
	}
133
	println('[1] after insertion tree size is ${tree.size()}') // 11
134
	del_vals := [-0.3, 0.0, 0.3, 0.6, 1.0, 1.5]
135
	for i in del_vals {
136
		tree = tree.delete(i)
137
	}
138
	print('[2] after deletion tree size is ${tree.size()}, ') // 7
139
	print('and these elements were deleted: ') // 0.0 0.3 0.6 1.0
140
	for i in vals {
141
		if !tree.search(i) {
142
			print('${i} ')
143
		}
144
	}
145
	println('')
146
}
147