lennyfoulds lennyfoulds - 2 months ago 13
Java Question

Expected Percentage of Red Nodes in Left Leaning Red Black Tree Program?

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?