树型查找-二叉排序树

二叉排序树插入的一个结点一定是新添加的叶结点，即二叉排序树插入新结点时不会引起树的分裂组合
中序遍历二叉排序树可得一个有序序列
二叉排序树的查找路径是自顶向下的，其平均查找长度主要取决于树的高度
当二叉排序树插入的关键字有序时，二叉排序树会形成一个长链，此时深度最大
- 在此种情况下进行查找，有可能需要比较每个结点的关键字，超过总结点数的二分之一
当输入序列是一个有序序列时，构造的二叉排序树是一个单支树
- 当在n个结点的单支树中查找一个不存在的关键字值或最后一个结点的关键字值时，需要进行n次比较，此为最大比较次数
当二叉排序树的叶结点全部都在相邻的两层内时，深度最小
- 理想情况是从第一层到倒数第一层为满二叉树。
  - 类比完全二叉树，可得深度为（log2（n+1））向上取整