About built-in AAs

[bearophile]

Walter Bright:

> It wasn't changed to simplify code, it was changed because it was faster.

Right.


> As for "attacks", if your code is subject to people sending it specially crafted 
> input in the hopes of making it run slowly, you can make specially crafted input 
> to make trees run slowly, too.

I think there are search trees like the Red-Black ones that guarantee a O(n ln n) worst case. I am wrong?

>Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red–black trees to be efficient in the worst-case, unlike ordinary binary search trees.<

From:
http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties

Bye,
bearophile