diff --git a/lib/puppet/rb_tree_map.rb b/lib/puppet/rb_tree_map.rb
index 0140066e2..f65981476 100644
--- a/lib/puppet/rb_tree_map.rb
+++ b/lib/puppet/rb_tree_map.rb
@@ -1,382 +1,385 @@
 # Algorithms and Containers project is Copyright (c) 2009 Kanwei Li
 #
 # Permission is hereby granted, free of charge, to any person obtaining a copy
 # of this software and associated documentation files (the 'Software'), to deal
 # in the Software without restriction, including without limitation the rights
 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 # copies of the Software, and to permit persons to whom the Software is
 # furnished to do so, subject to the following conditions:
 #
 # The above copyright notice and this permission notice shall be included in
 # all copies or substantial portions of the Software.
 #
 # THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 # SOFTWARE.
 #
 # A RbTreeMap is a map that is stored in sorted order based on the order of its keys. This ordering is
 # determined by applying the function <=> to compare the keys. No duplicate values for keys are allowed,
 # so duplicate values are overwritten.
 #
 # A major advantage of RBTreeMap over a Hash is the fact that keys are stored in order and can thus be
 # iterated over in order. This is useful for many datasets.
 #
 # The implementation is adapted from Robert Sedgewick's Left Leaning Red-Black Tree implementation,
 # which can be found at http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java
 #
 # Most methods have O(log n) complexity.
 
 class Puppet::RbTreeMap
   include Enumerable
 
   attr_reader :size
 
   alias_method :length, :size
 
   # Create and initialize a new empty TreeMap.
   def initialize
     @root = nil
     @size = 0
   end
 
   # Insert an item with an associated key into the TreeMap, and returns the item inserted
   #
   # Complexity: O(log n)
   #
   # map = Containers::TreeMap.new
   # map.push("MA", "Massachusetts") #=> "Massachusetts"
   # map.get("MA") #=> "Massachusetts"
   def push(key, value)
     @root = insert(@root, key, value)
     @root.color = :black
     value
   end
   alias_method :[]=, :push
 
   # Return true if key is found in the TreeMap, false otherwise
   #
   # Complexity: O(log n)
   #
   #   map = Containers::TreeMap.new
   #   map.push("MA", "Massachusetts")
   #   map.push("GA", "Georgia")
   #   map.has_key?("GA") #=> true
   #   map.has_key?("DE") #=> false
   def has_key?(key)
-    !get(key).nil?
+    !get_recursive(@root, key).nil?
   end
 
   # Return the item associated with the key, or nil if none found.
   #
   # Complexity: O(log n)
   #
   #   map = Containers::TreeMap.new
   #   map.push("MA", "Massachusetts")
   #   map.push("GA", "Georgia")
   #   map.get("GA") #=> "Georgia"
   def get(key)
-    get_recursive(@root, key)
+    node = get_recursive(@root, key)
+    node ? node.value : nil
+    node.value if node
   end
   alias_method :[], :get
 
   # Return the smallest key in the map.
   #
   # Complexity: O(log n)
   #
   #   map = Containers::TreeMap.new
   #   map.push("MA", "Massachusetts")
   #   map.push("GA", "Georgia")
   #   map.min_key #=> "GA"
   def min_key
-    @root.nil? ? nil : min_recursive(@root)
+    @root.nil? ? nil : min_recursive(@root).key
   end
 
   # Return the largest key in the map.
   #
   # Complexity: O(log n)
   #
   #   map = Containers::TreeMap.new
   #   map.push("MA", "Massachusetts")
   #   map.push("GA", "Georgia")
   #   map.max_key #=> "MA"
   def max_key
-    @root.nil? ? nil : max_recursive(@root)
+    @root.nil? ? nil : max_recursive(@root).key
   end
 
   # Deletes the item and key if it's found, and returns the item. Returns nil
   # if key is not present.
   #
   # Complexity: O(log n)
   #
   #   map = Containers::TreeMap.new
   #   map.push("MA", "Massachusetts")
   #   map.push("GA", "Georgia")
   #   map.delete("MA") #=> "Massachusetts"
   def delete(key)
     result = nil
     if @root
       return unless has_key? key
       @root, result = delete_recursive(@root, key)
       @root.color = :black if @root
       @size -= 1
     end
     result
   end
 
   # Returns true if the tree is empty, false otherwise
   def empty?
     @root.nil?
   end
 
   # Deletes the item with the smallest key and returns the item. Returns nil
   # if key is not present.
   #
   # Complexity: O(log n)
   #
   #   map = Containers::TreeMap.new
   #   map.push("MA", "Massachusetts")
   #   map.push("GA", "Georgia")
   #   map.delete_min #=> "Massachusetts"
   #   map.size #=> 1
   def delete_min
     result = nil
     if @root
       @root, result = delete_min_recursive(@root)
       @root.color = :black if @root
       @size -= 1
     end
     result
   end
 
   # Deletes the item with the largest key and returns the item. Returns nil
   # if key is not present.
   #
   # Complexity: O(log n)
   #
   #   map = Containers::TreeMap.new
   #   map.push("MA", "Massachusetts")
   #   map.push("GA", "Georgia")
   #   map.delete_max #=> "Georgia"
   #   map.size #=> 1
   def delete_max
     result = nil
     if @root
       @root, result = delete_max_recursive(@root)
       @root.color = :black if @root
       @size -= 1
     end
     result
   end
 
   # Iterates over the TreeMap from smallest to largest element. Iterative approach.
   def each
     return nil unless @root
     stack = Array.new
     cursor = @root
     loop do
       if cursor
         stack.push(cursor)
         cursor = cursor.left
       else
         unless stack.empty?
           cursor = stack.pop
           yield(cursor.key, cursor.value)
           cursor = cursor.right
         else
           break
         end
       end
     end
   end
 
   def to_hash
     @root ? @root.to_hash : {}
   end
 
   class Node # :nodoc: all
     attr_accessor :color, :key, :value, :left, :right
     def initialize(key, value)
       @key = key
       @value = value
       @color = :red
       @left = nil
       @right = nil
     end
 
     def to_hash
       h = {
         :node => {
           :key => @key,
           :value => @value,
           :color => @color,
         }
       }
       h.merge!(:left => left.to_hash) if @left
       h.merge!(:right => right.to_hash) if @right
       h
     end
 
     def red?
       @color == :red
     end
 
     def colorflip
       @color       = @color == :red       ? :black : :red
       @left.color  = @left.color == :red  ? :black : :red
       @right.color = @right.color == :red ? :black : :red
     end
 
     def rotate_left
       r = @right
       r_key, r_value, r_color = r.key, r.value, r.color
       b = r.left
       r.left = @left
       @left = r
       @right = r.right
       r.right = b
       r.color, r.key, r.value = :red, @key, @value
       @key, @value = r_key, r_value
       self
     end
 
     def rotate_right
       l = @left
       l_key, l_value, l_color = l.key, l.value, l.color
       b = l.right
       l.right = @right
       @right = l
       @left = l.left
       l.left = b
       l.color, l.key, l.value = :red, @key, @value
       @key, @value = l_key, l_value
       self
     end
 
     def move_red_left
       colorflip
       if (@right.left && @right.left.red?)
         @right.rotate_right
         rotate_left
         colorflip
       end
       self
     end
 
     def move_red_right
       colorflip
       if (@left.left && @left.left.red?)
         rotate_right
         colorflip
       end
       self
     end
 
     def fixup
       rotate_left if @right && @right.red?
       rotate_right if (@left && @left.red?) && (@left.left && @left.left.red?)
       colorflip if (@left && @left.red?) && (@right && @right.red?)
 
       self
     end
   end
 
   private
 
   def delete_recursive(node, key)
     if (key <=> node.key) == -1
       node.move_red_left if ( !isred(node.left) && !isred(node.left.left) )
       node.left, result = delete_recursive(node.left, key)
     else
       node.rotate_right if isred(node.left)
       if ( ( (key <=> node.key) == 0) && node.right.nil? )
         return nil, node.value
       end
       if ( !isred(node.right) && !isred(node.right.left) )
         node.move_red_right
       end
       if (key <=> node.key) == 0
         result = node.value
-        node.value = get_recursive(node.right, min_recursive(node.right))
-        node.key = min_recursive(node.right)
+        min_child = min_recursive(node.right)
+        node.value = min_child.value
+        node.key = min_child.key
         node.right = delete_min_recursive(node.right).first
       else
         node.right, result = delete_recursive(node.right, key)
       end
     end
     return node.fixup, result
   end
 
   def delete_min_recursive(node)
     if node.left.nil?
       return nil, node.value
     end
     if ( !isred(node.left) && !isred(node.left.left) )
       node.move_red_left
     end
     node.left, result = delete_min_recursive(node.left)
 
     return node.fixup, result
   end
 
   def delete_max_recursive(node)
     if (isred(node.left))
       node = node.rotate_right
     end
     return nil, node.value if node.right.nil?
     if ( !isred(node.right) && !isred(node.right.left) )
       node.move_red_right
     end
     node.right, result = delete_max_recursive(node.right)
 
     return node.fixup, result
   end
 
   def get_recursive(node, key)
     return nil if node.nil?
     case key <=> node.key
-    when  0 then return node.value
+    when  0 then return node
     when -1 then return get_recursive(node.left, key)
     when  1 then return get_recursive(node.right, key)
     end
   end
 
   def min_recursive(node)
-    return node.key if node.left.nil?
+    return node if node.left.nil?
 
     min_recursive(node.left)
   end
 
   def max_recursive(node)
-    return node.key if node.right.nil?
+    return node if node.right.nil?
 
     max_recursive(node.right)
   end
 
   def insert(node, key, value)
     unless node
       @size += 1
       return Node.new(key, value)
     end
 
     case key <=> node.key
     when  0 then node.value = value
     when -1 then node.left = insert(node.left, key, value)
     when  1 then node.right = insert(node.right, key, value)
     end
 
     node.rotate_left if (node.right && node.right.red?)
     node.rotate_right if (node.left && node.left.red? && node.left.left && node.left.left.red?)
     node.colorflip if (node.left && node.left.red? && node.right && node.right.red?)
     node
   end
 
   def isred(node)
     return false if node.nil?
 
     node.color == :red
   end
 end
diff --git a/spec/unit/rb_tree_map_spec.rb b/spec/unit/rb_tree_map_spec.rb
index 9cccad5bc..3208d6cb0 100644
--- a/spec/unit/rb_tree_map_spec.rb
+++ b/spec/unit/rb_tree_map_spec.rb
@@ -1,573 +1,572 @@
 #!/usr/bin/env ruby
 
 require 'spec_helper'
 
 require 'puppet/rb_tree_map'
 
 describe Puppet::RbTreeMap do
   describe "#push" do
     it "should allow a new element to be added" do
       subject[5] = 'foo'
       subject.size.should == 1
 
       subject[5].should == 'foo'
     end
 
     it "should replace the old value if the key is in tree already" do
       subject[0] = 10
       subject[0] = 20
 
       subject[0].should == 20
       subject.size.should == 1
     end
 
     it "should be able to add a large number of elements" do
       (1..1000).each {|i| subject[i] = i.to_s}
 
       subject.size.should == 1000
     end
 
     it "should create a root node if the tree was empty" do
       subject.instance_variable_get(:@root).should be_nil
 
       subject[5] = 'foo'
 
       subject.instance_variable_get(:@root).should be_a(Puppet::RbTreeMap::Node)
     end
   end
 
   describe "#size" do
     it "should be 0 for en empty tree" do
       subject.size.should == 0
     end
 
     it "should correctly report the size for a non-empty tree" do
       (1..10).each {|i| subject[i] = i.to_s}
 
       subject.size.should == 10
     end
   end
 
   describe "#has_key?" do
     it "should be true if the tree contains the key" do
       subject[1] = 2
 
       subject.should be_has_key(1)
     end
 
     it "should be true if the tree contains the key and its value is nil" do
-      pending "We can't yet distinguish a missing key from a nil value here"
       subject[0] = nil
 
       subject.should be_has_key(0)
     end
 
     it "should be false if the tree does not contain the key" do
       subject[1] = 2
 
       subject.should_not be_has_key(2)
     end
 
     it "should be false if the tree is empty" do
       subject.should_not be_has_key(5)
     end
   end
 
   describe "#get" do
     it "should return the value at the key" do
       subject[1] = 2
       subject[3] = 4
 
       subject.get(1).should == 2
       subject.get(3).should == 4
     end
 
     it "should return nil if the tree is empty" do
       subject[1].should be_nil
     end
 
     it "should return nil if the key is not in the tree" do
       subject[1] = 2
 
       subject[3].should be_nil
     end
 
     it "should return nil if the value at the key is nil" do
       subject[1] = nil
 
       subject[1].should be_nil
     end
   end
 
   describe "#min_key" do
     it "should return the smallest key in the tree" do
       [4,8,12,3,6,2,-4,7].each do |i|
         subject[i] = i.to_s
       end
 
       subject.min_key.should == -4
     end
 
     it "should return nil if the tree is empty" do
       subject.min_key.should be_nil
     end
   end
 
   describe "#max_key" do
     it "should return the largest key in the tree" do
       [4,8,12,3,6,2,-4,7].each do |i|
         subject[i] = i.to_s
       end
 
       subject.max_key.should == 12
     end
 
     it "should return nil if the tree is empty" do
       subject.max_key.should be_nil
     end
   end
 
   describe "#delete" do
     before :each do
       subject[1] = '1'
       subject[0] = '0'
       subject[2] = '2'
     end
 
     it "should return the value at the key deleted" do
       subject.delete(0).should == '0'
       subject.delete(1).should == '1'
       subject.delete(2).should == '2'
       subject.size.should == 0
     end
 
     it "should be able to delete the last node" do
       tree = described_class.new
       tree[1] = '1'
 
       tree.delete(1).should == '1'
       tree.should be_empty
     end
 
     it "should be able to delete the root node" do
       subject.delete(1).should == '1'
 
       subject.size.should == 2
 
       subject.to_hash.should == {
         :node => {
           :key => 2,
           :value => '2',
           :color => :black,
         },
         :left => {
           :node => {
             :key => 0,
             :value => '0',
             :color => :red,
           }
         }
       }
     end
 
     it "should be able to delete the left child" do
       subject.delete(0).should == '0'
 
       subject.size.should == 2
 
       subject.to_hash.should == {
         :node => {
           :key => 2,
           :value => '2',
           :color => :black,
         },
         :left => {
           :node => {
             :key => 1,
             :value => '1',
             :color => :red,
           }
         }
       }
     end
 
     it "should be able to delete the right child" do
       subject.delete(2).should == '2'
 
       subject.size.should == 2
 
       subject.to_hash.should == {
         :node => {
           :key => 1,
           :value => '1',
           :color => :black,
         },
         :left => {
           :node => {
             :key => 0,
             :value => '0',
             :color => :red,
           }
         }
       }
     end
 
     it "should be able to delete the left child if it is a subtree" do
       (3..6).each {|i| subject[i] = i.to_s}
 
       subject.delete(1).should == '1'
 
       subject.to_hash.should == {
         :node => {
           :key => 5,
           :value => '5',
           :color => :black,
         },
         :left => {
           :node => {
             :key => 3,
             :value => '3',
             :color => :red,
           },
           :left => {
             :node => {
               :key => 2,
               :value => '2',
               :color => :black,
             },
             :left => {
               :node => {
                 :key => 0,
                 :value => '0',
                 :color => :red,
               },
             },
           },
           :right => {
             :node => {
               :key => 4,
               :value => '4',
               :color => :black,
             },
           },
         },
         :right => {
           :node => {
             :key => 6,
             :value => '6',
             :color => :black,
           },
         },
       }
     end
 
     it "should be able to delete the right child if it is a subtree" do
       (3..6).each {|i| subject[i] = i.to_s}
 
       subject.delete(5).should == '5'
 
       subject.to_hash.should == {
         :node => {
           :key => 3,
           :value => '3',
           :color => :black,
         },
         :left => {
           :node => {
             :key => 1,
             :value => '1',
             :color => :red,
           },
           :left => {
             :node => {
               :key => 0,
               :value => '0',
               :color => :black,
             },
           },
           :right => {
             :node => {
               :key => 2,
               :value => '2',
               :color => :black,
             },
           },
         },
         :right => {
           :node => {
             :key => 6,
             :value => '6',
             :color => :black,
           },
           :left => {
             :node => {
               :key => 4,
               :value => '4',
               :color => :red,
             },
           },
         },
       }
     end
 
     it "should return nil if the tree is empty" do
       tree = described_class.new
 
       tree.delete(14).should be_nil
 
       tree.size.should == 0
     end
 
     it "should return nil if the key is not in the tree" do
       (0..4).each {|i| subject[i] = i.to_s}
 
       subject.delete(2.5).should be_nil
       subject.size.should == 5
     end
 
     it "should return nil if the key is larger than the maximum key" do
       subject.delete(100).should be_nil
       subject.size.should == 3
     end
 
     it "should return nil if the key is smaller than the minimum key" do
       subject.delete(-1).should be_nil
       subject.size.should == 3
     end
   end
 
   describe "#empty?" do
     it "should return true if the tree is empty" do
       subject.should be_empty
     end
 
     it "should return false if the tree is not empty" do
       subject[5] = 10
 
       subject.should_not be_empty
     end
   end
 
   describe "#delete_min" do
     it "should delete the smallest element of the tree" do
       (1..15).each {|i| subject[i] = i.to_s}
 
       subject.delete_min.should == '1'
       subject.size.should == 14
     end
 
     it "should return nil if the tree is empty" do
       subject.delete_min.should be_nil
     end
   end
 
   describe "#delete_max" do
     it "should delete the largest element of the tree" do
       (1..15).each {|i| subject[i] = i.to_s}
 
       subject.delete_max.should == '15'
       subject.size.should == 14
     end
 
     it "should return nil if the tree is empty" do
       subject.delete_max.should be_nil
     end
   end
 
   describe "#each" do
     it "should yield each pair in the tree in order if a block is provided" do
       # Insert in reverse to demonstrate they aren't being yielded in insertion order
       (1..5).to_a.reverse.each {|i| subject[i] = i.to_s}
 
       nodes = []
       subject.each do |key,value|
         nodes << [key,value]
       end
 
       nodes.should == (1..5).map {|i| [i, i.to_s]}
     end
 
     it "should do nothing if the tree is empty" do
       subject.each do |key,value|
         raise "each on an empty tree incorrectly yielded #{key}, #{value}"
       end
     end
   end
 
   describe "#isred" do
     it "should return true if the node is red" do
       node = Puppet::RbTreeMap::Node.new(1,2)
       node.color = :red
 
       subject.send(:isred, node).should == true
     end
 
     it "should return false if the node is black" do
       node = Puppet::RbTreeMap::Node.new(1,2)
       node.color = :black
 
       subject.send(:isred, node).should == false
     end
 
     it "should return false if the node is nil" do
       subject.send(:isred, nil).should == false
     end
   end
 end
 
 describe Puppet::RbTreeMap::Node do
   let(:tree) { Puppet::RbTreeMap.new }
   let(:subject) { tree.instance_variable_get(:@root) }
 
   before :each do
     (1..3).each {|i| tree[i] = i.to_s}
   end
 
   describe "#red?" do
     it "should return true if the node is red" do
       subject.color = :red
 
       subject.should be_red
     end
 
     it "should return false if the node is black" do
       subject.color = :black
 
       subject.should_not be_red
     end
   end
 
   describe "#colorflip" do
     it "should switch the color of the node and its children" do
       subject.color.should == :black
       subject.left.color.should == :black
       subject.right.color.should == :black
 
       subject.colorflip
 
       subject.color.should == :red
       subject.left.color.should == :red
       subject.right.color.should == :red
     end
   end
 
   describe "#rotate_left" do
     it "should rotate the tree once to the left" do
       (4..7).each {|i| tree[i] = i.to_s}
 
       root = tree.instance_variable_get(:@root)
 
       root.rotate_left
 
       tree.to_hash.should == {
         :node => {
           :key => 6,
           :value => '6',
           :color => :black,
         },
         :left => {
           :node => {
             :key => 4,
             :value => '4',
             :color => :red,
           },
           :left => {
             :node => {
               :key => 2,
               :value => '2',
               :color => :black,
             },
             :left => {
               :node => {
                 :key => 1,
                 :value => '1',
                 :color => :black,
               },
             },
             :right => {
               :node => {
                 :key => 3,
                 :value => '3',
                 :color => :black,
               },
             },
           },
           :right => {
             :node => {
               :key => 5,
               :value => '5',
               :color => :black,
             },
           },
         },
         :right => {
           :node => {
             :key => 7,
             :value => '7',
             :color => :black,
           },
         },
       }
     end
   end
 
   describe "#rotate_right" do
     it "should rotate the tree once to the right" do
       (4..7).each {|i| tree[i] = i.to_s}
 
       root = tree.instance_variable_get(:@root)
 
       root.rotate_right
 
       tree.to_hash.should == {
         :node => {
           :key => 2,
           :value => '2',
           :color => :black,
         },
         :left => {
           :node => {
             :key => 1,
             :value => '1',
             :color => :black,
           },
         },
         :right => {
           :node => {
             :key => 4,
             :value => '4',
             :color => :red,
           },
           :left => {
             :node => {
               :key => 3,
               :value => '3',
               :color => :black,
             },
           },
           :right => {
             :node => {
               :key => 6,
               :value => '6',
               :color => :black,
             },
             :left => {
               :node => {
                 :key => 5,
                 :value => '5',
                 :color => :black,
               },
             },
             :right => {
               :node => {
                 :key => 7,
                 :value => '7',
                 :color => :black,
               },
             },
           },
         },
       }
     end
   end
 end