BST

gistfile1.rb

class Node
  attr_accessor :key, :value, :left, :right, :size

  def initialize(key, value)
    @key = key
    @value = value
    @size = 0
    @left, @right = nil, nil
  end
end

class BST
  attr_accessor :root

  def initialize
    @root = nil
  end

  def minimum
    min(@root)
  end

  def maximum
    max(@root)
  end

  def count
    size(@root)
  end

  def fetch(key)
    get(@root, key)
  end

  def insert(key, value)
    @root = put(@root, key, value)
  end

  private

  def min(node)
    return nil if node.nil?
    return node if node.left.nil?

    min(node.left)
  end

  def max(node)
    return nil if node.nil?
    return node if node.right.nil?

    max(node.right)
  end

  def size(node)
    return 0 if node.nil?
    return node.size
  end

  def get(node, key)
    return nil if node.nil?

    if key > node.key
      get(node.right, key)
    elsif key < node.key
      get(node.left, key)
    else
      node.value
    end
  end

  def put(node, key, value)
    if node.nil?
      node = Node.new(key,value)
    # If specified key is less than current key, send to the left.
    elsif key < node.key
      node.left = put(node.left, key, value)
    # If specified key is greater than the current key, send to the right.
    elsif key > node.key
      node.right = put(node.right, key, value)
    # If keys match, update the value.
    elsif key == node.key
      node.value = value
   end
   # Track size of node.
   node.size = size(node.left) + size(node.right) + 1

   node
  end

end


require 'rspec'

describe BST do

 context '#maximum' do
   subject(:tree) { BST.new }

   before do
     tree.insert('c', 1)
     tree.insert('a', 26)
     tree.insert('d', 2)
     tree.insert('y', 25)
     tree.insert('b', 3)
   end

   it 'returns the correct max node' do
     expect(tree.maximum.key).to eq('y')
   end

 end

 context '#minimum' do
   subject(:tree) { BST.new }

   before do
     tree.insert('c', 1)
     tree.insert('a', 26)
     tree.insert('d', 2)
     tree.insert('y', 25)
     tree.insert('b', 3)
   end

   it 'returns the correct minimum node' do
     puts tree.root.inspect
     expect(tree.minimum.key).to eq('a')
   end

 end

 context '#get' do
   subject(:tree) { BST.new }

   context 'retrieves correct value' do
     before do
       tree.insert('a', 3)
       tree.insert('z', 5)
       tree.insert('j', 4)
     end

     it 'returns correct value for a' do
       expect(tree.fetch('a')).to eq(3)
     end

     it 'returns correct value for z' do
       expect(tree.fetch('z')).to eq(5)
     end

     it 'returns correct value for j' do
       expect(tree.fetch('j')).to eq(4)
     end
   end
 end

 context '#insert' do
   subject(:tree) { BST.new }

   context 'basic insert' do
     before { tree.insert('a', 1) }

     it 'should not be nil' do
       puts tree.inspect
       expect(tree.root).not_to eq(nil)
     end

     it 'sets root node to a' do
       expect(tree.root.key).to eq('a')
     end
   end

   context 'value update' do
     before do
       tree.insert('a', 1)
       tree.insert('b', 2)
       tree.insert('c', 3)
       tree.insert('c', 8)
     end

     it 'correctly updates key c value to 8' do
       expect(tree.root.right.right.value).to eq(8)
     end

   end

   context 'multiple insert' do
     before do
       tree.insert('a', 1)
       tree.insert('b', 2)
       tree.insert('c', 3)
       tree.insert('d', 4)
       tree.insert('z', 26)
       tree.insert('j', 10)
     end

     it 'sets root node to a' do
       expect(tree.root.key).to eq('a')
     end

     it 'sets right node to b' do
       expect(tree.root.right.key).to eq('b')
     end

     it 'sets right child of b to c' do
       expect(tree.root.right.right.key).to eq('c')
     end

     it 'sets right child of c to d' do
       expect(tree.root.right.right.right.key).to eq('d')
     end

     it 'sets right child of d to z' do
       expect(tree.root.right.right.right.right.key).to eq('z')
     end

     it 'sets left child of z to j' do
       expect(tree.root.right.right.right.right.left.key).to eq('j')
     end
   end

 end

end