Tango tree

<p>A tango tree is a type of <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree</a> proposed by <a href="/facts/Erik_D._Demaine/qby54dWx">Erik D. Demaine</a>, Dion Harmon, <a href="/facts/John_Iacono/q1obsg5x">John Iacono</a>, and <a href="/facts/Mihai_P%25C4%2583tra%25C8%2599cu_(computer_scientist)/5JEXV5zz">Mihai Pătrașcu</a> in 2004. It is named after <a href="/facts/Buenos_Aires/9lUVmS7f">Buenos Aires</a>, of which the <a href="/facts/Tango/zjY3wATe">tango</a> is emblematic.
</p><p>It is an <a href="/facts/Online_algorithm/64TsU7Yz">online</a> binary search tree that achieves an 
  
    
      
        O
        (
        log
        ⁡
        log
        ⁡
        n
        )
      
    
    {\displaystyle O(\log \log n)}
  
 <a href="/facts/Competitive_ratio/ocEpTvXG">competitive ratio</a> relative to the <a href="/facts/Offline_algorithm/64TsU7Yz">offline</a> <a href="/facts/Optimal_binary_search_tree/ESfe6hoL">optimal binary search tree</a>, while only using 
  
    
      
        O
        (
        log
        ⁡
        log
        ⁡
        n
        )
      
    
    {\displaystyle O(\log \log n)}
  
 additional bits of memory per node. This improved upon the previous best known competitive ratio, which was 
  
    
      
        O
        (
        log
        ⁡
        n
        )
      
    
    {\displaystyle O(\log n)}
  
.
</p>

Tango tree open-in-new

Tango tree