binary_search_tree.rb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Binary search tree for numbers
class Bst
  def initialize(root)
    @left = nil
    @right = nil
    @data = root
  end

  def insert(value)
    insert_side(value <= @data ? :left : :right, value)
  end

  def each
    # Iterate over the entire tree from L-R
    if block_given?
      @left.each { |x| yield(x) } if @left
      yield data
      @right.each { |x| yield(x) } if @right
    else
      enum_for(:each) { size }
    end
  end

  attr_reader :left, :right, :data

  private

  def insert_side(side, value)
    # Insert into a subtree
    if (subtree = instance_variable_get("@#{side}"))
      subtree.insert(value)
    else
      instance_variable_set "@#{side}", Bst.new(value)
    end
  end
end

Comments


You're not logged in right now. Please login via GitHub to comment