doubly logarithmic tree
{{Short description|Concept in computer science}}
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.{{citation|first1=Omer|last1=Berkman|first2=Baruch|last2=Schieber|author2-link=Baruch Schieber|first3=Uzi|last3=Vishkin|author3-link=Uzi Vishkin|title=Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values|journal=Journal of Algorithms|volume=14|pages=344–370|year=1993|issue=3|doi=10.1006/jagm.1993.1018|citeseerx=10.1.1.55.5669}} The number of children at a node from each leaf to root is 0,2,2,4,16, 256, 65536, ... {{OEIS|id=A001146}}
A similar tree called a k-merger is used in Prokop et al.'s cache oblivious Funnelsort to merge elements.Harald Prokop. [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5650 Cache-Oblivious Algorithms]. Masters thesis, MIT. 1999.
References
{{reflist}}
Further reading
- M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), p. 285-297. 1999. [https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=814600 Extended abstract at IEEE], [http://citeseer.ist.psu.edu/307799.html at Citeseer].
- Demaine, Erik. [http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L17/lecture17.pdf Review of the Cache-Oblivious Sorting]. Notes for MIT Computer Science 6.897: Advanced Data Structures.