Java Binary Search Tree & TreeSet

Binary Search Tree - Search Efficiency

1. Binary Search Tree of TreeSet

In the past few examples, we learned about TreeSet, How to Perform Natural Sorting & Custom Sorting. Now we will look at the internal structure of the TreeSet and how it uses the Binary Search Tree for search efficiency. First, we will learn what is Binary Tree and how to turn it down as Search Tree (Binary). Finally, we will use our Product and see how it is represented as a Binary Search Tree. Note, some call this Binary Search Tree as Red-Black tree when it is balanced. We will learn this also in this example.

2. Binary Tree & Its Nodes

Binary Tree is the organization of nodes in such a way that each node will have at maximum 2 Childs. To learn it, let us say we have seven unique numbers as in the picture below:

Set of Numbers
Set of Numbers

At this stage, the above numbers are not sorted, and we can store them as a binary tree. One such a tree is below:

Binary Tree Representation of the Numbers
Binary Tree Representation of the Numbers

In the above tree you can take any node and it will have 2 or less child(s). The node 1 has two Childs whereas node 4 has no child. In our tree form of the numbers, the nodes 5,3,4 and 7 are leaf nodes or end nodes with no child. Node 6 is the root node.

3. Binary Search Tree

The improved form of Binary Tree is Binary Search Tree. Here, duplicate elements are not allowed. Also, the Tree structure holds the nodes in a sorted way. Let us consider the same set of numbers. To form the data structure, we must sort the numbers first. The sorted numbers are below:

Set of Numbers - Sorted
Set of Numbers – Sorted

Now, we can form the search tree by taking the middle element as root and here it is number 4. Then comes the next rules.

  1. For a given node, Left side will have lower value
  2. Right side will have a higher value.

By applying the above rule, we will get the Binary Search Tree as in the below picture:

Binary Search Tree of Same Numbers
Binary Search Tree of Same Numbers

Now, when we take any node, all the left side node(s) will have lower value and right-side node(s) will have higher value. This formation of nodes helps in searching for a specific element efficiently which we will see in the next section.

The search is efficient when the binary tree is balanced. A Balanced Tree contains a nearly equal number of nodes on left & right side of the root node. In our above tree, we can observe the Balanced Tree as its root node 4 has an equal number of nodes on both sides. Java calls these balanced trees as Red-Black Trees. Now have a look at the below picture:

Binary Search Tree - Search Efficiency
Binary Search Tree – Search Efficiency

In the above Red-Black Tree we keep seven numbers. The tree has three levels marked as Level0, Level1 & Level2. Now, to search a specific number among these 7, we need a maximum of three comparison. In each compare, we get past one level.

Let us say we want to find number 7 exists in the Tree. The comparison starts from the root and how it goes is bulleted below:

  • Number 7 compared with the root 4. Number 7 is bigger, so we travel right.
  • Right side node is 6. The number 7 is bigger than 6, we travel right again.
  • Right side node is 7. We found number 7.

There are only three compare (7 vs 4, 7 vs 6, 7 vs 7). When the number of elements grows, this Red-Black tree provides much more search efficiency. In the above picture, you can see Level 32 alone in the tree can hold 1 million elements. And maximum comparison required to find an element is only 32. The tree traversal algorithm reports element not found when its tree traverse reaches the root node in search of an element.

5. Examining Binary Search Tree

In the past article on HashSet Bucketing, we visualized it through Eclipse Debugger. To see how TreeSet forms the Tree Nodes, we will add logging code in the compareTo method of the Product class. Note, we added this method while we learned about Java Comparator Interface. Below is the changed code to log the comparison in the console output window:

Next, we create six Products and add it to the TreeSet. The insertion order is 102, 104, 101, 103, 106 and 105.

You can check out the tree formation and how Root Node is changing by looking at the console output window. The root node change is the proof that Java TreeSet maintains its Binary Tree balanced so that search will be efficient. The below picture shows the Tree formation which derived from the console output window:

Product Class Represented as Binary Search Tree - By TreeSet
Product Class Represented as Binary Search Tree – By TreeSet

Note, we hand made the Tree by examining console output. Some node may be wrong as Java will change it on each add function call to keep the tree balanced. But the above picture makes you visualize how Java keeps the Product instances in the Tree form. One can watch the video at the end of this example, which will make clear about the Tree Formation and how Java adjusts it on each node insertion.

6. Complete Code Example on TreeSet’s Red-Black Tree

7. Watch Binary Search Tree Formation – YouTube

Do you like this Example? Please comment about it for others!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.