I recently got interested in Go and wrote a database server which uses a binary tree for data storage for fun. As I have no prior experience in Go, I'd like to gather a bit feedback on my code and would like to know how I can improve/optimize it.
File: BinaryTree.go
package BinaryTree
//import "fmt"
type SearchTree struct {
value *int
left, right *SearchTree
}
func (r SearchTree) getNode(i int) *SearchTree {
if r.value != nil && *r.value == i {
return &r
}
if r.left != nil {
ref := r.left.getNode(i)
if ref != nil {
return ref
}
}
if r.right != nil {
ref := r.right.getNode(i)
if ref != nil {
return ref
}
}
return nil
}
func (r SearchTree) Contains(n int) bool {
node := r.getNode(n)
return node != nil
}
func (r *SearchTree) Add(n int) {
pointer := r
for {
if pointer.value == nil {
pointer.value = &n
return
}
if *pointer.value == n {
return
} else if *pointer.value < n {
if pointer.left != nil {
pointer = pointer.left
} else {
pointer.left = &SearchTree{&n, nil, nil}
return
}
} else {
if pointer.right != nil {
pointer = pointer.right
} else {
pointer.right = &SearchTree{&n, nil, nil}
return
}
}
}
}
File: server.go
package main
import (
"fmt"
"net"
"log"
"BinaryTree"
"strconv"
)
var data BinaryTree.SearchTree
func generateAddr() *net.TCPAddr {
addr, err := net.ResolveTCPAddr("tcp", "localhost:19800")
if err != nil {
log.Fatal(err)
}
return addr
}
func handleConnection(con net.Conn) {
fmt.Println("handling connection")
buffer := make([]byte, 256)
for {
numBytes, err := con.Read(buffer)
if err != nil {
con.Close()
return
}
cmdTxt := string(buffer[:numBytes])
n, err := strconv.Atoi(cmdTxt[1:numBytes])
if err == nil {
fmt.Println(n)
switch (cmdTxt[0]) {
case 'g':
if data.Contains(n) {
con.Write([]byte{6})
} else {
con.Write([]byte{25})
}
case 's':
data.Add(n)
con.Write([]byte{6})
}
}
}
}
func startServer() {
ln, err := net.ListenTCP("tcp", generateAddr())
if err != nil {
log.Fatal(err)
}
for {
fmt.Println("wait for connection")
conn, err := ln.Accept()
if err == nil {
go handleConnection(conn)
}
}
}
func main() {
startServer()
}
1 Answer 1
This is a review of your binary tree implementation. I suppose it works, and it doesn't violate any major Go idioms. However, your algorithm for getNode sucks (\$O(n)\$ complexity), and there are a few minor WTFs.
I fail to understand why your SearchTree struct contains a value *int. Your design has no way for a user to get the value out of the tree, and changing the value would destroy the sorting. All you ever do is get a pointer to an argument (which was passed by value...), and then do annoying if value != nil tests. All of that is unnecessary once you use a simple value int.
As mentioned above, your getNode() is weird: Unless the current node contains the value, you recurse into both the left and right subtree. Since you insert the values in a sorted order, we can use the binary tree as an actual binary tree. The function then simplifies to:
func (node *SearchTree) getNode(i int) *SearchTree {
if node.value < i {
if node.left == nil {
return nil
}
return node.left.getNode(i)
}
else if i < node.value {
if node.right == nil {
return nil
}
return node.right.getNode(i)
}
else {
return node
}
}
I also renamed the receiver argument from r to the less cryptic node, and changed the receiver type to *SearchTree. Previously, your function took a tree by value (i.e. copy), then returned a pointer to that copy, which appears to be a bit backwards.
Actually, we can use the same getNode() function for both search and insertion with a few variations. To do this, we return a pointer to the .left or .right entry, which is itself a pointer. We guarantee that the returned pointer will never be nil, and that it will be a pointer to nil if no element was found. Only if it points to nil will that pointer will be writable.
func (node *SearchTree) getNode(i int) **SearchTree {
if node.value < i {
if node.left == nil {
return &node.left
}
return node.left.getNode(i)
} else if i < node.value {
if node.right == nil {
return &node.right
}
return node.right.getNode(i)
}
return &node // not nil, not writable
}
func (node *SearchTree) Contains(n int) bool {
return *(node.getNode(n)) != nil
}
// returns true if the tree was mutated as a result,
// and false if the number was already present
func (node *SearchTree) Add(n int) bool {
target := node.getNode(n)
if *target == nil {
*target = &SearchTree{n, nil, nil}
return true
}
return false
}
This double pointer may seem a bit jarring since we're already using one level of pointers. However, we want a pointer to that field in the parent node, which merely happens to contain a pointer type itself.
There is a remaining problem with your tree. Right now, declaring a variable of type SearchTree will assign a default value, which is a struct with all members assigned their default values – nil for pointers and 0 for integers. However, this means that the following code will always evaluate to true:
val empty SearchTree
empty.Contains(0) // true, oops!
The solution is to create a wrapper type containing a pointer to the search tree for the public interface. What was previously called SearchTree, we rename to node, and create type BinaryTree struct { root *node }. While not necessary, I'd also provide an explicit constructor NewBinaryTree().
This is the code I ended up with:
type BinaryTree struct {
root *node
}
func NewBinaryTree() *BinaryTree {
return &BinaryTree { nil }
}
type node struct {
value int
left, right *node
}
func (node *node) getNode(i int) **node {
if node.value < i {
if node.left == nil {
return &node.left
}
return node.left.getNode(i)
} else if i < node.value {
if node.right == nil {
return &node.right
}
return node.right.getNode(i)
}
return &node // not nil, not writable
}
func (tree *BinaryTree) Contains(n int) bool {
root := tree.root
if root == nil {
return false
}
return *(root.getNode(n)) != nil
}
// returns true if the tree was mutated as a result,
// and false if the number was already present
func (tree *BinaryTree) Add(n int) bool {
if tree.root == nil {
tree.root = &node{n, nil, nil}
return true
}
target := tree.root.getNode(n)
if *target == nil {
*target = &node{n, nil, nil}
return true
}
return false
}