Поскольку оператор множественного выбора требует уникальности каждого значения, т.е. каждое число может встречаться в наборе (диапазоне) значений лишь однажды, легко показать, что:

а) в обеих кучах будет содержаться равное количество чисел (в худшем случае - в одной куче окажется на число больше);

б) все числа кучи A меньше наименьшего из чисел кучи B. Следовательно, достаточно выполнить только одно сравнение, чтобы определить в какой из двух куч следует искать сравниваемое значения.

Высота нового дерева будет равна ((N+1/2)+1), где N - количество гнезд старого дерева. Действительно, ветвь дерева делится надвое и добавляется новое гнездо - отсюда и берется N/2 и +1, а (N+1) необходимо для округления результата деления в большую сторону. Т.е. если высота не оптимизированного дерева достигала 100 гнезд, то теперь она уменьшилась до 51. Затем можно разбить каждую из двух ветвей еще на две. Это уменьшит высоту дерева до 27 гнезд! Аналогично, последующее уплотнение даст 16 ' 12 ' 11 ' 9 ' 8… и все! Более плотная упаковка дерева невозможна. Восемь гнезд - это не сто! Полное прохождение оптимизированного дерева потребует менее девяти сравнений!

Рисунок 5 Логическое дерево до утрамбовки (слева) и после (справа)

"Трамбовать" логические деревья оператора множественного выбора умеют практически все компиляторы - даже не оптимизирующие! Это увеличивает производительность, но затрудняет анализ откомпилированной программы. Взглянув еще раз на рис. 5 - левое несбалансированное дерево наглядно и интуитивно - понятно. После же балансировки (правое дерево) совсем запутанное.

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

Рассуждая от противного - все узлы логического дерева, правая ветка которых содержит одно или более гнезд, могут быть замещены на эту самую правую ветку без потери функциональности дерева, то данная конструкция представляет собой оператор switch. Правая ветка потому что оператор множественного выбора в "развернутом" состоянии представляет цепочку гнезд, соединенных левыми ветвями друг с другом, а на правых держащих case-обработчики, - вот и следует попытаться подцепить все правые гнезда на левую ветвь. Если это удается, значит, имеет место оператор множественного выбора, если нет – то с чем-то другим.

Рассмотрим обращение балансировки на примере следующего дерева (см. рис. 6-а). Двигаясь от левой нижней ветви, следует продолжать взбираться на дерево до тех пор, пока не встретится узел, держащий на своей правой ветви одно или более гнезд. В данном случае - это узел (a > 5). Если данный узел заменить его гнездами (a==7) и (a == 9) функциональность дерева не нарушиться! (см. рис. 6-б). Аналогично узел (a > 10) может быть безболезненно заменен гнездами (a > 96), (a == 96), (a == 22) и (a == 11), а узел (a > 96) в свою очередь - гнездами (a == 98), (a == 666) и (a == 777). В конце -концов образуется классическое switch-дерево, в котором оператор множественного выбора распознается с первого взгляда.

Рисунок 6-а Обращение балансировки логического дерева

Рисунок 6-б Обращение балансировки логического дерева

2.3 Сложные случаи балансировки или оптимизирующая балансировка

Для уменьшения высоты "утрамбовываемого" дерева хитрые трансляторы стремятся замещать уже существующие гнезда балансировочными узлами. Рассмотрим следующий пример: (см. рис. 7). Для уменьшения высоты дерева транслятор разбивает его на две половины - в левую идут гнезда со значениями меньшие или равные единицы, а в правую - все остальные. Казалось бы, на правой ветке узла (a > 1) должно висеть гнездо (a == 2), но это не так! Здесь видно узел (a >2), к левой ветки которого прицеплен case-обработчик :2. Вполне логично - если (a > 1) и !(a > 2), то a == 2!

Легко видеть, что узел (a > 2) жестко связан с узлом (a > 1) и работает на пару с последним. Нельзя выкинуть один из них, не нарушив работоспособности другого! Обратить балансировку дерева по описанному выше алгоритму без нарушения его функциональности невозможно! Отсюда может создаться мнение, что имеет место вовсе не оператор множественного выбора, а что-то другое.

Чтобы развеять это заблуждение придется предпринять ряд дополнительных шагов. Первое - у switch-дерева все case-обработчики всегда находятся на правой ветви. Нужно посмотреть - можно ли трансформировать дерево так, чтобы case-обработчик 2 оказался на левой ветви балансировочного узла? Оказывается, можно: заменив (a > 2) на (a < 3) и поменяв ветви местами (другими словами выполнив инверсию). Второе - все гнезда switch-дерева содержат в себе условия равенства, - смотрим: можно ли заменить неравенство (a < 3) на аналогичное ему равенство? Да, можно - (a == 2)!

Вот, после всех этих преобразований, обращение балансировки дерева удается выполнить без труда!

Рисунок 7 Хитрый случай балансировки

2.4 Ветвления в case-обработчиках.

В реальной жизни case-обработчики прямо-таки кишат ветвлениями, циклами и прочими условными переходами всех мастей. Как следствие - логическое дерево приобретает вид ничуть не напоминающий оператор множественного выбора. Идентифицировав case-обработчики, можно бы решить эту проблему, но их нужно идентифицировать!

За редкими исключениями, case-обработчики не содержат ветвлений относительно сравниваемой переменной. Действительно, конструкции "switch(a) …. case 666 : if (a == 666) …." или "switch(a) …. case 666 : if (a > 66) …." абсолютно лишены смысла. Таким образом, можно смело удалить из логического дерева все гнезда с условиями, не касающимися сравниваемой переменной (переменной коневого гнезда).

Если программист в порыве собственной глупости или стремлении затруднит анализ программы "впаяет" в case-обработчики ветвления относительно сравниваемой переменной, то оказывается, это ничуть не затруднит анализ! "Впаянные" ветвления элементарно распознаются и обрезаются либо как избыточные, либо как никогда не выполняющиеся. Например, если к правой ветке гнезда (a == 3) прицепить гнездо (a > 0) - его можно удалить, как не несущее в себе никакой информации. Если же к правой ветке того же самого гнезда прицепить гнездо (a == 2) его можно удалить, как никогда не выполняющееся - если a == 3, то заведомо a != 2!