1require "spec_helper"
  2
  3describe AVLTree do
  4  subject { AVLTree.new }
  5
  6  context "when empty" do
  7    it "should have a size of 0" do
  8      expect(subject.size).to eq(0)
  9    end
 10
 11    it "should have have a height of 0" do
 12      expect(subject.height).to eq(0)
 13    end
 14  end
 15
 16  context "when a single item is added" do
 17    before :each do
 18      subject.push("A")
 19    end
 20
 21    it "should have a size of 1" do
 22      expect(subject.size).to eq(1)
 23    end
 24
 25    it "should have a height of 1" do
 26      expect(subject.height).to eq(1)
 27    end
 28  end
 29
 30  context "when two items are added" do
 31    before :each do
 32      subject.add("a")
 33      subject.add("b")
 34    end
 35
 36    it "should have a size of 2" do
 37      expect(subject.size).to eq(2)
 38    end
 39    it "should have a height of 2" do
 40      expect(subject.height).to eq(2)
 41    end
 42  end
 43
 44  context "when a balanced tree has 3 items" do
 45    before :each do
 46      subject.add("b")
 47      subject.add("a")
 48      subject.add("c")
 49    end
 50
 51    it "should have a size of 3" do
 52      expect(subject.size).to eq(3)
 53    end
 54
 55    it "should have a height of 2" do
 56      expect(subject.height).to eq(2)
 57    end
 58  end
 59
 60  context "when the tree is unbalanced" do
 61    context "with a right-right case" do
 62      before :each do
 63        subject.add("a")
 64        subject.add("b")
 65        subject.add("c")
 66      end
 67
 68      it "should re-balance it self" do
 69        expect(subject.height).to eq(2)
 70      end
 71
 72      it "should have a new root" do
 73        expect(subject.root.data).to eq("b")
 74      end
 75
 76      it "should change the left side" do
 77        expect(subject.root.left.data).to eq("a")
 78      end
 79
 80      it "should change the right side" do
 81        expect(subject.root.right.data).to eq("c")
 82      end
 83    end
 84
 85    context "with a left-left case" do
 86      before :each do
 87        subject.add("c")
 88        subject.add("b")
 89        subject.add("a")
 90      end
 91
 92      it "should re-balance it self" do
 93        expect(subject.height).to eq(2)
 94      end
 95
 96      it "should have a new root" do
 97        expect(subject.root.data).to eq("b")
 98      end
 99
100      it "should change the left side" do
101        expect(subject.root.left.data).to eq("a")
102      end
103
104      it "should change the right side" do
105        expect(subject.root.right.data).to eq("c")
106      end
107    end
108
109    context "with a left-right case" do
110      before :each do
111        subject.add(5)
112        subject.add(3)
113        subject.add(4)
114      end
115
116      it "should adjust the height" do
117        expect(subject.height).to eq(2)
118      end
119
120      it "should have a new root" do
121        expect(subject.root.data).to eq(4)
122      end
123
124      it "should have a proper left side" do
125        expect(subject.root.left.data).to eq(3)
126      end
127
128      it "should have a proper right side" do
129        expect(subject.root.right.data).to eq(5)
130      end
131    end
132
133    context "with a right-left case" do
134      before :each do
135        subject.add(3)
136        subject.add(5)
137        subject.add(4)
138      end
139
140      it "should adjust the height" do
141        expect(subject.height).to eq(2)
142      end
143
144      it "should have a new root" do
145        expect(subject.root.data).to eq(4)
146      end
147
148      it "should have a proper left side" do
149        expect(subject.root.left.data).to eq(3)
150      end
151
152      it "should have a proper right side" do
153        expect(subject.root.right.data).to eq(5)
154      end
155    end
156  end
157end