From e2bbfb897e073b5955088b1d71097cb0bfdb43f2 Mon Sep 17 00:00:00 2001
From: mo khan <mo@mokhan.ca>
Date: Fri, 30 Aug 2013 17:36:46 -0600
Subject: balance avl tree with left right case

---
 lib/data_structures/avl_tree.rb | 34 ++++++++++++++++++++++++++--------
 1 file changed, 26 insertions(+), 8 deletions(-)

(limited to 'lib/data_structures')

diff --git a/lib/data_structures/avl_tree.rb b/lib/data_structures/avl_tree.rb
index b2a2fce..3bfb1d1 100644
--- a/lib/data_structures/avl_tree.rb
+++ b/lib/data_structures/avl_tree.rb
@@ -54,7 +54,7 @@ class AVLTree
     end
 
     def re_balance
-      p balance_factor
+      p "balance factor for:#{data} is #{balance_factor}"
       if balance_factor < -1
         p "right right case"
         @right.left = self
@@ -62,22 +62,40 @@ class AVLTree
         @right = nil
         new_root
       elsif balance_factor > 1
-        @left.right = self
-        new_root = @left
-        @left = nil
-        new_root
+        if @left.balance_factor == -1
+          left_right_case
+        else
+          left_left_case
+        end
       else
         self
       end
     end
 
-    private
-
     def balance_factor
-      p "left: #{left_height}, right: #{right_height}"
+      #p "left: #{left_height}, right: #{right_height}"
       (left_height - right_height) || 0
     end
 
+    private
+
+    def left_right_case
+      p "left right case"
+      left = @left
+      @left = @left.right
+      @left.left = left
+      left.right = nil
+      left_left_case
+    end
+
+    def left_left_case
+      p "left left case"
+      @left.right = self
+      new_root = @left
+      @left = nil
+      new_root
+    end
+
     def left_height
       @left ? @left.height : 0
     end
-- 
cgit v1.2.3