靜態(tài)查找表：只查找，不改變集合內(nèi)的數(shù)據(jù)元素。
一、順序查找（ Linear search，又稱線性查找 ）用逐一比較的辦法順序查找關(guān)鍵字。
1、順序查找時(shí)間復(fù)雜度：O(n)
2、順序查找平均查找長(zhǎng)度 ASL=(n+1)/2
二、折半查找前提是順序存儲(chǔ)，記錄有序。
思想：與記錄中間值比較，如果比中間值小去左邊查，否則去右邊查找，直到找到為止，區(qū)域內(nèi)沒(méi)記錄時(shí)查找失敗。
1、折半查找時(shí)間復(fù)雜度：O()
2、折半查找平均查找長(zhǎng)度? ASL=
動(dòng)態(tài)查找表：既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。
二叉排序樹(shù)滿足下列性質(zhì)
1）若左子樹(shù)不為空，則左子樹(shù)上的所有結(jié)點(diǎn)的值（關(guān)鍵字）都小于根節(jié)點(diǎn)的值；
2）若右子樹(shù)不為空，則右子樹(shù)上的所有結(jié)點(diǎn)的值（關(guān)鍵字）都大于根節(jié)點(diǎn)的值；
3）左、右子樹(shù)都分別為二叉排序樹(shù)。
二叉排序樹(shù)的查找思想
1）首先將給定的K值與二叉排序樹(shù)的根節(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較：若相等，則查找成功；
2）若給定的K值小于二叉排序樹(shù)的根節(jié)點(diǎn)的關(guān)鍵字：繼續(xù)在該節(jié)點(diǎn)的左子樹(shù)上進(jìn)行查找；
3）若給定的K值大于二叉排序樹(shù)的根節(jié)點(diǎn)的關(guān)鍵字：繼續(xù)在該節(jié)點(diǎn)的右子樹(shù)上進(jìn)行查找。
二叉排序樹(shù)總結(jié)
1）查找過(guò)程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；
2）中序遍歷此二叉樹(shù)，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）；
3）如果查找不成功，能夠方便地將被查元素插入到二叉樹(shù)的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。
