6
\$\begingroup\$

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()
}
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

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
}

(see it live on ideone)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.