二重対数木

コンピュータサイエンスにおいて、二重対数木とは、高さ1の内部ノード（葉の上の層）がそれぞれ2つの子を持ち、高さの各内部ノードがそれぞれ子を持つ木である。根の各子には葉が含まれる。^{[1]各葉から根までのノードにおける子の数は、0,2,2,4,16,256,65536,…である（} OEISのシーケンスA001146）。 ${\displaystyle h>1}$ ${\displaystyle 2^{2^{h-2}}}$ ${\displaystyle {\sqrt {n}}}$

二重丸太の木

プロコップらのキャッシュ忘却型 ファネルソートでは、k-mergerと呼ばれる同様のツリーが要素をマージするために使用されています。^[2]

参考文献

1. Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993)、「最も近い小さな値をすべて見つけることに基づく最適な二重対数並列アルゴリズム」、Journal of Algorithms、14 (3): 344– 370、CiteSeerX  10.1.1.55.5669、doi :10.1006/jagm.1993.1018
2. Harald Prokop. キャッシュ忘却アルゴリズム. MIT修士論文. 1999年.

さらに読む

• M. Frigo, CE Leiserson, H. Prokop, S. Ramachandran. キャッシュ忘却アルゴリズム. Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), p. 285-297. 1999. IEEEにおける拡張概要、Citeseerにて公開。
• デメイン、エリック. キャッシュ忘却ソートのレビュー. MITコンピュータサイエンス6.897「高度なデータ構造」のノート.