search

braibant / articheck

14 stars 2 forks source link

Do some math #20

Open protz opened 10 years ago

protz commented 10 years ago

I think we could ask our friends from RAP (e.g. Henning) to compute for us the probability that a randomly-generated tree actually satisfies the Red-Black tree property (I suspect it's at least exponentially small). That would be a good point for the intro paragraph.

braibant commented 10 years ago

To be fair, one should check in quickcheck papers whether they can tune the generators to that extent...

braibant commented 10 years ago

http://www.seas.upenn.edu/~cis552/12fa/lectures/stub/RedBlack.html