Well, nobody I know uses hash tables without periodically "rebalancing" them either.

Where I went to school, we were taught not to compare the worst case behavior of one structure to the average of another. We were also taught not to confuse binary trees with red-black trees.