二分木

##### 🚨注意🚨

以下，Ruby入門二日目の**ド**素人がコード書いてます．

# 問題
Binary search treeをRubyで実装してください．

![bst gif](https://www.mathwarehouse.com/programming/images/binary-search-tree/optimal-binary-search-tree-from-sorted-array.gif)

# 解答例

## recursiveに書きましたという答え
```ruby
class Node
  # define instance variable `value` and its reader method
  attr_reader :value

  # define instance variable `left`, `right` and their read/write methods
  attr_accessor :left, :right

  # initializer
  def initialize(value = nil)
    @value = value
    @left = nil
    @right = nil
  end

end

class BinaryTree
  # root node represents one tree
  attr_accessor :root

  # initializer
  def initialize
    @root = Node.new(nil)
  end

  # insertion
  def insert(value)
    if @root.value
      self._insert(@root, value)
    else
      @root = Node.new(value) 
    end
  end
  def _insert(node, value)
    if value > node.value
      if node.right 
        _insert(node.right, value)
      else
        node.right = Node.new(value)
      end
    elsif value == node.value
      return node
    else # value < node.value
      if node.left 
        _insert(node.left, value)
      else
        node.left = Node.new(value)
      end
    end
  end

  # inorder traversal with recursive: left -> parent -> right
  def inorder
    self._inorder(self.root)
  end
  def _inorder(node)
    if node.nil?
      []
    else # left -> parent -> right
      left_wing = self._inorder(node.left)
      right_wing = self._inorder(node.right)
      return left_wing + [node.value] + right_wing
    end
  end

  # preorder traversal with recursive: parent -> left -> right
  def preorder
    self._preorder(self.root)
  end
  def _preorder(node)
    if node.nil?
      []
    else # parent -> left -> right
      [node.value] + self._preorder(node.left) + self._preorder(node.right)
    end
  end

  # postorder traversal without recursive: left -> right -> parent
  def postorder
    self._postorder(self.root)
  end
  def _postorder(node)
    if node.nil?
      []
    else # left -> right -> parent
      self._postorder(node.left) + self._postorder(node.right) + [node.value]
    end
  end

  # create tree from array
  def create_from_array(input_array)
    for element in input_array do
      self.insert element
    end
  end

  # inorder with stack
  def inorder_with_stack
    ret = []
    current = self.root
    stack = []
    flag = false
    while !flag
      if !current.nil?
        stack << current
        current = current.left
      else
        if stack.length > 0
          current = stack[stack.length-1]
          stack.delete_at(stack.length-1)
          ret << current.value
          current = current.right
        else
          flag = true
        end
      end
    end
    return ret
  end

end

##### script starts below #####
# create new binary tree
bst = BinaryTree.new

# create sample input
sample_array = []
(100).times do |i|
  sample_array << i
  # sample_array << rand(i)
end

puts "sample_array:\t" + sample_array.to_s
bst.create_from_array(sample_array)
puts "bst:\t\t" + bst.inorder.to_s
```

## iterativeに書きましたという答え

```ruby
class Node
  # define instance variable `value` and its reader method
  attr_reader :value

  # define instance variable `left`, `right` and their read/write methods
  attr_accessor :left, :right

  # initializer
  def initialize(value = nil)
    @value = value
    @left = nil
    @right = nil
  end

end

class BinaryTree
  # root node represents one tree
  attr_accessor :root

  # initializer
  def initialize
    @root = Node.new(nil)
  end

  # insertion
  def insert(value)
    if @root.value
      self._insert(@root, value)
    else
      @root = Node.new(value) 
    end
  end
  def _insert(node, value)
    current = node
    parent = nil
    if node.nil?
      return Node.new(value)
    end

    while current
      parent = current
      if value < current.value
        current = current.left
      else
        current = current.right
      end
    end
    if value < parent.value
      parent.left = Node.new(value)
    else
      parent.right = Node.new(value)
    end
    return node
  end

  # inorder traversal with recursive: left -> parent -> right
  def inorder
    self._inorder(self.root)
  end
  def _inorder(node)
    if node.nil?
      []
    else # left -> parent -> right
      left_wing = self._inorder(node.left)
      right_wing = self._inorder(node.right)
      left_wing + [node.value] + right_wing
    end
  end

  def inorder_iterative
    self._inorder_iterative(self.root)
  end
  def _inorder_iterative(node)
    ret = []
    current = node
    if node.nil?
      return
    end
    while current
      if current.left.nil? # 今注目している`current`より大きいノードが存在しない
        ret << current.value
        current = current.right # 右側を見に行く
      else # 今注目している`current`を根とする木の中でまだ小さい値が左にあるのでそっちを見に行く
        predecessor = current.left # `current`の一つ前のノード`predecessor`を探しに行く
        while predecessor.right && predecessor.right != current # `predecessor`の右側になんかあるなら，`current`と`predecessor`の間にまだ様子があるからそっちに移る
          predecessor = predecessor.right
        end
        if predecessor.right.nil? # `predecessor`の右側の子として`current`をメモっておく（あとで消す）
          predecessor.right = current
          current = current.left
        else
          predecessor.right = nil # 上節`if`でメモっておいた分を元に戻す
          ret << current.value
          current = current.right
        end
      end
    end
    ret
  end

  # preorder traversal with recursive: parent -> left -> right
  def preorder
    self._preorder(self.root)
  end
  def _preorder(node)
    if node.nil?
      []
    else # parent -> left -> right
      [node.value] + self._preorder(node.left) + self._preorder(node.right)
    end
  end

  # postorder traversal without recursive: left -> right -> parent
  def postorder
    self._postorder(self.root)
  end
  def _postorder(node)
    if node.nil?
      []
    else # left -> right -> parent
      self._postorder(node.left) + self._postorder(node.right) + [node.value]
    end
  end

  # create tree from array
  def create_from_array(input_array)
    for element in input_array do
      self.insert element
    end
  end
end

##### script starts below #####
# create new binary tree
bst = BinaryTree.new

# create sample input
sample_array = []
(10).times do |i|
  # sample_array << i
  sample_array << rand(1000)
end

puts "sample_array:\t" + sample_array.to_s
puts "bst:\t\t" + bst.inorder_iterative.to_s
```

# 学び

- 再帰 v.s.反復
- 末尾再帰

## 再帰 v.s. 反復
- 再帰も反復も「なんども同じような計算を行う」ための手法

- 反復
    - いわゆる`for`文
    - 「状態」を表現する変数（状態変数）を与え，「状態」を次々に変化させていく．状態変数が終了条件を満たした時に繰り返しを終える．
    - メモリ上にスタックフレームの列として「直前に実行したこと」の履歴が残らない
    - 状態変数が履歴の役割を果たすことになる

```go
// Iterativeに階乗を計算する
func factorial(n int) int {
    ret = 1
    for i := 1; i <= n; i++ { // `i`が状態変数
        ret = ret * i
    }
    return ret
}
```

- 再帰
    - 自分を自分で呼ぶ
    - どこに戻るかがスタック上に残っている
        - 直前に何をやっていたかがメモリ上に残っている
    - 計算自体を自分の次の関数に遅延させていく
    - 自分自身を自分自身で呼び出し続けるとは，スタックフレームに自分自身をどんどん積み上げていくことになる
    - 計算を遅延させるので，何らかの条件（Base condition）を満たした段階で値を返すようにしなければならない．つまり，関数内で「ある条件を満たした時に`return`する」ようにしていないといけない．

```go
// Recursiveに階乗を計算する
func factorial(n int) int {
    if n == 0 { // Base condition
        return 1
    }
    return n * factorial(n-1) // 自分で自分を呼び出している
}
```

## 末尾再帰
- 再帰的に呼び出**された**関数の返り値が，呼び出**し**側の関数の返り値にそのまま使われるような再帰のことを「末尾再帰」という．
- 末尾再帰の場合，（呼び出された側の関数の実行結果を待つことなく）呼び出し側のフレームを解放することができる
    - だって呼び出し側で何も操作しないから
    - 今`f`が`f'`（実体は`f`に等しい）を再帰的に呼び出した（つまり`f`が呼び出し側，`f'`が呼び出され側）とすると，もし末尾再帰なら，`f'`の返り値を，`f`をすっ飛ばして，`f`の呼び出し元に直接返せばいいので，`f`のスタックレームは不要になる
- 賢いコンパイラは末尾再帰に気がついて，無駄にスタックフレームを積まないように機械語コードを最適化してくれる

## 関数の末尾再帰化

```go
func sum(n int) int {
    if n == 1 {
        return 1
    } else {
        return n + sum(n-1)
    }
}
```

これは`return`の部分で，再帰的に呼び出された`sum`の返り値を計算に使っているので，末尾再帰になっていない．なので，`n`を大きくするとスタックが溢れてしまう．
この`sum`関数を末尾再帰化していきたい．
末尾再帰ってことは要するに「`return`するときに呼び出し側で作業するな」ということなので，本来呼び出し側でやりたかった処理（ここでは`n + sum(n-1)`」を呼び出され側に**押し込んでやればいい**．そうすることで，末尾再帰になる．

```go
func sum(n, result int) int {
    if n == 1 {
        return result + 1
    } else {
        return sum(n-1, result + n)
    }
}
```

この関数を`sum(10, 0)`として呼び出せば$0$から$10$までの和を求めることができるし，要するに次の関数と同じことになる．

```go
func sum(n int) int {
    m := 0
    for n != 1 {
        m = m + n
        n = n - 1
    }
    return m + 1
}
```

# 参考文献

- [Recursion vs. Looping in Python](https://hackernoon.com/recursion-vs-looping-in-python-9261442f70a5)
- [2016年度「プログラミング言語」配布資料 (9)](http://www.fos.kuis.kyoto-u.ac.jp/~igarashi/class/pl/09-rec-iter.html)