5. Разделительное дерево
Теперь легко доказать следующее.
Теорема 8. Разделительное дерево с 
ярусами может быть построено с любым распределением
Можно доказать это утверждение по индукции. Как было показано, оно верно для 
. Из предположения, что оно верно для 
следует, что оно верно для 
поскольку лемма утверждает, что любая последовательность
может быть разложена в сумму двух последовательностей, каждая из которых может быть реализована деревом в силу индуктивного предположения.
Ясно, что среди возможных распределений
для дерева может быть найдено «почти равномерное» распределение для всех переменных, кроме одного. Таким образом, можно распределить нагрузки между 
из них равномерно, а для одного переменного использовать один (переключающий) элемент. Получим такие близкие к равномерному распределения:
