二叉排序樹的查找操作心得？

在計算機(jī)科學(xué)中，二叉樹是每個節(jié)點(diǎn)最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。 二叉排序樹（Binary Sort Tree）又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。 二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

(充分必要條件) （1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；

（3）左、右子樹也分別為二叉排序樹；

（4）沒有鍵值相等的節(jié)點(diǎn)。 每個結(jié)點(diǎn)的C(i)為該結(jié)點(diǎn)的層次數(shù)。

最壞情況下，當(dāng)先后插入的關(guān)鍵字有序時，構(gòu)成的二叉排序樹蛻變?yōu)閱沃洌瑯涞纳疃葹槠淦骄檎议L度(n+1)/2(和順序查找相同），最好的情況是二叉排序樹的形態(tài)和折半查找的判定樹相同，其平均查找長度和log 2 (n)成正比。