Hierarchical Data Structure in Java – Binary Tree, Binary Search Tree,Heap
In Part 1 – Linear Data Structures in Java, we discussed arrays, linked lists, stacks, and queues. In this Java tutorial, we are going to study about Hierarchical Data Structure: Binary Tree, BST, Heap, and Hash in detail with examples.
So, let us start with Hierarchical Data Structure in Java.
2. Hierarchical Data Structure in Java
In this Java tutorial, we are going to study the Types of Java hierarchical data structure–
- Binary Tree
- Binary Search Tree
3. Binary Tree
A hierarchical data structure in java is unlike linear data structures, a binary tree is a tree data structure, it can have at most two children, called the left child and the right child, and it is implemented using links.
a. Representation of Binary Tree
A binary tree is represented by a pointer on the topmost node in a tree, if the nodes in the tree are empty then the root of that tree is NULL.
Following are the parts of a tree –
- Pointer to the right child
- Pointer for the left child
A binary tree can be traversed in the following two ways –
In order (Left-Root-Right), Preorder (Root-Left-Right) and Postorder (Left-Right-Root)
Level Order Traversal
b. Properties of Binary Tree
|The most number of nodes at level ‘l’||2^(l-1)|
|Maximum number of nodes ( h is height of tree)||2^(h – 1)|
|Minimum possible height ()log with base 2)||ceil(Log(n+1))|
|Time Complexity of Tree Traversal||0(n)|
c. Binary Tree Example
4. Binary Search Tree (BST)
Binary search Tree is another Hierarchical data structure in Java, which is similar to a binary tree but with some added properties, they are –
- The left subtree of the BST has nodes which are less than the node’s key.
- Left subtree of the BST has only nodes with keys greater than the node’s key.
- Left and right should also be BST.
They provide quicker access and search options which is quicker than linked lists and slower than arrays.
They provide quicker insertion and deletion options which is quicker than arrays and slower than linked lists.
a. Time Complexities
Extra Space: O(n) for pointers
h: Height of BST
n: Number of nodes in BST
If Binary Search Tree is Height Balanced,
h = O(log n)
Its fundamental utilize is in look application where information is continually entering/leaving and information needs to imprinted in an arranged request. For instance in usage in E-business sites where another item is included or item leaves stock and all items are listed in the arranged request.
5. Binary Heap
A binary heap is a binary tree of a Hierarchical data structure in Java with added facilities –
- It’s an entire tree (All levels are totally filled aside from potentially the last level and the last level has all keys as left as could expect under the circumstances). This property of Binary Heap makes them appropriate to put away in an exhibit.
- Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be least among all keys show in Binary Heap. A similar property must be recursively valid for all hubs in Binary Tree. Max Binary Heap is like MinHeap. It is, for the most part, actualized utilizing exhibit.
Get Minimum in Min Heap: O(1) [Or Get Max in Max Heap]
Extract Minimum Min Heap: O(Log n) [Or Extract Max in Max Heap]
Decrease Key in Min Heap: O(Log n) [Or Extract Max in Max Heap]
Insert: O(Log n)
Delete: O(Log n)
Utilized as a part of actualizing productive need lines, which thusly utilize for planning forms in working frameworks. Need Queues are likewise utilized as a part of Dijstra’s and Prim’s diagram calculations.
Request measurements: The Heap information structure can utilize to productively discover the k’th littlest (or biggest) component in an exhibit.
Heap is an extraordinary information structure and it can’t utilize for seeking a specific component.
6. HashingHash Function
A hashingHash function – Hierarchical data structure in java use to convert a big input key to a small integer value which is more practical.
- Collision Handling: Since a hash work gets us a modest number for a key which is a major whole number or string, there is plausibility that two keys result in the same value. The circumstance where a recently embedded keymap to an effectively possessed space in a hash table is called impact and should take care of utilizing some crash taking care of procedure.
Following are the approaches to deal with it:
Chaining: The thought is to make every cell of hash table point to a connected rundown of records that have same hash work esteem. Chaining is basic, yet requires extra memory outside the table.
Open Addressing: In open tending to, all components are put away in the hash table itself. Each table section contains either a record or NIL. While hunting down a component, we one by one look at tablespaces until the point when the coveted component is found or unmistakably the component isn’t on the table.
Search: O(1) [Average] O(n) [Worst case]
Insertion: O(1) [Average] O(n) [Worst Case]
Deletion: O(1) [Average] O(n) [Worst Case]
So, this was all about Hierarchical Data Structure in Java. Hope you like our explanation.
In this tutorial, we learned about the second set of a Hierarchical data structure in Java programming language, in the second set we covered Binary Tree, Representation of Binary Tree, Properties of Binary Tree, Binary Search Tree, Binary Heap, HashingHash Function. In the third set, we will cover graphs and other topics. Furthermore, if you have any query, feel free to ask in the comment section.