在 "資料結構" 系列文章裡寫過了 Binary search ，也寫過了 Tree．Binary search 能幫助我們在一個 "排序" 好的資料序列做快速的資料尋找．Tree 提供我們一個資料儲存 (放置) 的結構，當這兩個碰在一起時，產生了一個相當有用的資料結構.
Binary Search Tree 的發明比起我和絕大部份的讀者的都還要來的老，它出現在 1960 年代，在那個電腦硬體仍不太發達的年代，這個超級有用的資料結構就被發明出來了．誠如之前談的 binary search 內容，當你要進行 binary search 時，有一個很重要的前提就是被尋找的資料需要以某種排序好的順序存在，不論是從小排到大，從大排到小，或是從中排到小，再排中排到大，只要是資料依照某種屬性而排序好，就可以進行 binary search. 它的尋找資料的時間複雜度也在前面文章提過了，是 O (log N) 的複雜度，因為每一次尋找都可以捨棄掉一半非尋找目標的資料，這對尋找是個很大的幫助．然後，別忘了剛剛說的前題，資料必需是以某種方式排序好的．若你要在一堆沒有排序好的資料，把它排序，再執行 binary search 來找資料的話，這顯然有點過頭了，因為光是較快的排序都要花費 O(nlogn) 時間．因此在使用 binary search 之前，資料已是排序好的方式存在則能馬上使用 binary search，
當要讓資料以某種排序的方式建立起來時，可想而知，在建立的過程中可能要花費較多的時間，畢竟這不是隨便把資料加上去就好，而是要找到一個適當的位置才能加上去，以維持排序的狀態．你可以想像一個 integer single link list ，當你要加資料進去時，你得找到適當的位置並執行 insert 的動作，如下圖所示:
因此，只要我們能找一個適合的資料結構將資料依排序的目標建立起來，binary search 就可以派上用場. 在 Tree 的應用裡面，有個基本的結構叫 binary tree，也就是每個樹節點除了資料本身的空間外，還有另外兩個空間，一個是指向左邊節點的空間，另一個是指向右邊節點的空間. Binary tree 本身並不涉及任何資料排序的概念，但若我們為它加上一個限制，資料大的往右邊節點方向去建立，而資料小的往左邊節點方向建立，那麼這個 binary tree 便存在了排序的特性，如下圖所示，在任一個樹節點上，若左邊存在一個節點，則左邊節點的值將比較小，同理，右邊節點的值將比較大.
當 binary tree 加上了 "順序" 的特性時，這時就稱它為 binary search tree. 當尋找資料的動作發生時，從 root 開始出發，假設我們在上圖的 binary tree 上找 44，我們會在 root node 往右邊走，因為 44 > 11．以此類推，只要經過兩個樹楖點，我們便能找到 44. 如前面所說，這個動作的時間複雜度是 O(logn). 在大部份的應用裡，這個速度已經夠快了．
此時，你可能會發現在 binary search tree 要找資料時, root 的值是很重要的，因為你可能會看到如下圖的情況,
如上圖，倘若我們選到了一個不適合的值來當 root 時，此時 binary search tree 就長 "歪" 了．所謂的歪並不是壞掉的意思，而是大量傾向某一邊造成不平衡的情況．所謂的不平衡的意思就是某一樹節點左邊的 subtree 和右邊的 subtree 在高度上有大的落差．這會造成搜尋成本的不平均．比如，若你要找 44，它剛好是 root，所以一下子就找到了，若你要找 7，中間要經過 44 -> 33 -> 11 -> 6 ，最後到 7，若是你要找 11，中間經過 44 -> 33 就到 11. 所以，每個節點被找到的成本存在的大差異，因為我們稱之為不平衡的樹．這是我們希望能避免的情況，畢竟你希望的是每一個資料在被尋找時，每個資料被找到的時間成本和平均成本是很接近的，這樣才是公平．倘若資料本身需要不公平的情況，那就另當別論了.
Binary search tree 幫助我們將資料能用某一種順序的方式儲存起來，並且在尋找時也能達成 binary search 的效果．有些程式語言的程式庫裡都會提到這一個好用的資料結構，例如 C++ 的 map 就是典型的 binary search tree 實作. 如果你常用的程式語言裡沒有提供 binary search tree 的實作，我強烈建議你應該要在網路上找找是否有其他人做好成熟度夠高的實作，因為 binary search tree 的應用實在很多而且很好用. 當然 binary search tree 並無法為你自動達成 "平衡"，所以才會有其他的資料結構產生用來解決這個平衡的事情，如 AVL tree, red back tree, B tree 等等. AVL tree, red black tree, B tree 也算是蠻有用的資料結構，不光是學術價值，其工業應用價值也是頗高，以後會寫文章來介紹它們.
