Binary Search Trees

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