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

Stay updated with the latest technology trends while you're on the move - Join DataFlair's Telegram Channel

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 structure in java2. 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

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.

directed-graph

Undirected graph – An undirected graph is a set of objects or nodes which are connected together. It is a bidirectional graph.

undirected-graph1

ii. Weight

Weighted graph – A weighted graph is a graph in which every edge contains weight. It is also a special type of labelled graph.

weighted-graph

Unweighted graph –An unweighted graph is the one in which an edge doesnot have any weight. The graph is assumed to be unweighted.

unweighted graph

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.

Java Quiz

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)

Trie-data-structure

the output of this tree will be

Trie-data-structure-output

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.

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

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.

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 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.