Skip to content

Instantly share code, notes, and snippets.

@mathiasjakobsen
Created February 3, 2016 20:34
Show Gist options
  • Save mathiasjakobsen/6fe4cf7da9e7c606f1c8 to your computer and use it in GitHub Desktop.
Save mathiasjakobsen/6fe4cf7da9e7c606f1c8 to your computer and use it in GitHub Desktop.
An implementation of a binary search tree data structure, in Ruby.
module BinarySearchTree
class Node
attr_reader :value
attr_accessor :left, :right, :count
def initialize(v)
@value = v
@count = 1
end
def insert(v)
case value <=> v
when 1 then insert_left(v)
when -1 then insert_right(v)
when 0 then @count += 1
end
end
def to_a
left.to_a + Array.new(@count, value) + right.to_a
end
def min
left.nil? ? value : left.min
end
def max
right.nil? ? value : right.max
end
private
def insert_left(v)
left ? left.insert(v) : @left = Node.new(v)
end
def insert_right(v)
right ? right.insert(v) : @right = Node.new(v)
end
end
end
# Example:
tree = BinarySearchTree::Node.new(100)
tree.insert(35)
tree.insert(60)
tree.insert(234)
tree.insert(60)
puts "Min.: #{tree.min}\n" # => 35
puts "Max.: #{tree.max}\n" # => 234
puts "Sorted:\n"
puts tree.to_a # => 35, 60, 60, 100, 234
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment