Search code examples
javabinary-treecomparatortreeset

What would be the impact of using a TreeSet<Integer> with a comparator that allows duplicates

The problem (No binary tree with duplicates in java collections).

I need a binary tree with duplicates, I need the O(Log(n)) complexity of searching and insertion while keeping the order (so i can't use Hash tables), java doesn't have a collection that implements a binary tree and allow duplicates while keeping all binary tree operations.

Can we use TreeSet to do this?

I'm trying to tweak TreeSet and allow duplicates by passing a comparator that never returns 0. I know this won't be a set anymore but it's ok, i need duplicates.

Example

TreeSet<Integer> binaryTreeWithDuplicates = new TreeSet<Integer>((x, y) -> x>y?1:-1);

Will there be an undesirable side effect of such implementation and usage?
because we are obviously violating the rules in comparator api like the sign rule.

Solution

  • contains would never return true.

    You could have arbitrary duplicates in the set, and not be able to identify or remove them. (remove would never work.)