Дважды логарифмическое дерево

В информатике дважды логарифмическое дерево — это дерево , в котором каждый внутренний узел высоты 1, слой дерева над листьями, имеет двух дочерних элементов, а каждый внутренний узел высоты $h>1$ имеет $2^{2^{h-2}}$ дети. Каждый дочерний элемент корня содержит ${\sqrt {n}}$ листья. ^[1] Количество дочерних элементов узла от каждого листа до корня равно 0,2,2,4,16, 256, 65536,... (последовательность A001146 в OEIS )

Подобное дерево, называемое k-слиянием, используется в Прокопа и др., не обращающей внимания на кеш, сортировке воронок для объединения элементов. ^[2]

Ссылки

^ Беркман, Омер; Шибер, Барух ; Вишкин, Узи (1993), «Оптимальные дважды логарифмические параллельные алгоритмы, основанные на поиске всех ближайших меньших значений», Journal of Algorithms , 14 (3): 344–370, CiteSeerX 10.1.1.55.5669 , doi : 10.1006/jagm.1993.1018
^ Харальд Прокоп. Алгоритмы, не обращающие внимания на кэш . Магистерская диссертация, Массачусетский технологический институт. 1999.

Дальнейшее чтение

М. Фриго, К.Э. Лейзерсон, Х. Прокоп и С. Рамачандран. Алгоритмы, не обращающие внимания на кэш. В материалах 40-го симпозиума IEEE по основам информатики (FOCS 99), с. 285-297. 1999. Расширенный реферат в IEEE , в Citeseer .
Демейн, Эрик . Обзор сортировки без учета кэша . Примечания для MIT Computer Science 6.897: Расширенные структуры данных.

[1] Беркман, Омер; Шибер, Барух ; Вишкин, Узи (1993), «Оптимальные дважды логарифмические параллельные алгоритмы, основанные на поиске всех ближайших меньших значений», Journal of Algorithms , 14 (3): 344–370, CiteSeerX 10.1.1.55.5669 , doi : 10.1006/jagm.1993.1018

[2] Харальд Прокоп. Алгоритмы, не обращающие внимания на кэш . Магистерская диссертация, Массачусетский технологический институт. 1999.

[1]

[2]