Commit fb4b787

@@ -0,0 +1,55 @@
+class AVLTree
+  def initialize
+  end
+
+  def push(item)
+    if @root
+      @root.push(item)
+    else
+      @root = Node.new(item)
+    end
+  end
+
+  def size
+    return 0 unless @root
+    @root.size
+  end
+
+  def height
+    return 0 unless @root
+    @root.height
+  end
+
+  alias_method :add, :push
+
+  class Node
+    def initialize(data)
+      @data = data
+    end
+
+    def push(item)
+      if (item <=> @data) == -1
+        @left.push(item) if @left
+        @left = Node.new(item) unless @left
+      else
+        @right.push(item) if @right
+        @right = Node.new(item) unless @right
+      end
+    end
+
+    def size
+      result = 1
+      result += @left.size if @left
+      result += @right.size if @right
+      result
+    end
+
+    def height
+      result = 1
+      left_height = @left ? @left.height : 0
+      right_height = @right ? @right.height : 0
+      result += left_height >= right_height ? left_height : right_height
+      result
+    end
+  end
+end

@@ -0,0 +1,65 @@
+require "spec_helper"
+
+describe AVLTree do
+  let(:sut) { AVLTree.new }
+
+  context "when empty" do
+    it "should have a size of 0" do
+      sut.size.should == 0
+    end
+
+    it "should have have a height of 0" do
+      sut.height.should == 0
+    end
+  end
+
+  context "when a single item is added" do
+    before :each do
+      sut.push("A")
+    end
+
+    it "should have a size of 1" do
+      sut.size.should == 1
+    end
+
+    it "should have a height of 1" do
+      sut.height.should == 1
+    end
+  end
+
+  context "when two items are added" do
+    before :each do
+      sut.add("a")
+      sut.add("b")
+    end
+
+    it "should have a size of 2" do
+      sut.size.should == 2
+    end
+    it "should have a height of 2" do
+      sut.height.should == 2
+    end
+  end
+
+  context "when a balanced tree has 3 items" do
+    before :each do
+      sut.add("b")
+      sut.add("a")
+      sut.add("c")
+    end
+
+    it "should have a size of 3" do
+      sut.size.should == 3
+    end
+
+    it "should have a height of 2" do
+      sut.height.should == 2
+    end
+  end
+
+  context "when adding an item that would cause the tree to be unbalanced" do
+    it "should re-balance it self" do
+      
+    end
+  end
+end

@@ -7,3 +7,4 @@ require_relative '../lib/sorting/merge_sort'
 require_relative '../lib/data_structures/linked_list_stack'
 require_relative '../lib/data_structures/dynamic_array_stack'
 require_relative '../lib/data_structures/binary_tree'
+require_relative '../lib/data_structures/avl_tree'