diff --git a/lib/puppet/rb_tree_map.rb b/lib/puppet/rb_tree_map.rb
new file mode 100644
index 000000000..8feba17fa
--- /dev/null
+++ b/lib/puppet/rb_tree_map.rb
@@ -0,0 +1,415 @@
+# 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_accessor :height_black
+
+  # Create and initialize a new empty TreeMap.
+  def initialize
+    @root = nil
+    @height_black = 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)
+    @height_black += 1 if isred(@root)
+    @root.color = :black
+    value
+  end
+  alias_method :[]=, :push
+
+  # Return the number of items in the TreeMap.
+  #
+  #   map = Containers::TreeMap.new
+  #   map.push("MA", "Massachusetts")
+  #   map.push("GA", "Georgia")
+  #   map.size #=> 2
+  def size
+    @root and @root.size or 0
+  end
+
+  # Return the height of the tree structure in the TreeMap.
+  #
+  # Complexity: O(1)
+  #
+  #   map = Containers::TreeMap.new
+  #   map.push("MA", "Massachusetts")
+  #   map.push("GA", "Georgia")
+  #   map.height #=> 2
+  def height
+    @root and @root.height or 0
+  end
+
+  # 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?
+  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)
+  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)
+  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)
+  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
+    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
+    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
+    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, :size, :height
+    def initialize(key, value)
+      @key = key
+      @value = value
+      @color = :red
+      @left = nil
+      @right = nil
+      @size = 1
+      @height = 1
+    end
+
+    def to_hash
+      h = {
+        :node => {
+          :key => @key,
+          :value => @value,
+          :color => @color,
+          :size => size,
+          :height => height,
+        }
+      }
+      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 update_size
+      @size = (@left ? @left.size : 0) + (@right ? @right.size : 0) + 1
+      left_height = (@left ? @left.height : 0)
+      right_height = (@right ? @right.height : 0)
+      if left_height > right_height
+        @height = left_height + 1
+      else
+        @height = right_height + 1
+      end
+      self
+    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
+      r.update_size
+      update_size
+    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
+      l.update_size
+      update_size
+    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?)
+
+      update_size
+    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)
+        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 -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?
+
+    min_recursive(node.left)
+  end
+
+  def max_recursive(node)
+    return node.key if node.right.nil?
+
+    max_recursive(node.right)
+  end
+
+  def insert(node, key, value)
+    return Node.new(key, value) unless node
+
+    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.update_size
+  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
new file mode 100644
index 000000000..2b933ab1f
--- /dev/null
+++ b/spec/unit/rb_tree_map_spec.rb
@@ -0,0 +1,733 @@
+#!/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 "#height" do
+    it "should be 0 for an empty tree" do
+      subject.height.should == 0
+    end
+
+    # This is kind of a cop-out, but height depends on insertion order.
+    it "should be the height of the root node" do
+      root = stub('root', :height => 5)
+      subject.instance_variable_set(:@root, root)
+
+      subject.height.should == 5
+    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,
+          :size => 2,
+          :height => 2,
+        },
+        :left => {
+          :node => {
+            :key => 0,
+            :value => '0',
+            :color => :red,
+            :size => 1,
+            :height => 1,
+          }
+        }
+      }
+    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,
+          :size => 2,
+          :height => 2,
+        },
+        :left => {
+          :node => {
+            :key => 1,
+            :value => '1',
+            :color => :red,
+            :size => 1,
+            :height => 1,
+          }
+        }
+      }
+    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,
+          :size => 2,
+          :height => 2,
+        },
+        :left => {
+          :node => {
+            :key => 0,
+            :value => '0',
+            :color => :red,
+            :size => 1,
+            :height => 1,
+          }
+        }
+      }
+    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,
+          :size => 6,
+          :height => 4,
+        },
+        :left => {
+          :node => {
+            :key => 3,
+            :value => '3',
+            :color => :red,
+            :size => 4,
+            :height => 3,
+          },
+          :left => {
+            :node => {
+              :key => 2,
+              :value => '2',
+              :color => :black,
+              :size => 2,
+              :height => 2,
+            },
+            :left => {
+              :node => {
+                :key => 0,
+                :value => '0',
+                :color => :red,
+                :size => 1,
+                :height => 1,
+              },
+            },
+          },
+          :right => {
+            :node => {
+              :key => 4,
+              :value => '4',
+              :color => :black,
+              :size => 1,
+              :height => 1,
+            },
+          },
+        },
+        :right => {
+          :node => {
+            :key => 6,
+            :value => '6',
+            :color => :black,
+            :size => 1,
+            :height => 1,
+          },
+        },
+      }
+    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,
+          :size => 6,
+          :height => 3,
+        },
+        :left => {
+          :node => {
+            :key => 1,
+            :value => '1',
+            :color => :red,
+            :size => 3,
+            :height => 2,
+          },
+          :left => {
+            :node => {
+              :key => 0,
+              :value => '0',
+              :color => :black,
+              :size => 1,
+              :height => 1,
+            },
+          },
+          :right => {
+            :node => {
+              :key => 2,
+              :value => '2',
+              :color => :black,
+              :size => 1,
+              :height => 1,
+            },
+          },
+        },
+        :right => {
+          :node => {
+            :key => 6,
+            :value => '6',
+            :color => :black,
+            :size => 2,
+            :height => 2,
+          },
+          :left => {
+            :node => {
+              :key => 4,
+              :value => '4',
+              :color => :red,
+              :size => 1,
+              :height => 1,
+            },
+          },
+        },
+      }
+    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
+    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'
+    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'
+    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 "#update_size" do
+    describe "when recalculating size" do
+      it "should set the size to the sum of its subtrees + 1 for itself" do
+        subject.left.size = 13
+        subject.right.size = 17
+
+        subject.update_size
+
+        subject.size.should == 31
+      end
+
+      it "should only count the left subtree if there is no right" do
+        subject.left = nil
+        subject.right.size = 11
+
+        subject.update_size
+
+        subject.size.should == 12
+      end
+
+      it "should only count the left subtree if there is no right" do
+        subject.right = nil
+        subject.left.size = 19
+
+        subject.update_size
+
+        subject.size.should == 20
+      end
+
+      it "should be 1 if there are no children" do
+        subject.left = nil
+        subject.right = nil
+
+        subject.update_size
+
+        subject.size.should == 1
+      end
+    end
+
+    describe "when recalculating height" do
+      it "should set the height to the height of the longer subtree + 1 for itself" do
+        subject.height.should == 2
+
+        subject.left.height = 5
+        subject.update_size
+
+        subject.height.should == 6
+
+        subject.right.height = 10
+        subject.update_size
+
+        subject.height.should == 11
+      end
+
+      it "should use the left subtree if there is no right" do
+        subject.left.height = 9
+        subject.right.height = 20
+        subject.right = nil
+
+        subject.update_size
+
+        subject.height.should == 10
+      end
+
+      it "should use the right subtree if there is no right" do
+        subject.left.height = 20
+        subject.left = nil
+        subject.right.height = 14
+
+        subject.update_size
+
+        subject.height.should == 15
+      end
+
+      it "should be 1 if there are no children" do
+        subject.left = nil
+        subject.right = nil
+
+        subject.update_size
+
+        subject.height.should == 1
+      end
+    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,
+          :size => 7,
+          :height => 4,
+        },
+        :left => {
+          :node => {
+            :key => 4,
+            :value => '4',
+            :color => :red,
+            :size => 5,
+            :height => 3,
+          },
+          :left => {
+            :node => {
+              :key => 2,
+              :value => '2',
+              :color => :black,
+              :size => 3,
+              :height => 2,
+            },
+            :left => {
+              :node => {
+                :key => 1,
+                :value => '1',
+                :color => :black,
+                :size => 1,
+                :height => 1,
+              },
+            },
+            :right => {
+              :node => {
+                :key => 3,
+                :value => '3',
+                :color => :black,
+                :size => 1,
+                :height => 1,
+              },
+            },
+          },
+          :right => {
+            :node => {
+              :key => 5,
+              :value => '5',
+              :color => :black,
+              :size => 1,
+              :height => 1,
+            },
+          },
+        },
+        :right => {
+          :node => {
+            :key => 7,
+            :value => '7',
+            :color => :black,
+            :size => 1,
+            :height => 1,
+          },
+        },
+      }
+    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,
+          :size => 7,
+          :height => 4,
+        },
+        :left => {
+          :node => {
+            :key => 1,
+            :value => '1',
+            :color => :black,
+            :size => 1,
+            :height => 1,
+          },
+        },
+        :right => {
+          :node => {
+            :key => 4,
+            :value => '4',
+            :color => :red,
+            :size => 5,
+            :height => 3,
+          },
+          :left => {
+            :node => {
+              :key => 3,
+              :value => '3',
+              :color => :black,
+              :size => 1,
+              :height => 1,
+            },
+          },
+          :right => {
+            :node => {
+              :key => 6,
+              :value => '6',
+              :color => :black,
+              :size => 3,
+              :height => 2,
+            },
+            :left => {
+              :node => {
+                :key => 5,
+                :value => '5',
+                :color => :black,
+                :size => 1,
+                :height => 1,
+              },
+            },
+            :right => {
+              :node => {
+                :key => 7,
+                :value => '7',
+                :color => :black,
+                :size => 1,
+                :height => 1,
+              },
+            },
+          },
+        },
+      }
+    end
+  end
+end