CODEWITHSUNDEEP
javahashmaptime-complexity
JavaDeveloper
JavaDeveloper

Reputation: 5670

What's the worst-case time complexity of TreeSet?

It is stated here that

TreeSet has a log(n) time complexity guarantuee for add()/remove()/contains().

But TreeSet uses a binary search tree and in the worst case, binary search trees can have O(n) height. How is the log(n) complexity "guaranteed"?

Upvotes: 0

Views: 1437

Answers (1)

Søren Debois
Søren Debois

Reputation: 5688

The implementation rebalances the tree upon inserts.

The O(lg n) time bound for insert is guaranteed by the official documentation. This should not come as a surprise: A classic way to implement sets is as some sort of self-balancing binary search tree.

Java libraries are publicly available, so let's go see for ourselves. TreeSet can be found, e.g., here. It is implemented in terms of TreeMap, which is in turn here. As @Don Roby points out, the underlying data structure is a Red-Black tree.

Upvotes: 3

Related Questions