二叉查找樹(shù)（二叉搜索樹(shù)或二叉排序樹(shù)）是一種數(shù)據(jù)結(jié)構(gòu)莱革。采用了圖的樹(shù)形結(jié)構(gòu)献丑。數(shù)據(jù)存儲(chǔ)于二叉查找樹(shù)的各個(gè)結(jié)點(diǎn)中悟民。
二叉查找樹(shù)的示例如下圖：結(jié)點(diǎn)中的數(shù)字就是存的數(shù)據(jù)厕氨。（這里以不存在相同的數(shù)字為例）
二叉查找樹(shù)性質(zhì)：
1.每個(gè)結(jié)點(diǎn)的值大于其左樹(shù)上任意結(jié)點(diǎn)的值
2.每個(gè)結(jié)點(diǎn)的值小于其右樹(shù)上任意結(jié)點(diǎn)的值
比如9大于其左樹(shù)上的3和8。
根據(jù)這兩個(gè)性質(zhì)可以得出結(jié)論：
二叉查找樹(shù)的最小結(jié)點(diǎn)從頂端開(kāi)始汹粤，往其左樹(shù)的末端尋找命斧。此處最小值是3。
二叉查找樹(shù)的最大結(jié)點(diǎn)從頂端開(kāi)始嘱兼，網(wǎng)右樹(shù)的末端尋找国葬。此處的最大值是28。
二叉樹(shù)添加數(shù)據(jù)：
假設(shè)往當(dāng)前二叉樹(shù)里面添加一個(gè)數(shù)據(jù)芹壕，比如添加數(shù)字1汇四。
先從頂端開(kāi)始比較：
因?yàn)?1 < 15 ,所以往左下位置繼續(xù)尋找
接下來(lái)和9比較，因?yàn)? < 9 踢涌，所以繼續(xù)往左下位置尋找
接下來(lái)和和3比較通孽，因?yàn)? < 3 ,所以繼續(xù)向左下位置尋找
最終左下沒(méi)有值了，得到的結(jié)果是
接下來(lái)操作再添加一位數(shù)字4
先將4和15比較4 < 15 ,往左樹(shù)尋找
4 < 9 ,再往左樹(shù)尋找睁壁，
4 > 3 ,往右樹(shù)尋找背苦，
4 < 8 ,將4添加到8的左樹(shù)位置，添加完成潘明。
二叉樹(shù)刪除數(shù)據(jù)
嘗試性刪除結(jié)點(diǎn)28行剂，
刪除結(jié)果如下圖
下面嘗試刪除帶子節(jié)點(diǎn)的結(jié)點(diǎn)8
刪除之后效果
下面刪除帶子樹(shù)的節(jié)點(diǎn)9
刪除之后，先將左樹(shù)上最大結(jié)點(diǎn)4放在被刪除的結(jié)點(diǎn)位置（這里樹(shù)的結(jié)構(gòu)沒(méi)有達(dá)到最優(yōu)解钉疫，那么還需要繼續(xù)遞歸調(diào)整結(jié)點(diǎn)的操作）
（備注說(shuō)明：將左樹(shù)中的最大結(jié)點(diǎn)和右樹(shù)中的最小結(jié)點(diǎn)放在9的原有置都可以）
當(dāng)前情況下將4放在該位置已經(jīng)是最優(yōu)解硼讽，因此不用再做調(diào)整。
數(shù)據(jù)查找：
查找數(shù)據(jù)也是從頂端開(kāi)始和被查找值的大小進(jìn)行對(duì)比牲阁，12 < 15 ,所以需要查找左樹(shù)。
12 > 4 ,查找右樹(shù)
到此查到結(jié)束壤躲。
時(shí)間計(jì)算
因?yàn)槎娌檎覙?shù)有前面兩個(gè)性質(zhì)城菊，所以在查找數(shù)據(jù)或者尋找合適添加數(shù)據(jù)位置時(shí)候，只要將其和現(xiàn)有數(shù)據(jù)比較大小碉克，就可以根據(jù)比較結(jié)果得知該往那邊移動(dòng)了凌唬。
比較的次數(shù)取決于樹(shù)的高度。所以如果結(jié)點(diǎn)數(shù)目為n,而且樹(shù)比較均衡漏麦，比較大小和移動(dòng)的次數(shù)最多就是log2n
因此時(shí)間復(fù)雜度為O（logn）客税。但是，如果樹(shù)的形狀朝單側(cè)縱向延伸撕贞，樹(shù)就變得很高更耻，此時(shí)的時(shí)間復(fù)雜度就變成了O（n）。
應(yīng)用
有很多以二叉查找樹(shù)為基礎(chǔ)的擴(kuò)展數(shù)據(jù)結(jié)構(gòu)捏膨。比如“平衡二叉查找樹(shù)”秧均。這種結(jié)構(gòu)可以修正形狀不均衡的樹(shù)食侮，讓其始終保持均衡的形態(tài)，以提高查找效率目胡。
雖然二叉查找樹(shù)中的一個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)锯七，但我們可以把子結(jié)點(diǎn)數(shù)擴(kuò)展為m.
像這種結(jié)點(diǎn)數(shù)可以自由設(shè)定，并且形狀均衡的樹(shù)叫做B樹(shù)誉己。
