Jul 16 2016
There's nothing like implementing some data structures on a Friday night! In my ongoing pursuit of shoring up my CS basics, I decided to take some time tonight reading up on Binary Search Trees, as many interview gotchas that I hear of seem to involve them. This is a fairly simple implementation with only the size, get, and put methods, but its a start.
class BinarySearchTree
attr_reader :root
def initialize(key, value)
@root = Node.new(key,value)
end
def size(node)
node.nil? ? 0 : size(node.left) + size(node.right) + 1
end
def get(node,key)
return nil if node.nil?
if node.key == key
node
else
key < node.key ? get(node.left, key) : get(node.right, key)
end
end
def put(node, key, value)
if node.key == key
puts "Changed Value of Node #{key} to #{value}"
return node.value = value
end
if key < node.key
if node.left
put(node.left,key,value)
else
puts "Added a new node to the left of #{node} with key #{key}, value #{value}"
node.left = Node.new(key,value)
end
else
if node.right
put(node.right,key,value)
else
puts "Added a new node to the right of #{node} with key #{key}, value #{value}"
node.right= Node.new(key,value)
end
end
end
class Node
attr_accessor :left, :right, :key, :value
def initialize(key, value)
@key = key
@value = value
end
end
end
And to try it out in the wild, heres a little implementation script.
nums = (1..100000).to_a.shuffle
bst = BinarySearchTree.new(nums.pop, 5)
b = bst.root
until nums.empty? do
bst.put(b, nums.pop, (1..9).to_a.sample)
end
Lets benchmark searching for a number in this tree we made with searching for one in an array to see the benefit of BSTs.
require 'benchmark'
nums = (1..100000).to_a.shuffle # need to remake as we destroyed it via pop
Benchmark.bm do |benchmark|
benchmark.report("array search"){ (1..10000).each {|n| nums.include? n } }
benchmark.report("binary tree "){ (1..10000).each {|n| bst.get(b, n) } }
end
user system total real
array search 3.090000 0.000000 3.090000 ( 3.102407)
binary tree 0.040000 0.000000 0.040000 ( 0.038214)
Pretty cool, that is quite a lot faster! Binary Trees are able to query in 2 ln N time, which is about 1.39 lg N.
-JM