I modified a left-leaning red black tree program from a textbook to count the number of red nodes after inserting N distinct integers in the range of 1 to N for an assignment. I consistently get a percentage of of 52%-54%, for a N of 10^4, 10^5, and 10^6 when using an array of random integers created by the Java class Random.
Is this in a an acceptable range or should it be lower than that? I think about it in my head and I feel it should be lower so I was wondering if I made a mistake.
Thanks for your help!
The percentage should definitely be lower, around 30-35%. What algorithm are you using to calculate your percentage?