Skip to content
Latest
Binary Search Tree - Search Efficiency

Performance Study – ArrayList vs TreeSet

In the past examples, we came across ArrayList and TreeSet. We know how Binary Tree of TreeSet involves in search efficiency. In this example, we will compare performance of the TreeSet with ArrayList, Here, we use our Product class and add Millions of it to both TreeSet & ArrayList and then search for specific items in it. We do this test to know operation performance for both adding the items as well as finding the items.

Binary Search Tree - Search Efficiency

Java Binary Search Tree & 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.

How Comparator compare Method Works

Java Comparator & compare

In the past example on Comparable Interface, we built Natural Sorting Order for our Product class by overriding the compareTo method. We did this sorting in the Product class itself. Then we used the Product as TreeSet Items. This means, does TreeSet support only one sorting? No, we can define custom sorting also. We can define it through a user class which signs the Comparator Interface and overrides its compare method. We can define one or many custom sorting orders using the Comparator Interface. For example, Sorting the product by its name in Ascending and descending order can be done through Java Comparator Interface.

Comparing Object Via Comparable Interface - Explained

Java Comparable Interface & compareTo Method

We used TreeSet class in the past example on the Integer boxed type. The TreeSet knows how to compare two Integer boxed type because the Java Integer class implements Comparable interface. For user-defined types, one should sign the the Comparable interface contract so that Java Collection class like TreeSet knows how to compare two objects and choose which one is bigger. The Comparable interface has a contract method compareTo which will study two objects and returns an integer. This integer value is helpful to know the object bigger or smaller or equal with the compared object. In this example, we will use the Java TreeSet to store Product objects.

Java TreeSet and SortedSet Interface

Java TreeSet & SortedSet Explained

The Java TreeSet class implements the SortedSet Interface. Before we move on to the TreeSet Collection class, we will study about the SortedSet interface and functionality it offers. Set interface is base for SortedSet interface, and a SortedSet gives all the functionality of the Set interface. We once saw the Set interface when we leant about the HashSet in HashSet Example. On top of the Set’s unique items claim, the SortedSet claims for Element Ordering.

Since SortedSet perform sorting, it needs to know how to compare two elements and say which one is big. Java types String and Boxed types Integer, Double etc. provide these comparisons via the Comparable Interface.