10

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?

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
  • I wouldn't call one order of magnitude (64/6) "pretty negligible". – Paul R Feb 03 '15 at 08:14
  • 2
    @PaulR this order of magnitude is achieved when you search through 10^20 elements. To get the difference that one can notice (1 second) I need a number way higher then 10^1000. – Salvador Dali Feb 03 '15 at 08:24
  • It's absolutely negligible if you are dealing with a regular problem. If you are doing some calculations that require worknig with HUGE(REALLY HUGE) numbers then maybe. – Christo S. Christov Feb 04 '15 at 07:14
  • 3
    @Chris please look carefully at the question. If you even take the [number of atoms in the universe (n=10^81)](http://en.wikipedia.org/wiki/Shannon_number) the difference will be negligible `log(n) = 270` and `log(log(n)) = 8` – Salvador Dali Feb 04 '15 at 08:18

1 Answers1

5

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.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120