Binary Search Trees(BST)

• Array vs. Tree
  1.Array
  Search table：為一個ordered map，用array來實現
  search : O(logn)
  insert : O(n)
  delete : O(n)

  -->因為插入跟刪除都要搬裡面的元素，需要O(n)
  2.Tree
  特性：左子樹的key<=中間的root<=右子樹的key
  註：若用inorder traversal，一定為由小排到大

• Search in BST
  演算法：若要搜尋的字比node小，往左子樹走；反之，往右子樹走，直到找到或碰到external node

• Insertion in BST
  與搜尋差不多，直到leaf則放入

  -->worse case與高度成正比，而如何讓tree的高度越小越好呢-->AVL Tree

• Deletion in BST
  1.此node只有一個子樹
  直接把子樹接上
  2.有兩個子樹
  將successor接上
  -->若還有右子樹

      -->** 直接取代拿出的node**
  

• Performance
  space : O(n)
  method : O(h)
  h要看樹的形狀，worse case : O(n)、best case : O(logn)