LoginSignup
5

More than 5 years have passed since last update.

二分木を線型時間でリストにする4つの方法

Last updated at Posted at 2014-01-27

要素数nの二分木を最悪計算量O(n)でリストへと平坦化 (flatten) する方法を4つ紹介する.

二分木は次のものを使う.

definition
data Tree a = Leaf | Node (Tree a) a (Tree a)

実験する場合は,次を使うといいと思う.

experiment
lefttree, righttree, perfecttree :: Int -> Tree Int
lefttree 0 = Leaf
lefttree n = Node (lefttree (n-1)) n Leaf
righttree 0 = Leaf
righttree n = Node Leaf n (righttree (n-1))
perfecttree 0 = Leaf
perfecttree n = Node (perfecttree (div n 2)) n (perfecttree (div n 2))
bash
> length $ flatten $ righttree 100000
100000
> length $ flatten $ lefttree 100000
100000
> length $ flatten $ perfecttree 100000
131071

まずは愚直解.最悪計算量は,木が完全に左に偏っている場合で O(n^2).

naive
flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node l x r) = flatten l ++ [x] ++ flatten r

ではさっそく,最悪計算量がO(n)である実装を見ていこう.

1番目は,差分リストを使う方法.

dlist
flatten :: Tree a -> [a]
flatten t = toList (go t)
  where
    go :: Tree a -> DList a
    go Leaf = fromList []
    go (Node l x r) = go l ++* fromList [x] ++* go r

type DList a = [a] -> [a]
fromList :: [a] -> DList a
fromList xs = (xs ++)
toList :: DList a -> [a]
toList dxs = dxs []
(++*) :: DList a -> DList a -> DList a
(++*) = (.)

2番目は,蓄積変数を使う方法.本質的には差分リストを使う方法と変わらないが,オーソドックスなテクニックだといえる.山本和彦氏がTwitterで教えてくださった.

accum
flatten :: Tree a -> [a]
flatten t = go t []
  where
    go Leaf xs = xs
    go (Node l x r) xs = go l (x : go r xs)

3番目は,差分リストを脱関数化する方法.http://h2.jaguarpaw.co.uk/posts/demystifying-dlist/ に載っていた.

demystify
flatten :: Tree a -> [a]
flatten t = toList (go t)
  where
    go :: Tree a -> TList a
    go Leaf = fromList []
    go (Node l x r) = go l ++* fromList [x] ++* go r

data TList a = Tip [a] | Branch (TList a) (TList a)
fromList :: [a] -> TList a
fromList = Tip
toList :: TList a -> [a]
toList (Tip xs) = xs
toList (Branch (Tip xs) t) = xs ++ toList t
toList (Branch (Branch l r) t) = toList (Branch l (Branch r t))
(++*) :: TList a -> TList a -> TList a
(++*) = Branch

4番目は,不思議な方法.おそらく一番美しい方法.3番目をヒントに思い付いた.O(n)になることを確認してほしい.

wonder
flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node Leaf x t) = x : flatten t
flatten (Node (Node l x r) y t) = flatten (Node l x (Node r y t))

シンプルな問題でも本当に奥が深い.

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5