In this post, we introduce three popular data structures Binary tree, Graph and Trie. The link of their implementations are listed below. You can get the source code of add, delete, search and traverse methods as foundations to build your own.
Table of Content
1. Binary tree
A tree is a hierarchical data structure. It consists of nodes with a root node at the top and subtree of children nodes. The nodes are connected by edges. A binary tree has at most two children, we name them left child and right child.
There are many variations of binary tree, such as binary search tree, complete binary tree, balanced binary tree etc. Each one has unique characteristics and applications. The well known one is binary search tree.
A binary search tree is an ordered binary tree. The left subtree contains nodes whose keys are less than the node’s key value, while the right subtree contains nodes whose keys are greater than or equal to the node’s key value. Moreover, both subtrees are also binary search trees. A binary search tree can retrieve data efficiently.
A graph is a data structure that consists of a set of nodes connected by edges. Nodes (aka vertices) store data. Edges are used to connect nodes. A Tree is one kind of graph in which there is no cycle.
In a directed graph, all of the edges represent a one-way relationship. In an undirected graph, all edges are bi-directional. If the edges in the graph have weights (represent costs or distances), the graph is a weighted graph. If the edges do not have weights, the graph is an unweighted graph.
In Graph, there are two search methods – Depth first search (DFS) and Breadth first search(BFS). They are wildly used in strings, trees and graphs searches. Depth First Search starts from the source node, and explores the adjacent nodes as far as possible before backtracking. DFS is usually implemented with recursion or stack. Breath First Search starts from the source node, and explores all its adjacent nodes before going to the next level adjacent nodes. BFS is usually implemented with Queue.
A trie is a tree-like data structure in which every node stores a character. After building the trie, strings or substrings can be retrieved by traversing down a path of the trie.
Trie node is similar to tree node or graph node. It contains the information of the node and its children. Additionally, there is a boolean variable to indicate whether the node is the end of the string.
Trie has many variations as well. Prefix tree is a compressed trie for prefix. It stores combined string instead of a char in the node. Suffix trie is a trie that stores all suffixes of a string. Suffix Tree is a compressed trie for all suffixes of the given string. It stores combined string instead of a char in the node.