Doubly logarithmic tree

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a doubly logarithmic tree is a <a href="/facts/Tree_(data_structure)/RcXz9noF">tree</a> where each internal node of height 1, the tree layer above the leaves, has two children, and each internal node of height 
  
    
      
        h
        >
        1
      
    
    {\displaystyle h>1}
  
 has 
  
    
      
        
          2
          
            
              2
              
                h
                −
                2
              
            
          
        
      
    
    {\displaystyle 2^{2^{h-2}}}
  
 children. Each child of the root contains 
  
    
      
        
          
            n
          
        
      
    
    {\displaystyle {\sqrt {n}}}
  
 leaves. The number of children at a node from each leaf to root is 0,2,2,4,16, 256, 65536, ... (sequence A001146 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>)
</p>

<p>A similar tree called a k-merger is used in <a href="/facts/Harald_Prokop/1e4kGdzT">Prokop</a> et al.'s <a href="/facts/Cache_oblivious/8pueWrAn">cache oblivious</a> <a href="/facts/Funnelsort/baQXQIPq">Funnelsort</a> to merge elements.
</p>

Doubly logarithmic tree open-in-new

Doubly logarithmic tree