Tree 構造を利用した二分探索木(Ruby)
(※注記)以下のコードは未熟なので、二分探索木については(よろしければ)こちらをどうぞ。(2019/1/18)
- 作者: 川中真耶,杵渕朋彦,椎名俊輔
- 出版社/メーカー: アスキー・メディアワークス
- 発売日: 2012/05/30
- メディア: 大型本
- 購入: 5人 クリック: 34回
- この商品を含むブログ (6件) を見る
ここで実装した Tree 構造を使いました。
require './tree' class BinaryTree < Tree def change(node, oldchild, newchild) replace(@root, newchild) unless node if left(node) == oldchild replace(left(node), newchild) elsif right(node) == oldchild replace(right(node), newchild) else raise "No child." end end def left(node) #左の子供 get_children(node)[0] end def right(node) #右の子供 get_children(node)[1] end def insert(node) raise "Already newchild exists." if @node.include?(node) @node << node nd = @root loop do if node < nd if left(nd) nd = left(nd) else @lh[nd].children[0] = node @lh[node] = Branch.new(nd) return end else if right(nd) nd = right(nd) else @lh[nd].children[1] = node @lh[node] = Branch.new(nd) return end end end end def search(start, goal) return false unless start return true if start == goal return search(left(start)) if goal < start search(right(start)) end def self.build(ar) ar1 = ar.dup t = BinaryTree.new(ar1.shift) ar1.each {|node| t.insert(node)} t end end if __FILE__ == $0 ar = [3, 10, 1, 8, 5, 2, 6, 7, 4, 11, 9] p t = BinaryTree.build(ar) end