Is there any practical application of Tango Trees?

问题:

Balanced binary search tree gives an O(log(n)) guaranteed search time.

Tango trees achieves a search of O(log(log(n)) while compromising small amount of memory per node. While I understand that from theoretical point of view log(n) and log(log(n)) makes a huge difference, for majority of practical applications it provides almost no advantage.

For example even for a huge number like n = 10^20 (which is like few thousand petabytes) the difference between log(n) = 64 and log(log(n)) = 6 is pretty negligible. So is there any practical usage of a Tango tree?

回答1:

tl;dr: no, use a splay tree instead.

Tango trees don't give you O(log log n) worst case lookups -- the average case is I think O(log n log log n). What they do is run at most O(log log n) times more slowly than a binary tree with an oracle that performs rotations to optimize the access patterns.

Splay trees might run O(1) times more slowly than the aforementioned theoretical magic tree -- this is the Dynamic Optimality conjecture. Splay trees are much simpler than tango trees and will have lower constant factors to boot. I can't imagine a practical application where the tango tree guarantee would be useful.