終於講到樹，快接近尾聲了(煙
二元搜尋圖(Binary Search Tree)是一種很高效的資料結構，先來看一下圖:

這是一個完全二元樹，以樹的定義，只會有一個root(根節點)，而且不會有cycle，否則就是圖了
每一個node可以有多個child，但在二元樹裡面，為了有效做搜尋，每一個node的child只會有兩個

說一下這資料結構要怎麼做搜尋
首先root的值是5，左邊的child node是3比5小，右邊的child node是9比5大，有沒有發現邏輯了，比目前的node值大的會放在右邊的child，比較小會放在左邊。
假如你要搜尋4，就會從root開始找，4比5小往左走，4比3大往右走，就會找到4了。二元樹每次都透過比大小，可以有效的排除掉另外一半的資料，是一個折半的搜尋算法，速度非常快，在完全的二元樹下，時間複雜度為O(log n)。

樹還有一個很有趣的地方，每一層的node加起來，等於上層數全部的node加總再減1，例如在第3層是4個node，那1、2層的加總就是4-1，大家可以算一下。

有完全二元樹，那有不完全嗎？

像這個例子，如果我們要搜尋20，就要一直往右找，沒有折半的效果，因為樹並不平衡，有一邊是歪的，在這個時候複雜度會從O(log n)升為O(n)，等同於鏈結。目前主要有兩種樹是會做平衡的，最壞的case在新增刪除修改都能維持在O(log n)，那就是AVL Trees 和 Red Black Trees。

簡單的介紹到這邊，明天會來實作Binary Search Tree～