Forem: Ogundele Olumide

Data Structures: Binary Search Trees with Go

Ogundele Olumide — Mon, 21 Sep 2020 08:15:26 +0000

In continuation of this exciting quest to learn more about data structures and algorithms. I will love to talk about binary search trees which build on the knowledge last discussed on linked-list which is referenced from this book, you can find the post here.

Why Binary Search Trees?

There are some data structures that allow a fast search or flexible update, but not both. An unsorted, doubly-linked lists support insertion in constant time O(1) but the search took linear time O(n) in the worse case. Sorted arrays support binary search which helps lookup in logarithm time O(logn), but at the cost of linear-time update.

Binary Search Trees will allow us to have a fast search and update in logarithm time O(logn) but there is a caveat to this which will be explained later when we talk about balancing a binary search tree.

The arrangement and balancing of the tree is done in a way that the keys of nodes on the left subtrees are less than the keys on the right subtrees and this leads to the tree being sorted always.

Implementation of Binary Search Trees

To create a binary search tree, we need a linked list with 2 pointers per node.
The idea is that there is a left subtree and right subtree and the node is labeled with a key. I will implement the following operations on the binary search tree: Searching, Traversal, and Insertion.

The nodes of the tree have 1. left pointer 2. right pointer 3. optional parent pointer 4. data field, where we store values inserted. All the code and tests for this implementation can be found here on github.

To create a binary search tree, you will need to have a root where everything builds from, it can be empty or it can consist of a node together with 2 binary search trees called left and right subtrees which consist of nodes, a node (tree) which is the smallest unit and foundation of a binary search tree as shown below:

    // Tree is the basic structure or node in a binary search tree.
    type Tree struct {
        parent *Tree  // parent can be nil i.e Root tree
        left   *Tree  // left child or left subtree
        right  *Tree  // right child or right subtree
        Item   string // data held by the node
    }

The parent can be a tree but in the case of a rooted tree, it will be empty and the left and right can also be empty which indicates we are at the end of the tree. We will model a Dictionary (collection of sorted words in ascending order) using this data structure.

    // BinarySearchTree to store the words of a dictionary.
    type BinarySearchTree struct {
        Root *Tree
    }

Insertion

I have 2 different implementations for the insertion operation, the recursive and non-recursive approach.

Non-Recursive

This approach is more code and a bit easier to reason about. We will start going through the binary search tree from the root and then based on the item to be inserted, we have the following decision points and this also forms the concept behind the recursive approach:

If the root is empty, insert the item thereby creating a new tree, where parent, left and right subtree or children are nil.
If the item to be inserted is less than the current item in the node, we move to the left subtree and continue our search till we get to the end of the left-subtree i.e nil, then we inserted a new item there encapsulated as a new tree.
If the item to be inserted is greater than the current item in the node, repeat the above step but instead of moving to the left subtree, we move to the right subtree.

This is illustrated below:

    func (bt *BinarySearchTree) NormalInsert(item string) {
        if bt.Root == nil {
            bt.Root = &Tree{
                Item: item,
            }
            return
        }
        currentTree := bt.Root

    insertionLoop:
        for {
            switch {
            // go to the left subtree
            case item < currentTree.Item:
                if currentTree.left == nil { // at the end of the left subtrees
                    // attach the new node
                    currentTree.left = &Tree{
                        Item:   item,
                        parent: currentTree,
                    }
                    break insertionLoop
                } else {
                    currentTree = currentTree.left
                }
                break
            // go to the right subtree
            case item > currentTree.Item:
                if currentTree.right == nil { // at the end of the right subtree
                    // attach the new node
                    currentTree.right = &Tree{
                        Item:   item,
                        parent: currentTree,
                    }
                    break insertionLoop
                } else {
                    currentTree = currentTree.right
                }
                break
            default:
                break insertionLoop
            }
        }
    }

We needed a label on the loop because when we break in a switch statement, it breaks out of the switch and not the loop.

Recursive

Just as discussed above, this approach is less code but takes a little to reason about especially when you get to the point where you want to attach the new tree to its parent, it follows the same approach above.

    func (bt *BinarySearchTree) RecursiveInsert(currentTree **Tree, item string, parent *Tree) {
        // currentTree is a pointer to the memory location(also a pointer) where the current node tree
        // is stored. This is needed because, when we get to a tree that is empty and we need to insert
        // the new item, we'll need to replace the empty space (which is to hold a tree) with the new tree, this warrants having access to the location.
        // If you don't do this, your update will be detached from the main binary search tree.

        // when we have come to the end of the search.
        if *currentTree == nil {
            newTree := &Tree{
                Item:   item,
                left:   nil,
                right:  nil,
                parent: parent,
            }
            // Attach to its parent, by getting the memory location where the currentTree.
            *currentTree = newTree
            return
        }

        // Recursively search for where to put the item.
        if item < (*currentTree).Item { // diverge to the left subtree
            bt.RecursiveInsert(&(*currentTree).left, item, *currentTree)
        } else {
            bt.RecursiveInsert(&(*currentTree).right, item, *currentTree)
        }
    }

Attaching the new node to the tree takes constant time but the search operation that is performed before the node is attached uses a running time of O(h), h - the height of the tree

Note that the insertion here doesn’t guarantee a balanced search tree, this will be discussed in another post when I discuss the Red-Black Tree and Slay Tree which is guaranteed to be O(logn) in height and that applies for insertion, update, and deletion, the tree responds to mutation to make it close to being balanced to guarantee the height of the tree is always or close to O(log n).

What we have so far is a random binary search tree that is good too but if the insertion goes south (which we don’t have control over the values or items inserted by the user), we can end up in O(n) height for the tree.

Searching

It is important to label a binary search tree so that we can uniquely identify each tree using its identifier.

These are the steps to consider when performing this operation:

Start the search at the root of the tree
If the search has a key to be searched for;
Check if the key is greater or less than the key or identifier in the root, this will determine if we’ll go down the left child of the tree or the right.
Continue these steps recursively till you find the item or get to the end of the tree

The search algorithm runs in O(h) time, where h is the height of the binary search tree

Finding the minimum node in the tree comes with the understanding that, the leftmost subtree has the minimum item, and also for maximum, the rightmost subtree has the highest item in the tree. The smallest key must reside in the left subtree of the root since all keys in the left subtree have values less than that of the root and the largest key resides in the right subtrees since the keys in the right subtrees are higher than the root. These operations are illustrated below:

Search:

    // Search searches for an item, it expects to start from the Root.
    func (bt *BinarySearchTree) Search(item string) string {

        if result := bt.Root.Search(bt.Root, item); result != nil { // found!
            return result.Item
        }
        return ""
    }

Minimum:

    func (bt *BinarySearchTree) FindMinimum() *Tree {
        // start from the Root and move to the left subtrees
        minTree := bt.Root

        for minTree.left != nil {
            minTree = minTree.left
        }
        return minTree
    }

Maximum:

    // FindMaximum returns the largest or highest item item in the tree.
    func (bt *BinarySearchTree) FindMaximum() *Tree {
        // start from the Root and move right wards
        maxTree := bt.Root

        for maxTree.right != nil {
            maxTree = maxTree.right
        }
        return maxTree
    }

Traversal

It is about visiting all the nodes in a rooted binary tree, this is a very important part of many algorithms. This is also a foundation for traversing the nodes and edges in a graph.

It comes with the understanding that the elements in the binary search tree are already sorted since the smallest keys are on the left of the root and the largest keys are on the right of the root tree.

This is achieved by using a recursive approach visiting the nodes of the tree, processing the left trees, processing the item on that tree, and also visiting the right subtrees recursively. The order in which this operation is done leads to 1. In-order traversal 2. Pre-order traversal 3. Post-order traversal

In-order traversal:

Traverse the left subtrees, process the item and traverse the right subtrees, the index of the recursion will be when we reach the leaf or node with no children i.e left and right tree are nil.

Pre-order traversal:

Process the item in the tree first, then Traverse the left subtrees and traverse the right subtrees

Post-order traversal:

Traverse the left subtrees first, then traverse the right subtrees and then process the item in the tree.

Pre-order and Post-order traversal comes in handy when the binary search tree represents an arithmetic expression or a logical expression where the order of operation is very important.

The running time of traversal is linear O(n) because each item is visited once.

Below is the illustration of In-order traversal, you can get the implementation of Pre-order and Post-order on github:

In-order Traversal:

    // InOrderTraversal traverse in the order [smallest ... largest] [allLeft ... allRight]
    func (bt *BinarySearchTree) InOrderTraversal(t *Tree, processItem func (string)) {
        if t != nil {
            bt.InOrderTraversal(t.left, processItem)
            // process the item in the tree using the power of closure
            processItem(t.Item)
            bt.InOrderTraversal(t.right, processItem)
        }
}

Final Thoughts

Picking the wrong data structure for the job can be disastrous in terms of performance. Identifying the very best data structure is usually not as critical because there can be several choices that perform similarly. - Steven S. Skiena

The problem you are trying to solve, will and should always inform the kind of data structure you use. It is a learning journey as always, I will be glad to hear from you if you have question(s) or feedback, have fun!

Data Structures: Singly-Linked List with Go

Ogundele Olumide — Tue, 04 Aug 2020 08:07:59 +0000

From my learning about Operating Systems, diving into the source code of Linux, seeing the data structures for p_threads, mutex, sockets, etc., I have grown to appreciate data structures and algorithms, they are combined to build powerful computer systems and tools. So, I want to share my learning as I resume my study on data structures and algorithms again after a while.

The majority of my learnings so far are attributed to this book and there are some excerpts from it too.

Data structures can be classified as contiguous or linked depending on if it is based on arrays or pointers. I think it is safe to see data structures as a way data or values are laid into the memory.

Contiguously-allocated Structures are composed of single slabs or blocks of memory, examples of data structures that are based on this are arrays, heaps, hash tables, etc.

Linked Data Structures are composed of distinct chunks of memory, bound together by pointers. They include lists, trees, graphs etc.

Pointers and Linked Structures

Pointers are the connections that hold the pieces of linked structures together.
Pointers represents the address of a location in memory. So a variable storing a pointer to a data item can provide more freedom than having a copy of the given data stored in the variable. This is what happens in Go when you pass a value to a function by reference instead of passing a copy of the value.
A cell phone number can be thought of as a pointer to the owner of the phone as they move about on planet earth.
Much of the spaces used in linked-data structures has to be devoted to the pointers than the data
Finally, we need a pointer to the head of the structure to know where to access it.

There is a small singly-linked list data structure created in Go and the basic operations supported are searching, insertions, and deletions as shown below:

The complete code with the tests can be found on github

I will be creating a linked data structure that stores an item but in this case, a name, the elements of the linked-list will be encapsulated in a node where we can hold the item and also the pointer to the next node that is linked to it, see the code below;

    type nameNode struct {
        name string    // item
        next *nameNode // pointer to the next node it is linked to
    }

We need to have the main list that houses all the nodes and it will have just one attribute, head, this will help us to know the start of the list.

    type nameList struct {
    head *nameNode // the starting point in the list
    }

Searching a List

It can be done iteratively or recursively, we take the item being searched for and iteratively or recursively move through the pointer till we get to the end which will be nil or empty in whichever way you structure your element or node. This is illustrated below:

    func (l *nameList) searchList(name string) *nameNode {
        // starting from the head of the list
        // searchNode is a recursive function
        return searchNode(l.head, name)
    }

Insertion into a List

It is easily done at the beginning of the list, no need to traverse the list.
What is just needed is to have a variable to store the head of the pointer.
When a new insertion is needed, swap the head for the new insertion and point the next node of the new insertion to the previous head.
Update the head of the list to the new node.

This is illustrated below:

    func (l *nameList) insertList(name string) {
        newName := &nameNode{name, nil}
        if l.head == nil {
            l.head = newName
            return
        }
        previousHeader := l.head
        // link with the previous head and insert at the head
        newName.next = previousHeader
        l.head = newName
    }

Deletion from a List

It is a little tricky if it is a singly-linked-list compared to doubly-linked-list.

Search for the node or element.
Create another operation to return the pointer to the predecessor node before the item to be deleted.
Link the predecessor node with the node after the found node i.e make the predecessor pointer, point to the node after the found node which was gotten through search. That way, we detach the node we want to delete from the linked-list, and during house-keeping by the system or garbage collection, it will be removed from the memory and whatever memory address it was allocated will be freed.

This is shown below:

    func (l *nameList) deleteList(name string) {
        // search if the node exists
        foundNode := l.searchList(name)

        if foundNode != nil {
            // get the nodes before name
            nodeBefore := nodesBeforeItem(l.head, name)
            if nodeBefore != nil {
                nodeBefore.next = foundNode.next
            } else { // it means the foundNode is the head node
                l.head = foundNode.next
            }
        }
    }

Final Thoughts

Insertions and deletions are easier in a linked list compared to array lists.
When you have large records or data, moving pointers is easier and faster than moving the items themselves which might be huge, a good point to this is when you pass values to function in Go by reference and not by copying the value.
Linked structures require extra space for storing pointers, which means that apart from the data we want, pointers take up memory space too, so it might increase the data size.
The convenience of random access to items we get from array lists is not in linked-list, we have to do a traversal.
Also due to the way the memory is laid out in the computer, some optimizations have also being implemented by the operating system which allows fast data access and reduces CPU cycles, memory cache was created for better performance, array allows better memory locality which the memory cache takes advantage of because the block of memory used is allocated in a continuous way, compared to pointer structure that is composed of small memory chunks linked together which will result in jumping around in the memory and also lead to losing the memory locality. In other words, if you’ll be doing a lot of searching, compared to insertion and deletion, maybe you should think of the benefit of an array list.

A final thing to think about is that, Array and Lists are recursive objects, you can always remove the first element of a list and you have smaller elements, likewise, you can remove some constant number of elements from an array till you get to an empty array, which is a good base index when doing stuff the recursive way.

I will be glad to hear from you if you have a question(s) or feedback, have fun!

Building a multipurpose CLI tool with Cobra and Go

Ogundele Olumide — Tue, 04 Aug 2020 03:18:48 +0000

I have always loved how Unix/Linux tools work when using them in the terminal. I had reasons to build a CLI tool with Python which I used to start up any project with Git initialized some time ago ws, it doesn't do much. Recently, I got the inspiration to build a multipurpose unit-converter CLI tool taking the inspiration from Google's unit converter, I had to move away from my terminal often to do some conversions and I thought if I had a tool that will avoid leaving the terminal and maintain my focus, this led to creating uconv.

A command-line interface (CLI) processes commands to a computer program in the form of lines of text. The program which handles the interface is called a command-line interpreter or command-line processor. Operating systems implement a command-line interface in a shell for interactive access to operating system functions or services. Such access was primarily provided to users by computer terminals starting in the mid-1960s, and continued to be used throughout the 1970s and 1980s till today on Windows, Unix systems and personal computer systems.

Source Wikipedia

Uconv is also a CLI tool written with Go and Cobra, the full repository can be found here.

Design of uconv

I want to be able to create a user experience of uconv by doing the following in the terminal

    uconv temperature 100 --from=c --to=k

and get the following output

    temperature: 30°C ==> 303K`

The anatomy of the command is this

[command] [subcommand] [argument] --flags

Getting Started

Install Go from here

create a directory called whatever name you want, I'll use - uconv and open it with your code editor or IDE, I'll use VS Code

    mkdir uconv && cd uconv && code .

Initialise go modules for ease of package or dependency management in your project, it will create a go.mod and go.sum file when you start installing packages.

    go mod init

Install Cobra into the project

go get -u github.com/spf13/cobra/cobra

If you follow the usage guideline of Cobra, you'll find that you can bootstrap your project with it

cobra init --pkg-name <your project directory> like github.com/Lumexralph/uconv

When the files and directories are created, we can proceed by working on the base command cmd/root.go file to look like this

// rootCmd represents the base command when called without any subcommands
var rootCmd = &cobra.Command{
    Use:   "uconv",
    Short: "A multi-purpose unit converter",
    Long: `uconv is a CLI tool that helps you convert a value from one unit to another
    It can be used for temperature, weight, area, length, currency`,
}

// Execute adds all child commands to the root command and sets flags appropriately.
// This is called by main.main(). It only needs to happen once to the rootCmd.
func Execute() {
    if err := rootCmd.Execute(); err != nil {
        fmt.Println(err)
        os.Exit(1)
    }
}

When you're done, run the command to install the package as an executable in your local environment

    go install .

If all goes fine, you should be able to be able to use "uconv" in the terminal like you do with ls, pwd, grep etc... You can try it out, you should get something similar to this output, it might not be exact

    uconv is a CLI tool that helps you convert a value from one unit to another
        It can be used for temperature, weight, area, length, currency

    Usage:
    uconv [command]

    Available Commands:
    help        Help about any command
    length      Convert length for different units
    temperature Convert temperature for different units

    Flags:
        --config string   config file (default is $HOME/.uconv.yaml)
    -h, --help            help for uconv

    Use "uconv [command] --help" for more information about a command.

The final interesting part is creating the temperature sub-command, add another file called whatever name you want, I will use temperature.go in the cmd directory.

Create your flags and add it it to the sub-command which in our case is temperature packaged as tempCmd

     var tempTo, tempFrom string

    // special function that gets executed when the app is being compiled,
    func init() {
        // create your flags --from and --to or -f or -t
        tempCmd.Flags().StringVarP(&tempFrom, "from", "f", "c", "the unit to convert from")
        tempCmd.Flags().StringVarP(&tempTo, "to", "t", "f", "the unit to convert to")

        // add the temperature command to the the root command
        rootCmd.AddCommand(tempCmd)
    }

We have the tempCmd created below, it follows the same pattern as the rootCommand.

    var tempCmd = &cobra.Command{
    Use:   "temperature",
    Short: "Convert temperature for different units",
    Long: `temperature is a sub-command for uconv (unit converter).

    It helps to convert temperature from one unit to another, Kelvin - k,
    Fahrenheit - f and Celsius - c.

    If no flags are specified, it converts Celsius - c to Fahrenheit - f by default.

    Usage:
        uconv temperature 45
        uconv temperature 45 --from f --to c
        uconv temperature 45 -f f -t c
    `,
    Args: cobra.ExactArgs(1),
    Run:  executeTemperatureCmd,
    }

Use: "temperature" is the name of my sub-command to be able to achieve this

uconv temperature

Short: "Convert temperature for different units", is the short description you get when you typed just uconv in the terminal. While Long is the description of what the command does when you type the following

uconv temperature --h or -h

Args: cobra.ExactArgs(1), was used because I only wanted just one value or argument provided since I just want to convert one value to another value, and the best part for me is where the logic happens

Run: executeTemperatureCmd, this will have a function with the required signature by Cobra, it will get run to respond to the temperature sub-command and since function is a first class citizen in Go, it can be passed as value like I did below.

This is the function definition below

// executeTemperatureCmd - handles the temperature commands with respective flags
func executeTemperatureCmd(cmd *cobra.Command, args []string) {
    // convert the string to int
    arg, err := strconv.ParseInt(args[0], 10, 64)
    if err != nil {
        fmt.Println(err)
        return
    }

    switch {
    case tempFrom == "c" && tempTo == "f":
        fmt.Printf("temperature: %d°C ==> %d°F\n", arg, celsiusToFahrenheit(arg))
    case tempFrom == "f" && tempTo == "c":
        fmt.Printf("temperature: %d°F ==> %d°C\n", arg, fahrenheitToCelsius(arg))
    case tempFrom == "c" && tempTo == "k":
        fmt.Printf("temperature: %d°C ==> %dK\n", arg, celsiusToKelvin(arg))
    case tempFrom == "f" && tempTo == "k":
        fmt.Printf("temperature: %d°F ==> %dK\n", arg, fahrenheitToKelvin(arg))
    case tempFrom == "k" && tempTo == "c":
        fmt.Printf("temperature: %dK ==> %d°C\n", arg, kelvinToCelsius(arg))
    case tempFrom == "k" && tempTo == "f":
        fmt.Printf("temperature: %dK ==> %d°F\n", arg, kelvinToFahrenheit(arg))
    case tempFrom == tempTo:
        fmt.Printf("temperature: %d%s\n", arg, tempTo)
    }
}

// celsiusToFahrenheit - converts Celsius to Fahrenheit
func celsiusToFahrenheit(data int64) int64 {
    return (data * 9 / 5) + 32
}

// celsiusToKelvin - converts Celsius to Kelvin
func celsiusToKelvin(data int64) int64 {
    return data + 273
}

// fahrenheitToCelsius - converts Fahrenheit to Celsius
func fahrenheitToCelsius(data int64) int64 {
    return (data - 32) * 5 / 9
}

// fahrenheitToKelvin - converts Fahrenheit to Kelvin
func fahrenheitToKelvin(data int64) int64 {
    return (data-32)*5/9 + 273
}

// kelvinToCelsius - converts Kelvin to Celsius
func kelvinToCelsius(data int64) int64 {
    return data - 273
}

// kelvinToFahrenheit - converts Kelvin to Fahrenheit
func kelvinToFahrenheit(data int64) int64 {
    return (data-273)*9/5 + 32
}

If you are able to get this far, you can recreate it for other sub-commands you might have. Please ensure to consult the Cobra's guidelines if you want more to your CLI tool and I will be glad to hear from you if you have any question or feedback, have fun!

Before I go, here is a cool trick I do when I want to start a new project with VSCode, I created an alias using a function like this;

 alias np='function _newp(){ mkdir $1 && cd $1 && code .; };_newp'

call the new command-line alias like this

 np uconv