Hierarchical Data Structure in Java – Binary Tree, Binary Search Tree, Heap, Hash

Before we start, as usual, we will look at an example of a hierarchical data structure in real life.

Let us take the example of your family. Let’s say your great-grandfather had two children, a girl and a boy. Each of these two children had three children each. Again, each of these three children has two children each. If you try to represent these by linear data structures, you would face a lot of problems. Keep in mind that although it is not impossible to represent them linearly, it is quite difficult.

Hence, we use a tree-like structure starting with your grandfather and ending with you. After drawing this, it will be easier for you to understand the family tree. In programming, these types of data structures are hierarchical data structures. Let us learn more about them.

Hierarchical Data Structure in Java

As we already know, linear data structures store data in a linear fashion. Similarly, hierarchical data structures store elements on the basis of hierarchy. This is efficient for visualizing and retrieving data.

Some of the popular hierarchical data structures in Java are:

• Binary Tree
• Binary Search tree
• Heap
• Hash

Binary Tree

Take the example we talked about in the introduction of this article. Now let’s say your grandfather had two children. And each of his children had two children each. In this manner, if every individual has at most two children, then the resulting tree would be a binary tree.

A binary tree has the following properties:

• There can only be two child nodes of a single node, except for the leaf nodes.
• A leaf node does not have any children.
• Each node has a field to store data, i.e, the value of the node.
• Each node has a pointer to the left child node and a pointer to the right child node.
• At a level ‘l’ there can be a maximum of 2^(l-1) nodes.
• If ‘h’ is the height of the tree, then the maximum number of nodes in the tree is 2^(h-1)
• The time taken to traverse a Binary Tree would be O(n).
• The minimum possible height of a binary tree would be ceil(log(n+1)), where n is the number of nodes and the log is of base 2.

Types of Binary tree in java

There are 5 types of binary trees:

1. Full Binary Tree in Java

You can call a binary tree a full binary tree when each of its nodes contains exactly 2 children or none at all. There can be no node having a single child or more than two children. It is a tree where each node has two children except the leaf nodes. There are a total of internal nodes+1 leaf node in a binary tree.

LeafNodes=InternalNodes+1.

2. Complete Binary Tree in Java

A complete binary tree has two nodes at every branch of its structure.

A complete binary tree has all of its levels filled except the last level. What do we mean by filled? Well, a level “filled” if it has 2^L nodes where L is the level. L starts from 0. Hence, the first level(0th level ) has 2^0=1 Node, the second level has 2^1 nodes, i.e, 2 nodes, so on.

The keys or the nodes in the last level are as left-oriented as possible.

Binary Heaps are complete Binary Trees. We will read about them in detail later in this article.

3. Perfect Binary Tree in Java

It is like a pyramid structure where all the nodes will have the same level. That means the height of the tree from the first to the last of every node will be the same.

A binary tree is deemed to be a perfect binary tree when each level is complete( this means that each node has exactly 2 child nodes). A perfect Binary tree also has all of its leaf nodes at the same level. The number of nodes in a perfect binary tree is 2^h-1, where “h” is the height of the tree.

4. Balanced Binary Tree in Java

A balanced binary tree is a tree where the height of the tree is an exact power of 2. You can think of it as a tree where the height of the tree is log(n), where n is the number of nodes. Many trees follow this concept.

AVL Trees are balanced trees. They make sure that the difference between the heights of the left and right subtrees is almost equal to 1.
Balanced Binary Trees implement this concept. This is why they provide optimized time complexities for search insert and delete operations on the tree.

5. Pathological or Degenerate Trees in Java

Pathological Trees are the trees where each node has only one child. The tree does not live up to its name because this is very similar to Linked Lists. In this type of tree, every node has a single child, which forms the structure like a slope of a line.

Applications of Binary Tree in Java

• Binary trees are particularly useful for storing data where data is extremely dynamic in nature, i.e, data is constantly added and removed.
• All routers, including the one in your home, use Binary Trees for storing the routing tables
• Wireless networking also sees a lot of Binary Tree usage these days.
• Many compression algorithms also use Binary Trees.
• Binary trees are used in various Java frameworks. They play a crucial role in networking, where the nodes are connected.
• It is used in the backend for building the gaming application. Minecraft, Spiral Knights, and Wakfu are some famous gaming applications that use binary trees in Java.

Binary Search Tree in Java

Binary Search Tree(BST) is very similar to Binary Trees, but there is a catch. Every node only contains elements less than itself on the left side and elements greater than itself on the right side.

• The left subtree of a particular node contains elements that are smaller in value than the current node.
• The right subtree of a particular node contains elements that are greater than the value of the current node.
• Do note that the left and right subtrees of the current node should also be a Binary Search Tree.
• BST’s allow faster searching than arrays.
• They also provide quicker insertion and deletion operations.

Time Complexities of BST in Java

1. Searching takes O(h), where h is the height of the tree.
2. Insertion takes O(h).
3. To delete a node, the complexity is O(h)
4. It takes linear space, i.e, O(n), for pointers to the adjacent nodes.
5. If the number of nodes in a binary search tree is n, then the height of the binary tree is O(log(n)) if it is a balanced tree.

Binary Heap in Java

You can think of a binary heap as being very similar to a binary tree with a few differences. Let us look at them

• Binary heaps are complete binary trees. We read about complete binary trees in the previous topic. All of their levels are complete except the last level. However, their last level has all of its nodes as left-oriented as possible. You can store a binary heap as an array or any collection because of this property.
• Binary Heaps are either MinHeaps or MaxHeaps. A MinHeap is a data structure that has the smallest element as the root of the tree. This same condition should be recursively true for the remaining subtrees. A MaxHeap is simply the opposite of a MinHeap. Its root has the maximum element. This is also true for all the remaining subtrees.
• Binary heaps are useful for implementing priority queues and heap sort.
• Graph Algorithms such as Dijkstra’s Shortest path and Prim’s Algorithm can be efficiently implemented using binary heaps.
• You can also use Binary heaps for finding the Kth smallest or largest value in a collection.

Applications of Binary Heaps in Java

Binary heaps in Java are popularly used in implementing Heap data structures, priority queues, and in problems where the kth smallest or largest elements need to be found efficiently. Binary heaps reduce the time complexity of these problems to a great extent.

Hashing in Java

In layman’s terms, hashing is a simple method for converting large data to smaller data. This is useful because hashing provides a way for mapping keys to values. They also support efficient lookup times as each key gets mapped to a single value.

A hashing function is a special function that takes an input and then maps it to a value. One popular data structure that implements hashing is a Hash Table. It contains two parts

1. A bucket array – This is responsible for containing the key-value pairs.

2. A hashing function – This converts the objects into hash values.

You cannot invert the hash function to get the original key back, although there are some modified hash data structures that allow that. There may be cases where two different inputs, upon hashing, return the same result. This results in errors. There are two ways of working around this error.

3. Chaining – Chaining is basically attaching the same result of two different inputs to the hash function by a chain. For example, if the hash value of ‘a’ is 12H34 and ‘b’ is also 12H34, then both of these results are chained together. This method requires extra space.

4. Open Addressing – This method is space-efficient. In this, we put the inputs directly into the hash table. This means that the result table is equal to or greater than the number of keys. Now, while inserting, we keep probing the table until we find an empty slot, and then we put the element there.

For search, we keep on checking every memory slot till we find “k” or we reach an empty slot. While deleting, we place a “deleted” marker on the slot to mark that it has been deleted. If we delete the key only, then a request for a search operation may fail. You can implement open addressing by Linear probing, Quadratic Probing, Clustering, and Double Hashing.

Summary

In this article, we learned about hierarchical data structure such as Binary trees, Heaps, Binary Search Trees, and Hashing. We also learned about the various operations that they support. Hierarchical Data Structures is a favorite topic for interviewers to test the candidates upon. It is also very useful for developers who are developing efficient software. So a good concept of these data structures will come in handy.