> An immutable tree is often about as fast as a mutable tree, it's just pointer manipulation in either case.

This might be true, depending on what type of processing you're doing, and if you have a good garbage collector.

Of course, if you're allowed to use mutable trees, then you should just use a hash table which will be faster both asymptotically and in practice.