一直很想寫一個關于樹結構的專題，再一個就是很多初級點的碼農會認為樹結構無用論，其實歸根到底還是不清楚樹的實際用途。
一：場景：
1：現狀
前幾天我的一個大學同學負責的網站出現了嚴重的性能瓶頸，由于業務是寫入和讀取都是密集型，如果做緩存，時間間隔也隻能在30s左
右，否則就會引起客戶糾紛，是以同學也就沒有做緩存，通過測試發現慢就慢在資料讀取上面，總共需要10s，天啊...原來首頁的加載關聯
到了4張表，而且表資料中最多的在10w條以上，可以想象4張巨大表的關聯，然後就是排序+範圍查找等等相關的條件，讓同學抓狂。
2：我個人的提供解決方案
① 讀取問題
既然不能做緩存，那沒辦法，我們需要自己維護一套”記憶體資料庫“，資料如何組織就靠我們的算法功底了，比如哈希适合等于性的查找，
樹結構适合”範圍查找“，lucene适合字元串的查找，我們在添加和更新的時候同時維護自己的記憶體資料庫，最終杜絕表關聯，老同學，還
是先應急，把常用的表灌倒記憶體，如果真想項目好的話，改架構吧...
② 添加問題
或許你的add操作還沒有達到瓶頸這一步，如果真的達到了那就看情況來進行”表切分“，”資料庫切分“吧，讓使用者的add或者update
操作分流，雖然做起來很複雜，但是沒辦法，總比使用者糾紛強吧，可對...
二：二叉查找樹
正式切入主題，從上面的說明我們知道了二叉樹非常适合于範圍查找，關于樹的基本定義，這裡我就預設大家都知道，我就直接從
查找樹說起了。
1：定義
查找樹的定義非常簡單，一句話就是左孩子比父節點小，右孩子比父節點大，還有一個特性就是”中序周遊“可以讓結點有序。
2：樹節點
為了具有通用性，我們定義成泛型模闆，在每個結點中增加一個”資料附加域”。
3：添加
根據查找樹的性質我們可以很簡單的寫出add的代碼，一個一個的比呗，最終形成的效果圖如下
這裡存在一個“重複節點”的問題，比如說我在最後的樹中再插入一個元素為15的結點，那麼此時該怎麼辦，一般情況下，我們最好
不要在樹中再追加一個重複結點，而是在“重複節點"的附加域中進行”+1“操作。
4:範圍查找
這個才是我們使用二叉樹的最終目的，既然是範圍查找，我們就知道了一個”min“和”max“，其實實作起來也很簡單，
第一步：我們要在樹中找到min元素，當然min元素可能不存在，但是我們可以找到min的上界，耗費時間為o(logn)。
第二步：從min開始我們中序周遊尋找max的下界。耗費時間為m。m也就是比對到的個數。
最後時間複雜度為m+logn，要知道普通的查找需要o(n)的時間，比如在21億的資料規模下，比對的元素可能有30個，那麼最後
的結果也就是秒殺和幾個小時甚至幾天的巨大差異，後面我會做實驗說明。
5：删除
對于樹來說，删除是最複雜的，主要考慮兩種情況。
<1>單孩子的情況
這個比較簡單，如果删除的節點有左孩子那就把左孩子頂上去，如果有右孩子就把右孩子頂上去，然後打完收工。
<2>左右都有孩子的情況。
首先可以這麼想象，如果我們要删除一個數組的元素，那麼我們在删除後會将其後面的一個元素頂到被删除的位置，如圖
那麼二叉樹操作同樣也是一樣，我們根據”中序周遊“找到要删除結點的後一個結點，然後頂上去就行了，原理跟"數組”一樣一樣的。
同樣這裡也有一個注意的地方，在add操作時，我們将重複元素的值追加到了“附加域”，那麼在删除的時候，就可以先判斷是
不是要“-1”操作而不是真正的删除節點，其實這裡也就是“懶删除”，很有意思。
三：測試
假如現在我們有一張user表，我要查詢"2012/7/30 4:30:00"到"2012/7/30 4:40:00"這個時間段登陸的使用者，我在txt中生成一個
33w的userid和time的資料，看看在33w的情況下讀取效率如何...
比普通的dictionary效率還僅僅是快11倍，從數量級來說還不是非常明顯，為什麼說不是非常明顯，這是因為普通的查找樹的時間複雜度
不是嚴格的log(n)，在最壞的情況下會出現“連結清單”的形式，複雜度退化到o(n)，比如下圖。
不過總會有解決辦法的，下一篇我們繼續聊如何旋轉，保持最壞複雜度在o(logn)。