"Implement a red-black tree on a whiteboard" is code for "we don't know how to interview, so we ask about stuff that the hiree will never do". I'm not so sure the "advantage" is actually an advantage.
Yeah, it's very possible that Google doesn't know how to interview. I don't think it's a solved problem anywhere in the industry -- teams just do what seems to work for them, with lots of false positives and negatives.
* As far as I remember it was in Coders at Work (very good book btw)