троичное дерево, частично сбалансированное методом отрезков
Очевидно, что это не самое лучше дерево из всех. Максимальное количество сравнений (т. е. количество сравнений в худшем случае) сократилось с пяти до четырех, а количество ветвлений возросло вдове, в результате чего, время выполнения оператора switch только возросло. К тому же, структура построения дерева явна не оптимальна. Гнезда (a<=3), (a>=7), (a<=96), (a>=666) имеют свободные ветви, что увеличивает высоту дерева на единицу. Но, может быть, компилятор сумеет это оптимизировать?
Дизассемблирование показывает, что компилятор msvc генерирует троичное дерево, сбалансированное по улучшенному алгоритму отрезков, содержащее всего лишь 7 операций сравнения, 9 ветвлений и таблицу переходов на 10 элементов (см. "создание таблицы переходов"). В худшем случае, выполнение оператора switch требует 3 сравнений и 3 ветвлений. Троичное дерево построенное компилятором gcc, сбалансировано по классическому алгоритму отрезков и состоит из 11 сравнений и 24 ветвлений. В худшем случае, выполнение оператора switch растягивается на 4 сравнения и 6 ветвлений. Компилятор icl, работающий по принципу простого линейного поиска, строит двоичное дерево из 11 сравнений и 11 ветвлений. В худшем случае, все узлы дерева "пережевываются" целиком. Вот так "оптимизация"!
