Doubly logarithmic tree
|This article is an orphan, as no other articles link to it. Please introduce links to this page from ; try the Find link tool for suggestions. (October 2013)|
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. 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)
- 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, doi:10.1006/jagm.1993.1018.
- Harald Prokop. Cache-Oblivious Algorithms. Masters thesis, MIT. 1999.
- 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. Extended abstract at IEEE, at Citeseer.
- Erik Demaine. Review of the Cache-Oblivious Sorting. Notes for MIT Computer Science 6.897: Advanced Data Structures.