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:
At this stage, the above numbers are not sorted, and we can store them as a binary tree. One such a tree is below:
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:
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.
- For a given node, Left side will have lower value
- Right side will have a higher value.
By applying the above rule, we will get the Binary Search Tree as in the below picture:
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.
4. Balanced Binary Search Tree – Efficiency of Search
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:
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//Sample 05: Implement Product Comparison @Override public int compareTo(Object o) { //5.1: Cast the Element to Product Product element = (Product)o; int retVal = this.ProdId - element.getProdId(); //5.1: Log the Comparison System.out.println("Current Object: " + this ); System.out.println("Comparing: " + element ); System.out.println("Comparison Returns: " + retVal ); System.out.println("--------------------"); //5.2: Compare and Return return retVal; } |
Next, we create six Products and add it to the TreeSet. The insertion order is 102, 104, 101, 103, 106 and 105.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//Sample 02: Create Set SortedSet<Product> set = new TreeSet<Product>(); //Sample 03: Create six Products Product p1 = new Product(101, "Pen"); Product p2 = new Product(102, "Pencil"); Product p3 = new Product(103, "Rubber"); Product p4 = new Product(104, "Writing Pad"); Product p5 = new Product(105, "Clips"); Product p6 = new Product(106, "Sharpner"); //Sample 04: Add System.out.println("############ Add 102 Pencil ############"); set.add(p2); System.out.println("############ Add 104 Writing Pad #######"); set.add(p4); System.out.println("############ Add 101 Pen ###############"); set.add(p1); System.out.println("############ Add 103 Rubber ############"); set.add(p3); System.out.println("############ Add 106 Sharpner ##########"); set.add(p6); System.out.println("############ Add 105 Clips #############"); set.add(p5); set.clear(); |
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:
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
Product.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
import java.util.Objects; //Sample 05: Make Product Comparable for //Natural Sorting Order public class Product implements Comparable{ private int ProdId; private String ProdName; Product(int id, String name) { ProdId = id; ProdName = name; } @Override public String toString() { return ProdId + ":" + ProdName ; } public int getProdId() { return ProdId; } public void setProdId(int prodId) { ProdId = prodId; } public String getProdName() { return ProdName; } public void setProdName(String prodName) { ProdName = prodName; } @Override public int hashCode() { return Objects.hashCode(ProdId); } @Override public boolean equals(Object obj) { Product prod = (Product) obj; return (this.ProdId == prod.getProdId()); } //Sample 05: Implement Product Comparison @Override public int compareTo(Object o) { //5.1: Cast the Element to Product Product element = (Product)o; int retVal = this.ProdId - element.getProdId(); //5.1: Log the Comparison System.out.println("Current Object: " + this ); System.out.println("Comparing: " + element ); System.out.println("Comparison Returns: " + retVal ); System.out.println("--------------------"); //5.2: Compare and Return return retVal; } } |
TreeSetNumber.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
//Sample 01: Package Required import java.util.Iterator; import java.util.SortedSet; import java.util.TreeSet; public class TreeSetNumber { public static void main(String[] args) { //Sample 02: Create Set SortedSet<Product> set = new TreeSet<Product>(); //Sample 03: Create six Products Product p1 = new Product(101, "Pen"); Product p2 = new Product(102, "Pencil"); Product p3 = new Product(103, "Rubber"); Product p4 = new Product(104, "Writing Pad"); Product p5 = new Product(105, "Clips"); Product p6 = new Product(106, "Sharpner"); //Sample 04: Add System.out.println("############ Add 102 Pencil ############"); set.add(p2); System.out.println("############ Add 104 Writing Pad #######"); set.add(p4); System.out.println("############ Add 101 Pen ###############"); set.add(p1); System.out.println("############ Add 103 Rubber ############"); set.add(p3); System.out.println("############ Add 106 Sharpner ##########"); set.add(p6); System.out.println("############ Add 105 Clips #############"); set.add(p5); set.clear(); //Sample 05: Is it Balancing. Yes it is! System.out.println("############ Add 101 Pen ###############"); set.add(p1); System.out.println("############ Add 102 Pencil ############"); set.add(p2); System.out.println("############ Add 103 Rubber ############"); set.add(p3); System.out.println("############ Add 104 Writing Pad #######"); set.add(p4); System.out.println("############ Add 105 Clips #############"); set.add(p5); System.out.println("############ Add 106 Sharpner ##########"); set.add(p6); } //Sample 03: Traverse and Print the the Tree private static void printTree(SortedSet<Integer> set) { Iterator<Integer> itr = set.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ","); System.out.println(); } } |
7. Watch Binary Search Tree Formation – YouTube
Categories: Java
Tags: Binary Search Tree, Binary Tree, Red-Black Tree, TreeSet
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.