二元搜尋樹

說明

在二元樹中插入及搜尋數字。

當我們需要表示已排序的資料時，陣列並不是個理想的資料結構。

假設我們有個陣列 [1, 3, 4, 5]，接著加入 2，讓它變成 [1, 3, 4, 5, 2]。這下子我們又得把整個陣列重新排序！我們可以改善這種做法：只要為新元素騰出空間，變成 [1, nil, 3, 4, 5]，再把新元素放進我們騰出來的位置就行了。但這麼做仍然得把許多元素往後挪一個位置。

不過，二元搜尋樹處理已排序資料的效率就高得多。

二元搜尋樹由一連串相連的節點組成。每個節點包含一筆資料（例如數字 3）、一個名為left的變數，以及一個名為right的變數。left和right變數會指向nil或其他節點。由於這些節點底下還有其他節點，我們會說 left 和 right 變數指向子樹。左子樹中的所有資料都小於或等於目前節點的資料，而右子樹中的所有資料都大於目前節點的資料。

舉例來說，如果我們有個包含資料 4 的節點，並加入資料 2，我們的樹會長這樣：

  4
 /
2

接著如果加入 6，就會變成這樣：

  4
 / \
2   6

接著如果加入 3，就會變成這樣

   4
 /   \
2     6
 \
  3

而如果我們接著加入 1、5 和 7，就會變成這樣

      4
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7

提示

為了完成這道練習，你需要建立資料型態BST，並讓它擁有Eq和Show的實例，然後實作下列函式：

• bstLeft
• bstRight
• bstValue
• empty
• fromList
• insert
• singleton
• toList

你會發現檔案裡已經有佔位用的資料宣告和型別簽章，但定義這些函式、建立有意義的資料型態、newtype 或型別同義詞，全都得靠你自己喔。