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 can have at most two children, called the left child and the right child, and it is implemented using links.
The topmost node of a tree is the parent node and the nodes inside that parent node are child nodes.
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 –
- Depth First Search
- Breadth First Search
b. Properties of Binary Tree
|The most number of nodes at level ‘l’||2^(l-1)|
|Maximum number of nodes ( h is the height of tree)||2^(h – 1)|
|Minimum possible height ()log with base 2)||ceil(Log(n+1))|
|Time Complexity of Tree Traversal||0(n)|
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.
- The right subtree of the BST has only nodes with keys greater than the node’s key.
- Left and right should also be BST.
The binary search tree is mainly used in the search applications where the data is entered frequently for example maps. They provide quick 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)
5. Binary Heap
A binary heap is a binary tree of a Hierarchical data structure in Java with added functionalities –
- 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.
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 be used for searching a specific component.
6. Hashing Function
A hashing function is the Hierarchical data structure in java which is used to convert a big input key to a small integer value which is more practical.
In hash function maps the keys to values. Every key is associated with its value. There is a possibility that one or more values have the same key. But this may lead to the collision because of mapping.
Following are the approaches to deal with it:
Chaining: The thought is to make every cell of hash table point to a connected report of records that have the same hash work esteem. Chaining is basic, yet requires extra memory outside the table.
Open Addressing: In open addressing, 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 converted component is found or unmistakably the component isn’t on the table.
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.