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.

Data Structures in Java

Data Structures in Java – Graph, Trie, Segment Tree & Suffix Tree

2. What are Data Structures in Java?

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

Do you know the Difference Between Abstract Class and Interface in Java

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–

i. Direction

Undirected graph – In this graph, all edges bidirectional.
Directed graph – In this graph all the edges are unidirectional.

ii. Weight

Weighted graph – In this type graph weight is associated with the edges.
Unweighted graph – In this type of graph weight is not associated with the edges.

Time Complexities in case of –

  •  Adjacency Matrix 

Traversal: (By BFS or DFS) O(V^2)
Space: O(V^2)

  •  Adjacency List 

Traversal: (By BFS or DFS) O(ElogV)
Space: O(V+E)

Read about Interface in Java with Example program

Graph Data Structure Example- 

The most well-known case of the graph data structure in Java is to discover the briefest way in any system. Utilized as a part of Google maps or Bing. Another normal utilize use of graph is interpersonal interaction sites where the companion recommendation relies upon the number of middle of the road proposals and different things.

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.

Let’s study about Java Sting in detail

We can search the key in O(M) time, the hashing in Trie provides us O(N) on average for a word search.

The other name for Trie is radix tree or prefix tree.

The only drawback to Trie is that it takes a lot of space but it also provides no complexity and collisions. It also provides a prefix search.

Trie Data Structure Example –

The structure can be defined as follows :
struct trie_node

{
int value; /* Used to mark leaf nodes */
trie_node_t *children[ALPHABET_SIZE];
};

root
/   \    \
t   a     b
|   |     |
h   n     y
|   |  \  |
e   s  y  e
/  |   |
i  r   w
|  |   |
r  e   e
|
r

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)

Let’s read about Encapsulation in Java

Example –

The most widely recognized utilization of Trie Data Structure is to actualize word references because of prefix seek ability. Tries are likewise appropriate for executing inexact coordinating calculations, incorporating those utilized as a part of spell checking. It is likewise utilized for seeking Contact from Mobile Contact rundown OR Phone Directory.

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 sum, subtraction, etc. and even updating of the values.

Data Structures in Java - Segment Tree

Data Structures in Java – Segment Tree

Construction of segment tree: O(N)
Query: O(log N)
Update: O(log N)
Space: O(N) [Exact space = 2*N-1]

Have a look at Decision Making in Java

6. Suffix Tree

A Suffix Tree Data Structures in Java is used to search for patterns in a text. The main idea behind this is to preprocess the content with the goal that hunt task should be possible in time direct as far as example length. The example looking calculations like KMP, Z, and so forth require some investment relative to content length. This is extremely an extraordinary change since a length of example is for the most part considerably littler than content.

Data Structures in Java - Suffix Tree

Data Structures in Java – Suffix 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.

Follow this link to know about Method Overriding in Java

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.

7. Conclusion

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

For reference

Leave a Reply

Your email address will not be published. Required fields are marked *