Doubly logarithmic tree

In computer science, a doubly logarithmic tree is a tree where each internal node of height 1, the tree layer above the leaves, has two children, and each internal node of height has children. Each child of the root contains leaves.[1] The number of children at a node from each leaf to root is 0,2,2,4,16, 256, 65536, ... (sequence A001146 in the OEIS)

One dot at the top has two lines connecting to other dots.
A double log tree

A similar tree called a k-merger is used in Prokop et al.'s cache oblivious Funnelsort to merge elements.[2]

References

edit
  1. ^ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values", Journal of Algorithms, 14 (3): 344–370, CiteSeerX 10.1.1.55.5669, doi:10.1006/jagm.1993.1018
  2. ^ Harald Prokop. Cache-Oblivious Algorithms. Masters thesis, MIT. 1999.

Further reading

edit