computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, a doubly logarithmic tree is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

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^

children. Each child of the root contains

\sqrt

leaves. The number of children at a node from each leaf to root is 0,2,2,4,16, 256, 65536, ... Double log tree

A similar tree called a k-merger is used in

Prokop Prokop may mean either of two Hussite generals, both of whom died in the 1434 battle of Lipan: * Prokop the Great * Prokop the Lesser Other people who bore the name Prokop: * Procopius Procopius of Caesarea (; ''Prokópios ho Kaisareús''; ...

et al.'s cache oblivious Funnelsort to merge elements.Harald Prokop
Cache-Oblivious Algorithms
Masters thesis, MIT. 1999.

References

{{reflist

References

Further reading