二分搜索樹(shù)屬性
二分搜索樹(shù)的又名比較多，有的叫二叉排序樹(shù)，也有的叫二叉查找樹(shù)，或者有序二叉查找樹(shù)。是指一棵空樹(shù)或者具有下列性質(zhì)的二叉樹(shù)：
1.若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)所有節(jié)點(diǎn)的值均小于它根節(jié)點(diǎn)的值；
2.若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)所有節(jié)點(diǎn)的值均小于它根節(jié)點(diǎn)的值；
3.任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)；
4.沒(méi)有鍵值相等的節(jié)點(diǎn)。
它的查找、插入和刪除的時(shí)間復(fù)雜度都等于樹(shù)高，期望值是O(logn)，最壞時(shí)間復(fù)雜度是O(n)，比如樹(shù)退化成線(xiàn)性表。
（響應(yīng)讀者的建議，視頻動(dòng)畫(huà)不放BGM了）
動(dòng)畫(huà)
查找元素
二分搜索樹(shù)是為了實(shí)現(xiàn)快速查找而生的，也支持快速添加和刪除一個(gè)數(shù)據(jù)。如何查找某個(gè)元素首先跟根節(jié)點(diǎn)去做比較，如果相等的話(huà)就返回；如果待查元素要比根節(jié)點(diǎn)小，就進(jìn)行左子樹(shù)遞歸查找；如果待查元素要比根節(jié)點(diǎn)大，就進(jìn)行右子樹(shù)的遞歸查找；如果查找到最后還沒(méi)有一個(gè)符合的元素，就返回null。
遞歸查找
遞歸查找的方式有很多，有層序遍歷、前序遍歷、中序遍歷和后序遍歷。我這里就舉后面三個(gè)遍歷方式。
Code
如果代碼是下面這樣寫(xiě)的，那它遍歷過(guò)程是怎么樣的？看下面視頻動(dòng)畫(huà)。
視頻動(dòng)畫(huà)：前序遍歷
視頻動(dòng)畫(huà)：前中后遍歷
視頻動(dòng)畫(huà)：前中后遍歷 前序
視頻動(dòng)畫(huà)：前中后遍歷 中序
經(jīng)過(guò)中序遍歷得到的正好是一個(gè)升序序列。
視頻動(dòng)畫(huà)：前中后遍歷 后序
如果不考慮升序，后序遍歷能夠?yàn)槎炙阉鳂?shù)早點(diǎn)釋放內(nèi)存。
添加元素
對(duì)于二叉樹(shù)的添加和刪除元素，使用鏈表存儲(chǔ)形式比較好操作的，如果使用數(shù)組形式存儲(chǔ)，刪除某一個(gè)有子樹(shù)的元素會(huì)引發(fā)一系列的位置改變，涉及到交換元素的位置，性能也比鏈表的小。所以待會(huì)后面出現(xiàn)的偽代碼都以鏈表存儲(chǔ)形式去操作。
視頻動(dòng)畫(huà)：添加元素
Code
刪除元素：刪除最小和最大的元素
刪除最小和最大的元素很簡(jiǎn)單，如果是刪除最小的元素，從二叉樹(shù)的頂點(diǎn)出發(fā)，一直遞歸它的左孩子，直到某節(jié)點(diǎn)的左孩子為空，這時(shí)候這個(gè)節(jié)點(diǎn)就是最小的元素。刪除最大的元素也是一樣的，一直遞歸它的右孩子，直到某節(jié)點(diǎn)的右孩子為空。
視頻動(dòng)畫(huà)：刪除最小和最大的元素
刪除任意元素
如果刪除任意元素，而這元素正好有左右子樹(shù)的，那該是怎么般呢？
1962年，Hibbard提出了Hibbard Deletion的解決方法。
看到Hibbard名字就想起來(lái)，我在希爾排序介紹過(guò)Hibbard增量序列，也把它相應(yīng)的公式通過(guò)代碼體現(xiàn)出來(lái)，代替希爾增量序列去進(jìn)行希爾排序，最壞時(shí)間復(fù)雜度也比希爾增量序列的要小。
回到刪除有左右子樹(shù)的元素，想想它的左右子樹(shù)也屬于二叉排序樹(shù)（也是二分搜索樹(shù)），它左子樹(shù)的最大值比它小，它右子樹(shù)的最小值比它大。所以不管選擇左子樹(shù)的最大值還是選擇右子樹(shù)的最小值，替換掉要?jiǎng)h除的元素，整個(gè)二叉樹(shù)都是符合二分搜索樹(shù)的規(guī)則。
視頻動(dòng)畫(huà)：刪除任意元素
Code
支持重復(fù)元素的二分搜索樹(shù)
二分搜索樹(shù)有一個(gè)規(guī)則是：沒(méi)有鍵值相等的節(jié)點(diǎn)。那么就不建議把待添加的元素跳過(guò)值相等的節(jié)點(diǎn)，到下一步繼續(xù)比較直到插入新的節(jié)點(diǎn)。比如我想插入23，插完之后上有23，下有23，那查找就沒(méi)有意義了，也破壞了時(shí)間復(fù)雜度上的O(logn)。
建議就是在節(jié)點(diǎn)上加一個(gè)屬性：count。當(dāng)插入23的時(shí)候，count就可以自算++。這不僅滿(mǎn)足了沒(méi)有鍵值相等的規(guī)則，也滿(mǎn)足時(shí)間復(fù)雜度的期望值。
Code
喜歡本文的朋友，微信搜索「算法無(wú)遺策」公眾號(hào)，收看更多精彩的算法動(dòng)畫(huà)文章
