5.6 降低判定树的高度（2）
图5-9为代码清单5-18的结构图，从图中可以发现，这棵树的左右两侧并不平衡，而是两个if else结构。由于判断较少，平衡后的效果并不明显，且进行树平衡的效率明显低于if else。这时，编译器采取的策略是，当树中的叶子节点数小于等于3时，就会转换形成一个if else 结构。
当向左子树中插入一个叶子节点10000时，左子树叶子节点数大于4。此时if else的转换已经不适合了，优先查看是否可以匹配有序线性优化、非线性索引表优化，如果可以，则转换为相应的优化。在不符合以上两个优化规则的情况下，就做成平衡树。
在Release版下，使用IDA查看编译器是如何优化的。树结构流程图如图5-10所示。
 |
| 图5-10 树结构流程图 |
图5-10是从IDA中提取出来的，根据流程走向可以看出，有一个根节点，左边的多分支流程结构很像一个switch，而右边则是一个多次比较判断，和if else类似。进一步观察汇编代码，如代码清单5-19所示。
代码清单5-19 判定树结构片段1—Release版
- .text:00401018 mov eax, [esp+0Ch+var_4]
- ; 平衡scanf的参数
- .text:0040101C add esp, 8
- ; eax中保存着switch语句的参数，与35 比较
- .text:0040101F cmp eax, 35
- ; 大于35跳转到标号short loc_401080处
- .text:00401022 jg short loc_401080
- ; 等于35跳转到标号short loc_401071处
- .text:00401024 jz short loc_401071
- ; 用eax加-2，进行下标平衡
- .text:00401026 add eax, 0FFFFFFFEh ; switch 9 cases
- ; 比较最大case值，之前进行了减2的对齐下标操作
- ; 这里的比较数为8，考察对齐下标操作后，说明这里的最大case值为10
- .text:00401029 cmp eax, 8
- ; 大于8跳转到标号short loc_401093处
- ; IDA已经识别出这是个default分支
- .text:0040102C ja short loc_401093 ; default
- ; 看到这种4字节的相对比例因子寻址方式，之前又进行了下标判断比较，
- ; 可以肯定这个off_4010D0标号的地址为case地址表
- .text:0040102E jmp ds:off_4010D0[eax*4] ; switch jump
判定树中的case地址表如图5-11所示。
 |
| 图5-11 判定树中的case地址表—Release版 |