Функция Шеннона сложности интервального поиска на булевом кубе в классе деревьев

Для задачи интервального поиска на булевом кубе исследуется поведение функции Шеннона сложности в классе древовидных схем, называемых информационными деревьями. Показано, что для баз данных, чья мощность совпадает по порядку с мощностью булева куба, функция Шеннона по порядку равна оптимальной сложности в классе сбалансированных древовидных схем. Для баз данных с мощностью, меньшей по порядку, чем мощность булева куба, найдена асимптотика логарифма функции Шеннона.