Simple BST With Ruby

vang con

Init

1
2
3
4
5
6
7
class Node
  attr_accessor :left, :right, :value

  def initialize(val)
    @value = val
  end
end

Display Tree

1
2
3
4
5
def get_tree
  puts "#{value}\n"
  @left.get_tree() if @left
  @right.get_tree() if @right
end

Add Node

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
class Node
  attr_accessor :left, :right, :value

  def initialize(val)
    @value = val
  end

  def add(new_val)
    return if @value == new_val
    if(@value > new_val)
      add_left(new_val)
    else
      add_right(new_val)
    end
  end

  private

  def add_left(val)
    if(@left)
      @left.add(val)
    else
      @left = Node.new(val)
    end
  end

  def add_right(val)
    if(@right)
      @right.add(val)
    else
      @right = Node.new(val)
    end
  end

end

Check existing?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Node
  attr_accessor :left, :right, :value

  def initialize(val)
    @value = val
  end

  def include?(val)
    return true if(@value == val)

    if(@value > val)
      return false if !@left
      @left.include?(val)
    else
      return false if !@right
      @right.include?(val)
    end
  end
end

Update Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def update(current_value, new_value)
  if(@value == current_value)
    @value = new_value
    return true
  end

  if(@value > current_value)
    return false if !@left
    @left.update(current_value, new_value)
  else
    return false if !@right
    @right.update(current_value, new_value)
  end
end

Get Depth

1
2
3
4
def max_depth(root)
  return 0 if root.nil?
  return [max_depth(root.left), max_depth(root.right)].max + 1
end

Example

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Node
  attr_accessor :left, :right, :value

  def initialize(val)
    @value = val
  end

  def get_tree
    puts "#{value}\n"
    @left.get_tree() if @left
    @right.get_tree() if @right
  end

  def add(new_val)
    return if @value == new_val
    if(@value > new_val)
      add_left(new_val)
    else
      add_right(new_val)
    end
  end

  def include?(val)
    return true if(@value == val)

    if(@value > val)
      return false if !@left
      @left.include?(val)
    else
      return false if !@right
      @right.include?(val)
    end
  end

  def update(current_value, new_value)
    if(@value == current_value)
      @value = new_value
      return true
    end

    if(@value > current_value)
      return false if !@left
      @left.update(current_value, new_value)
    else
      return false if !@right
      @right.update(current_value, new_value)
    end
  end

  private

  def add_left(val)
    if(@left)
      @left.add(val)
    else
      @left = Node.new(val)
    end
  end

  def add_right(val)
    if(@right)
      @right.add(val)
    else
      @right = Node.new(val)
    end
  end

end

a = Node.new(5)
puts "#{a.value} | #{a.left ? a.left.value : nil} | #{a.right ? a.right.value : nil}"

a.add(2)
a.add(7)
a.add(9)

a.get_tree()

a.update(7, 6)

puts "#{a.value} | #{a.left ? a.left.value : nil} | #{a.right ? a.right.value : nil}"

a.get_tree()

b = a.right
puts "#{b.value} | #{b.left ? b.left.value : nil} | #{b.right ? b.right.value : nil}"