Doubly logarithmic tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 h > 1 has 2^{2^{h-2}} children. Each child of the root contains \sqrt{n} leaves. The number of children at a node as we go from leaf to root is 0,2,2,4,16, 256, 65536, ... (sequence A001146 in OEIS)

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

Double log tree.png