アルゴリズムとデータ構造の要点メモ in ruby（二分探索木）

目的

技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページにまとめる。
Rubyでそそくさと実装できることを目的とする。

配列 https://qiita.com/tsnb/items/983c32d83331de1e0bea
連結リスト https://qiita.com/tsnb/items/3028ee788ff77ebaaa5e
スタック https://qiita.com/tsnb/items/e6901249629ef090ee8f
キュー https://qiita.com/tsnb/items/588afe675ad830ff1fc6
二分木 https://qiita.com/tsnb/items/8aa4e1ebb24d87919c40

参考

• https://programming-place.net/ppp/contents/algorithm/index.html#header (分かりやすいです、書いた人あざます、この記事をRuby用にまとめてるだけです)

二分探索木（データ構造）

要点

二分探索木は、二分木に対して、「左の子の値＜親の値＜右の子の値」という条件を持たせたもの。

一回の比較で探索対象が半分になる。

• 節が根の左部分木や右部分木に偏ってしまうと、
  線形探索と同じ O(n) にまで効率が落ち込む
• O(log n)に近い

アルゴリズム

実装

• bsearchで二分探索、辿ったNodeのリストをlistで見せる
• bst_addで木にNodeを追加
• bst_delで木からNode削除、削除したNodeの親と、削除したNodeの左の子をつなぐ

class Node
  attr_accessor :val, :left, :right

  def initialize(val)
    @val = val
    @left = nil
    @right = nil
  end

  def add_left(val)
    self.left = Node.new(val)
  end

  def add_right(val)
    self.right = Node.new(val)
  end
end

class BinarySearchTree
  attr_reader :head, :list

  def initialize(val)
    @head = Node.new(val)
    @list = []
    @queue = []
  end

  def bst_add(val)
    @list = []
    node, type, _ = search(@head, val)
    node.add_left(val) if type == :left
    node.add_right(val) if type == :right
  end

  def bst_del(val)
    @list = []
    node, _, parent = search(@head, val)
    if node.val == val
      parent.left = node.left if parent.left == node
      parent.right = node.left if parent.right == node
    end
  end

  def bsearch(val)
    @list = []
    node, _, _ = search(@head, val)
    node.val == val
  end

  def bfs
    traverse(@head)
  end

private
  def traverse(node)
    return @list if node.nil?

    @list << node.val
    @queue << node.left if !!node.left
    @queue << node.right if !!node.right
    node = @queue.shift
    traverse(node)
  end

  def search(node, val, parent=nil)
    @list << node.val
    if val <= node.val
      return node, :left, parent if node.left.nil?
      search(node.left, val, node)
    else
      return node, :right, parent if node.right.nil?
      search(node.right, val, node)
    end
  end
end

bt = BinarySearchTree.new(12)
bt.head.add_left(9)
bt.head.left.add_left(3)
bt.head.left.add_right(11)
bt.head.add_right(25)
bt.head.right.add_left(18)
bt.head.right.add_right(27)

irb(main):207:0> bt = BinarySearchTree.new(12)
=> #<BinarySearchTree:0x00007feaf7164510 @head=#<Node:0x00007feaf71644e8 @val=12, @left=nil, @right=nil>, @list=[], @queue=[]>
irb(main):208:0> bt.head.add_left(9)
=> #<Node:0x00007feaf7157388 @val=9, @left=nil, @right=nil>
irb(main):209:0> bt.head.left.add_left(3)
=> #<Node:0x00007feaf714c730 @val=3, @left=nil, @right=nil>
irb(main):210:0> bt.head.left.add_right(11)
=> #<Node:0x00007feaf7136318 @val=11, @left=nil, @right=nil>
irb(main):211:0> bt.head.add_right(25)
=> #<Node:0x00007feaf7118278 @val=25, @left=nil, @right=nil>
irb(main):212:0> bt.head.right.add_left(18)
=> #<Node:0x00007feaf70f6ab0 @val=18, @left=nil, @right=nil>
irb(main):213:0> bt.head.right.add_right(27)
=> #<Node:0x00007feaf7871f88 @val=27, @left=nil, @right=nil>
irb(main):217:0> bt.bst_add(4)
=> #<Node:0x00007feaf78ceee0 @val=4, @left=nil, @right=nil>
irb(main):218:0> bt.bsearch(4)
=> true
irb(main):219:0> bt.list
=> [12, 9, 3, 4]
irb(main):220:0> bt.bst_del(4)
=> nil
irb(main):222:0> bt.bsearch(4)
=> false
irb(main):223:0> bt.list
=> [12, 9, 3]

感想

削除が難しい気がする、無理やりsearchに親Nodeを持たせたクソ実装になってしまった。
アンバランスな木にならないように配慮するとかは今後学ぶ。