目的
技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページにまとめる。
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を持たせたクソ実装になってしまった。
アンバランスな木にならないように配慮するとかは今後学ぶ。