二分搜索樹屬性
二分搜索樹的又名比較多多艇，有的叫二叉排序樹，也有的叫二叉查找樹像吻，或者有序二叉查找樹峻黍。是指一棵空樹或者具有下列性質(zhì)的二叉樹：
1.若任意節(jié)點的左子樹不空，則左子樹所有節(jié)點的值均小于它根節(jié)點的值拨匆；
2.若任意節(jié)點的右子樹不空姆涩，則右子樹所有節(jié)點的值均小于它根節(jié)點的值；
3.任意節(jié)點的左惭每、右子樹也分別為二叉查找樹骨饿；
4.沒有鍵值相等的節(jié)點。
它的查找台腥、插入和刪除的時間復(fù)雜度都等于樹高宏赘，期望值是O(logn)，最壞時間復(fù)雜度是O(n)览爵，比如樹退化成線性表置鼻。
（響應(yīng)讀者的建議镇饮，視頻動畫不放BGM了）
動畫
查找元素
二分搜索樹是為了實現(xiàn)快速查找而生的蜓竹，也支持快速添加和刪除一個數(shù)據(jù)。如何查找某個元素首先跟根節(jié)點去做比較，如果相等的話就返回俱济；如果待查元素要比根節(jié)點小嘶是，就進行左子樹遞歸查找；如果待查元素要比根節(jié)點大蛛碌，就進行右子樹的遞歸查找聂喇；如果查找到最后還沒有一個符合的元素，就返回null蔚携。
遞歸查找
遞歸查找的方式有很多希太，有層序遍歷、前序遍歷酝蜒、中序遍歷和后序遍歷誊辉。我這里就舉后面三個遍歷方式。
Code
如果代碼是下面這樣寫的亡脑，那它遍歷過程是怎么樣的堕澄？看下面視頻動畫。
視頻動畫：前序遍歷
視頻動畫：前中后遍歷
視頻動畫：前中后遍歷 前序
視頻動畫：前中后遍歷 中序
經(jīng)過中序遍歷得到的正好是一個升序序列霉咨。
視頻動畫：前中后遍歷 后序
如果不考慮升序蛙紫，后序遍歷能夠為二分搜索樹早點釋放內(nèi)存。
添加元素
對于二叉樹的添加和刪除元素途戒，使用鏈表存儲形式比較好操作的坑傅，如果使用數(shù)組形式存儲，刪除某一個有子樹的元素會引發(fā)一系列的位置改變棺滞，涉及到交換元素的位置裁蚁，性能也比鏈表的小。所以待會后面出現(xiàn)的偽代碼都以鏈表存儲形式去操作继准。
視頻動畫：添加元素
Code
刪除元素：刪除最小和最大的元素
刪除最小和最大的元素很簡單枉证，如果是刪除最小的元素，從二叉樹的頂點出發(fā)移必，一直遞歸它的左孩子室谚，直到某節(jié)點的左孩子為空，這時候這個節(jié)點就是最小的元素崔泵。刪除最大的元素也是一樣的秒赤，一直遞歸它的右孩子，直到某節(jié)點的右孩子為空憎瘸。
視頻動畫：刪除最小和最大的元素
刪除任意元素
如果刪除任意元素入篮，而這元素正好有左右子樹的，那該是怎么般呢幌甘？
1962年潮售，Hibbard提出了Hibbard Deletion的解決方法痊项。
看到Hibbard名字就想起來，我在希爾排序介紹過Hibbard增量序列酥诽，也把它相應(yīng)的公式通過代碼體現(xiàn)出來鞍泉，代替希爾增量序列去進行希爾排序，最壞時間復(fù)雜度也比希爾增量序列的要小肮帐。
回到刪除有左右子樹的元素咖驮，想想它的左右子樹也屬于二叉排序樹（也是二分搜索樹），它左子樹的最大值比它小训枢，它右子樹的最小值比它大托修。所以不管選擇左子樹的最大值還是選擇右子樹的最小值，替換掉要刪除的元素恒界，整個二叉樹都是符合二分搜索樹的規(guī)則诀黍。
視頻動畫：刪除任意元素
Code
支持重復(fù)元素的二分搜索樹
二分搜索樹有一個規(guī)則是：沒有鍵值相等的節(jié)點。那么就不建議把待添加的元素跳過值相等的節(jié)點仗处，到下一步繼續(xù)比較直到插入新的節(jié)點眯勾。比如我想插入23，插完之后上有23婆誓，下有23吃环，那查找就沒有意義了，也破壞了時間復(fù)雜度上的O(logn)洋幻。
建議就是在節(jié)點上加一個屬性：count郁轻。當(dāng)插入23的時候，count就可以自算++文留。這不僅滿足了沒有鍵值相等的規(guī)則好唯，也滿足時間復(fù)雜度的期望值。
Code
喜歡本文的朋友燥翅，微信搜索「算法無遺策」公眾號骑篙，收看更多精彩的算法動畫文章
