If I had a chance to pick up and learn one random topic from Java Tutorial, I would choose Hierarchical Data Structure in Java. It is the most interesting and easy to learn the concept in the whole Java Tutorial Series.
In our previous article, we discussed the Linear Data Structures in Java and covered arrays, linked lists, stacks, and queues.
Continuing the Data Structure chain today, we are going to learn about the Hierarchical Data Structure in Java, such as Binary Tree, Binary Search Tree, Heap, and Hash data structure in detail with examples. These data structures are non-linear in nature.
But before that, it is recommended for you to take a quick revision of Linear Data Structure in Java to clear your basics with Techvidvan.
So, let’s start exploring some Hierarchical Data Structures in Java.
Hierarchical Data Structures in Java
Hierarchical Data Structures are non-linear data structures. These structures mainly represent data containing the hierarchical relationship between its elements, for example, records, trees, etc.
1. Binary Trees
A Binary Tree is a structure in which each node can have at most two children (child nodes). In a Binary tree, there exists a unique path from the root node to every other node.
The topmost node of a binary tree is called the root node or the parent node, and the nodes coming from the root node are called the child nodes.
A binary tree is either empty (which is called a null tree), or it consists of a root node along with the remaining two nodes, each being a binary tree itself.
Each node in a binary tree can have zero, one or maximum two successors or child nodes: left successor or child node and right successor or child node. A terminal node (that is, a node with n successor) is called a leaf node.
The figure below shows a sample binary tree:
Representation of Binary Trees
Each object in a binary tree is represented by a pointer on the topmost node along with the two references of the left node and the right node of the tree. If the nodes in the tree are empty, that is, leaf node, then it’s left and right references are NULL.
The parts of the binary tree are:
- Data
- Reference to the left child
- Reference for the right child
In a binary tree, there is a level number for each node. The Root node is at level 0, then each child having the level number one more than the level number of its parent node.
Traversing Binary Trees
The tree traversal is the process of going through a tree, in such a way it visits each node only once. There are three standard ways of traversing a binary tree which are:
- Preorder Traversal
- Inorder Traversal
- Postorder Traversal
Properties of Binary Trees:
- The number of children of a node is called the degree of the tree. A binary tree is a tree of degree 2, as each node can have a maximum of 2 children.
- The depth or height of a tree is the maximum number of nodes in a branch of it. It is always one more than the longest level number of the tree.
- The maximum number of nodes at level ‘L’ is 2^ (L-1)
- The maximum number of nodes for a tree with height ‘h’ is 2^ (h – 1)
- Time Complexity of Tree Traversal is O(n)
2. Binary Search Tree (BST)
Binary Search Tree is the other most important hierarchical data structure in Java. It is similar to the binary trees but has some additional properties like:
- The value of each node N of the right subtree is greater than every value in the left subtree.
- The value of each node N of the left subtree is smaller than every value in the right subtree.
- The left and right subtrees must be a Binary Search Tree.
The figure below shows a sample binary search tree:
The primary use of a binary search tree is searching applications like maps where the data enters frequently. Binary search trees provide quick searching and accessing options which are fast as compared to the linked lists.
Properties of Binary Search Trees:
- Search: O(h)
- Insertion: O(h)
- Deletion: O(h)
where ‘h’ is the height of the tree.
3. Binary Heap
A Binary Heap is another hierarchical data structure that is similar to a Complete Binary Tree with some additional properties. A complete binary tree is a binary tree with no nodes with only one child; except the deepest level. The common use of binary heaps is to implement priority queues.
The Binary heap has the following properties:
- A Binary Heap can be either a Min Heap or a Max Heap.
- In a Min Binary Heap, the data at the root must be minimum among all data present in Binary Heap.
- In a Max Binary Heap, the data at the root must be maximum among all data present in Binary Heap.
Example of Min Heap:
Example of Max Heap:
4. Hashing Function
A hashing function or a hash function is the Hierarchical data structure in Java. Hashing function converts a group of characters (called a key) into a small integer value of a certain length called a hash value or hash codes or hash.
In short, this hash function maps keys to some values. The hash value represents the original string of characters into some integer value and this value is normally smaller than the original value.
We use hashing functions for indexing and locating items in databases as it is easier to find the shorter hash value than the longer string. The main application of Hashing can is in encryption. We can also call this function as a message digest function or hashing algorithm.
HashMap: HashMap is a collection class in Java that stores the elements as key-value pairs.
Approaches to deal with hashing are:
4.1 Chaining
In this approach, each slot of the hash table contains a link that points to a singly-linked list containing key-value pairs with the same hash.
4.2 Open Addressing
In open addressing, we store all the elements in the hash table itself. Each table section contains either Nil or a record.
Summary
In this tutorial, we learned about the second part of Java Data Structures that is, Hierarchical data structure in Java programming language. By this tutorial we learned about Binary Tree, Binary Search Tree, Binary Heap and, Hashing Function in Java.
This article will surely help you understand the concept of the hierarchical data structures in Java.
Thank you for reading our article. If you have any queries related to Java Data Structure, do let us know with the help of the comment section below.
Happy Learning 🙂