折半查找和二叉排序樹

1.折半查找和二叉排序樹的時間性能分析：

•  從查找過程看，二叉排序樹與二分查找相似。就平均時間性能而言，二叉排序樹上的查找和二分查找差不多，但不完全一緻；
• 折半查找的性能分析可以用二叉判定樹來衡量，平均查找長度和最大查找長度都是O（logn）；
• 二叉排序樹的查找性能與資料的輸入順序有關，最好情況下的平均查找長度與折半查找相同，但最壞情況時，即形成單支樹時，其查找長度為O(n)。
• 折半查找的判定樹唯一，而二叉排序樹不唯一，相同的關鍵字其插入順序不同可能生成不同的二叉排序樹。

2.就維護表的有序性而言，二叉排序樹無需移動節點，隻需修改指針即可完成插入和删除操作，平均執行時間是O（logn）。二分查找的對象是有序順序表，若有插入和删除結點的操作，所花的代價是O（n）。

3.當有序表是靜态查找表時，宜用順序表作為其存儲結構，而采用二分查找實作其查找操作；若有序表是動态查找表，則應選擇二叉排序樹作為其邏輯結構。

4.折半查找過程所對應的判定樹是一棵平衡二叉樹：每次把一個數組從中間分割時，總是把數組分為結點數相差最多不超過1的兩個子數組，進而使得對應的判定樹的兩顆子樹高度差絕對值不超過1。