# Counting the number of comparisons in red black tree

I have an array with $$N$$ elements and I run an algorithm that find how many distinct elements are in the array by using a red black tree as follows:

• for each element
• if element not in tree
• insert element to tree
• increase distinct elements counter by 1

I need to find a formula to count how many comparisons the algorithm performed with $$N$$ as variable for both the best case and worst case.

For the best case this is pretty easy, the array include $$N$$ instances of the same element so each search does 1 comparison and there is no insertions, except for the first element, hence the number of comparisons is $$N-1$$. But I'm having trouble with the worst case. Firstly I'm not sure what is the worst case in this scenario as red black tree balance itself after each insertion, I do know that all the elements in the array must be distinct but in order to get the worst case I will need that each search will go down the longest route to a leaf and same with the insert. How can i devise an input array that cause the worst case and how to create a formula that calculates the max number of comparisons?