Data Structures in Java – Graph, Trie, Segment Tree & Suffix Tree
1. Data Structure in Java – Objective
In the last two tutorials, we learned about linear data structures and hierarchal data structures. Here, we are going to learn about some other Data Structures in Java: Graph Data Structure in Java, Trie Data Structure in Java, Segment Tree and Suffix Tree with their example.
So, let us start Data Structure in Java Part 3.
In Part 3 of the overview of Data Structures in Java Programming Language, we will study about Graph Data Structure, Trie Data Structure, Segment Tree and suffix tree.
3. Graph Data Structure in Java
A graph data structure in Java has the following two components –
- A set of finite vertices which are called as nodes.
- An edge which has a finite set of ordered pair which is in the form (u, v). This set is called ordered because (u, v) is not the same as (v, u), this pair forms indices, and these indices can represent anything.
V -> Number of Vertices
N -> Number of Edges
a. Classification of Graph
Graph Data Structures in Java can be classified in many ways, two major ways by which classification can be done are–
Directed graph – A directed graph is a set of objects or nodes that are connected with each other, in which all the edges are directed from one vertex to another.
Undirected graph – An undirected graph is a set of objects or nodes which are connected together. It is a bidirectional graph.
Weighted graph – A weighted graph is a graph in which every edge contains weight. It is also a special type of labelled graph.
Unweighted graph –An unweighted graph is the one in which an edge doesnot have any weight. The graph is assumed to be unweighted.
Graph Data Structure Example-
A graph is used to represent the flow of computation. Talking about its applications Google maps use graph for the transportation system building. In facebook also the friend suggestion algorithm uses the theory of graphs. In the Operating System, allocation of resources is done with the help of a resource allocation graph in which every resource is considered as a vertex.
4. Trie Data Structure
A Trie Data Structures in Java is an effective structure to search for words in dictionaries, the search complexity is linear in Trie. It is much faster than Binary search tree as when we create BST, it should be proportional, which will need it to be M*Log N where M is the length of string which is maximum and N is the number of keys in Tree.
Insert time: O(M) where M is the length of the string.
Search time: O(M) where M is the length of the string.
Deletion time: O(M)
the output of this tree will be
5. Segment Tree
Segment Trees Data Structures in Java are used when there a lot of queries with a set of values, they are implemented using Java arrays. The queries can involve addition, subtraction, etc. and even updating the values.
Construction of segment tree: O(N)
Query: O(log N)
Update: O(log N)
Space: O(N) [Exact space = 2*N-1]
6. Suffix Tree
Suffix Tree Data Structures in Java is used to search for patterns in a text. It is a compressed trie which has all the suffixes of the given text as their keys and their positions as values. It has the fast implementation of string operations. It is also called as a position tree.
To create a suffix tree, we need to have trie of all suffixes, following are the steps to create a suffix tree –
- Generate suffix
- Consider all postfix as individual words and manufacture a packed trie.
Suffix Tree Example –
Used to discover all events of the example in a string. It is additionally used to locate the longest rehashed substring (when a test doesn’t change frequently), the longest regular substring and the longest palindrome in a string.
So, this was all about Data Structure in Java Tutorial. Hope you like our explanation.
Hence, in this Java tutorial, we learned about the various data structures in java: Graph data structure, trie data structure, segment tree, and suffix tree with their example.
See Also – Socket Programming in Java