すごいH本 part48

二分探索木を実装する

• 1つの要素が2つの子要素へのポインタを持つ
• 左の子は親より小さい
• 右の子は親より大きい
• それぞれの子要素は 0 or 1 or 2 個の要素を持つ

二分探索木はある要素の左側はその要素より小さく、 右側はその要素より大きいということが保証されている。

Data.Set や Data.Map が提供する Set や Map も木構造を使って実装されている。 ただの二分探索木ではなく、平衡二分探索木を使って実装されている。 平衡二分探索木は左右の要素の深さが大体同じになっている。

これを代数データ型で表現する。

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

木を作る関数を実装する

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
    | x == a = Node x left right
    | x < a  = Node a (treeInsert x left) right
    | x > a  = Node a left (treeInsert x right)

再帰で位置を調査していく。

要素が木に属しているか判定する関数を実装する

treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
    | x == a = True
    | x < a  = treeElem x left
    | x > a  = treeElem x right

テスト用の木を作る

*Main> let nums = [8,6,4,1,7,3,5]
*Main> let numsTree = foldr treeInsert EmptyTree nums
*Main> numsTree
Node 5 <- 実際には一行で表示される
  (Node 3
    (Node 1 EmptyTree EmptyTree)
    (Node 4 EmptyTree EmptyTree)
  )
  (Node 7
    (Node 6 EmptyTree EmptyTree)
    (Node 8 EmptyTree EmptyTree)
  )

値が木に含まれているかを判定する

*Main> 8 `treeElem` numsTree
True
*Main> 100 `treeElem` numsTree
False
*Main> 1 `treeElem` numsTree
True

マジでなんでも作れるとのこと

所感

問題を分解して基底部を見つけたりすることがとても難しく感じる。自分では頭が足りず全くできる気がしない。

すごいHaskellたのしく学ぼう！