Help us understand the problem. What is going on with this article?

アルゴリズムとデータ構造の要点メモ 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

参考

二分探索木(データ構造)

要点

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

一回の比較で探索対象が半分になる。
- 節が根の左部分木や右部分木に偏ってしまうと、
線形探索と同じ 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を持たせたクソ実装になってしまった。
アンバランスな木にならないように配慮するとかは今後学ぶ。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away