No trees in the stdlib?

[Lawrence D'Oliveiro]

In message <mailman.2144.1245999295.8015.python-list at python.org>, Miles 
Kaufmann wrote:

> On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote:
> 
>> That's pretty much the bisect module in a nutshell. It manipulates a
>> sorted list using binary search.
> 
> With O(n) insertions and removals, though.  A decent self-balancing
> binary tree will generally do those in O(log n).

For values of n below, say, a million, would you even notice the difference 
on modern hardware?