On: Aguri: Coolest Data Structure You've Never Heard Of

[bayareaguy]

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.

[ckuehne → bayareaguy]

I guess your school sucked. Red-black trees ARE binary search trees. Also: the worst case behavior of a hash table is in fact worse than that of a balanced (red-black tree, b-tree, avl-tree) search tree.

[bayareaguy → ckuehne]

Red-black trees ARE binary search trees.

Agreed. However the original poster said binary tree, a specific structure whose worse case behavior is O(n) just like a hash table.

They didn't say binary search tree (which as you observe may refer to one of several possible structures).

[tptacek → bayareaguy]

Your school taught you to "balance" hash tables?

[bayareaguy → tptacek]

The quotes were there for a reason.