Your Tree Or Mine
Create a Go facility to implement a simple set of integers based on
a plain BST.
Follow the code layout in the
linked
list example to create a file which can be compiled together with
any main that wants to use it. Your code should provide the following
for use by the client:
var is IntSet
This declares is (or any other name) as a set of integers. The name
IntSet is required.
is.contains(i)
Return true if the set is contains i, false if not.
is.add(i)
Add the integer i to the set is. Of course, if i is
already present, is does not change. The function also should
return a boolen value that is true if add changed the set, or
false if it did not. (The value returned is the inverse of what
contains would have returned before add was called.)
is.remove(i)
Remove the integer i from the set is if present. Like add,
remove returns true if it actually changes the set, and false
if it does not.
is.contents()
This method returns type []int, which is a slice that contains the
contents of the set, in ascending order.
You may create any number
additional methods or functions as helpers, as needed.
Implementation using a binary search tree is a requirement.
A plain BST that can become unbalanced is quite sufficient. If you just want
to do five times the work to create some kind of
balanced one, and you can make it
work, more power to you.
Here is a trival driver:
package main
import "fmt"
func main() {
var is IntSet
is.add(17)
is.add(20)
fmt.Println(is.contains(10),is.contains(17),is.contains(20),
is.contains(25))
fmt.Println(is.contents())
is.remove(20)
is.remove(30)
fmt.Println(is.contains(10),is.contains(17),is.contains(20),
is.contains(25))
fmt.Println(is.contents())
}
It outputs:
false true true false
[17 20]
false true false false
[17]
Hints
Create a struct for the tree node, and you probably want
IntSet to be a struct also, even if it contains only a
single field. Create the other methods in Go style, with
a receiver type
*IntSet.
You might want to create a helper function to search for an item
in the tree, which can be used to support several of these methods.
You will almost certainly want to use recursion to build
contents,
since it has to perform a traversal. You will want to allocate an
empty slice with
new, then use a recursive function to append each
item from the tree using an in-order traversal. I did not use recursion
elsewhere in my solution, but you are certainly welcome. It's sort of
a natural with trees.
Submission
When your program works, is well-commented, and nicely indented,
submit over the web
here.