Non-Linear Data Structures

Non-linear data structures are used in cryptography and other areas. A non-linear data structure is an arrangement in which an element is connected to many elements. These structures use memory quickly and efficiently. Free contiguous memory is not required for adding new elements.

The length of the data structures is not important before adding new elements. A non-linear data structure has multiple levels and a linear one has a single level. The values of the elements are not organized in a non-linear data structure. The data elements in a non-linear data structure cannot be iterated in one step. The implementation of these data structures is complicated.

Tree types such as binary search trees, treaps, and symbol tables are explained in this chapter.

This chapter covers the following non-linear data structures:

• Trees
• Tables
• Containers
• Hash functions...

Technical requirements

Install Go version 1.10 from https://golang.org/doc/install for your OS.

The GitHub URL for the code in this chapter is as follows: https://github.com/PacktPublishing/Learn-Data-Structures-and-Algorithms-with-Golang/tree/master/Chapter04.

Trees

A tree is a non-linear data structure. Trees are used for search and other use cases. A binary tree has nodes that have a maximum of two children. A binary search tree consists of nodes where the property values of the left node are less than the property values of the right node. The root node is at level zero of a tree. Each child node could be a leaf.

Trees and binary trees were introduced in Chapter 1, Data Structures and Algorithms, while we were discussing logarithmic complexity. Let's take a closer look at them in the next section.

Binary search tree

A binary search tree is a data structure that allows for the quick lookup, addition, and removal of elements. It stores the keys in a sorted order to enable...

Tables

As we already know, tables are used in data management and other areas. A table has a name and a header with the column names. Let's take a look at the different classes in tables such as the Table class, the Row class, the Column class, and the PrintTable method in the following sections.

For this section, please refer to the table.go file.

The Table class

A Table class has an array of rows and column names. The table's Name is a string property in the struct class, as shown here:

// Table Class
type Table struct {
    Rows []Row
    Name string
    ColumnNames []string
}

The Row class

...

Symbol tables

A symbol table is present in memory during the program translation process. It can be present in program binaries. A symbol table contains the symbol's name, location, and address. In Go, the gosym package implements access to the Go symbol and line number tables. Go binaries generated by the GC compilers have the symbol and line number tables. A line table is a data structure that maps program counters to line numbers.

Containers

The containers package provides access to the heap, list, and ring functionalities in Go. Containers are used in social networks, knowledge graphs, and other areas. Containers are lists, maps, slices, channels, heaps, queues, and treaps. Lists were introduced in Chapter 1, Data Structures and Algorithms. Maps and slices are built-in containers in Go. Channels in Go are called queues. A heap is a tree data structure. This data structure satisfies the heap property. A queue is modeled as a heap in Chapter 3, Linear Data Structures. A treap is a mix of a tree and a heap. It is a binary tree with keys and values and a heap that maintains priorities.

A ring is called a circular linked list and is presented in the next section. For this section, please refer to the circular_list.go file.

...

The hash functions

Hash functions are used in cryptography and other areas. These data structures are presented with code examples related to cryptography. There are two ways to implement a hash function in Go: with crc32 or sha256. Marshaling (changing the string to an encoded form) saves the internal state, which is used for other purposes later. A BinaryMarshaler (converting the string into binary form) example is explained in this section:

//main package has examples shown
// in Hands-On Data Structures and algorithms with Go book
package main
// importing bytes, crpto/sha256, encoding, fmt and log package
import (
 "bytes"
 "crypto/sha256"
 "encoding"
 "fmt"
 "log"
 "hash"
)

The main method creates a binary marshaled hash of two example strings. The hashes of the two strings are printed. The sum of the first hash is compared...

Summary

This chapter covered trees, binary search trees, and AVL trees. Treap, B-trees, and B+ trees were explained briefly. Operations such as insertion, deletion, and updating elements in trees were shown with various code examples. Tables, containers, and hash functions were presented in the last section. The complexity in time and space for operations such as insertion, deletion, and search were explained in each section.

In the next chapter, homogeneous data structures such as two-dimensional and multi- dimensional arrays will be covered.

Questions

1. Can you give an example where you can use a binary search tree?
2. Which method is used to search for an element in a binary search tree?
3. Which techniques are used to adjust the balance in an AVL tree?
4. What is a symbol table?

5. Which class and method are called to generate a binary marshaled hash on the hash class?
6. Which container in Go is used to model a circular linked list?
7. How do you create a JSON (indented) from a tree structure? Which class and method are used?
8. How do you compare the sum of hashes?
9. What is the balance factor in an AVL tree?
10. How do you identify a row and column in a table?

Further reading

The following books are recommended if you want to know more about trees, binary search trees, and AVL trees:

• Design Patterns, by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
• Introduction to Algorithms – Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• Data structures and Algorithms: An Easy Introduction, by Rudolph Russell