Perform left left rotate after deletion

3 files changed, 56 insertions, 4 deletions

diff --git a/src/03/avl_tree.c b/src/03/avl_tree.c
index cc7d52f..e0b5cc5 100644
--- a/src/03/avl_tree.c
+++ b/src/03/avl_tree.c
@@ -120,14 +120,14 @@ AVLTree *avl_tree_insert(AVLTree *tree, int value) {
   return rebalance(tree, value);
 }
 
-AVLTree *node_delete(AVLTree *root, int value) {
+AVLTree *avl_tree_delete(AVLTree *root, int value) {
   if (root == NULL)
     return root;
 
   if (value < root->value)
-    root->left = node_delete(root->left, value);
+    root->left = avl_tree_delete(root->left, value);
   else if (value > root->value)
-    root->right = node_delete(root->right, value);
+    root->right = avl_tree_delete(root->right, value);
   else {
     if ((root->left == NULL) || (root->right == NULL)) {
       AVLTree *temp = root->left ? root->left : root->right;
@@ -142,7 +142,7 @@ AVLTree *node_delete(AVLTree *root, int value) {
     } else {
       AVLTree *temp = smallest(root->right);
       root->value = temp->value;
-      root->right = node_delete(root->right, temp->value);
+      root->right = avl_tree_delete(root->right, temp->value);
     }
   }
 
diff --git a/src/03/avl_tree.h b/src/03/avl_tree.h
index 189d33c..66b89ad 100644
--- a/src/03/avl_tree.h
+++ b/src/03/avl_tree.h
@@ -8,4 +8,5 @@ typedef struct node {
 AVLTree *avl_tree_initialize(int value);
 int avl_tree_size(AVLTree *tree);
 AVLTree *avl_tree_insert(AVLTree *tree, int value);
+AVLTree *avl_tree_delete(AVLTree *tree, int value);
 void avl_tree_inspect(AVLTree *tree);
diff --git a/src/03/avl_tree_test.c b/src/03/avl_tree_test.c
index ccfcefb..5bf1c8c 100644
--- a/src/03/avl_tree_test.c
+++ b/src/03/avl_tree_test.c
@@ -105,10 +105,59 @@ Ensure(insert_performs_a_right_left_rotation) {
   assert_that(tree->right->value, is_equal_to(30));
 }
 
+Ensure(delete_handles_left_left_case) {
+/*
+      (z)                   (y)
+      / \                /      \
+    (y) (T4)          (X)        (z)
+    / \       -->   /    \      /   \
+  (x) (T3)        (T1)  (T2)  (T3)  (T4)
+  / \
+(T1) (T2)
+
+Delete (37):
+
+      (30)                           (20)
+      /  \                         /      \
+    (20) (35)                  (10)        (30)
+    / \     \           -->   /    \      /   \
+  (10) (25) *(37)            (5)  (15)  (25)  (35)
+  / \
+(5) (15)
+*/
+
+  AVLTree *tree = avl_tree_initialize(30);
+  tree = avl_tree_insert(tree, 35);
+  tree = avl_tree_insert(tree, 20);
+  tree = avl_tree_insert(tree, 10);
+  tree = avl_tree_insert(tree, 25);
+  tree = avl_tree_insert(tree, 37);
+  tree = avl_tree_insert(tree, 15);
+  tree = avl_tree_insert(tree, 5);
+
+  tree = avl_tree_delete(tree, 37);
+
+  assert_that(tree, is_not_equal_to(NULL));
+  assert_that(tree->value, is_equal_to(20));
+  assert_that(tree->left->value, is_equal_to(10));
+  assert_that(tree->left->left->value, is_equal_to(5));
+  assert_that(tree->left->right->value, is_equal_to(15));
+
+  assert_that(tree->right->value, is_equal_to(30));
+  assert_that(tree->right->left->value, is_equal_to(25));
+  assert_that(tree->right->right->value, is_equal_to(35));
+}
+
+Ensure(delete_handles_left_right_case) { }
+Ensure(delete_handles_right_right_case) { }
+Ensure(delete_handles_right_left) { }
+
 TestSuite *avl_tree_tests() {
   TestSuite *x = create_test_suite();
   add_test(x, initialize_returns_new_tree);
+
   add_test(x, size_returns_zero);
+
   add_test(x, insert_changes_size);
   add_test(x, insert_changes_height);
   add_test(x, insert_creates_a_new_root);
@@ -116,6 +165,8 @@ TestSuite *avl_tree_tests() {
   add_test(x, insert_performs_a_right_rotation);
   add_test(x, insert_performs_a_left_right_rotation);
   add_test(x, insert_performs_a_right_left_rotation);
+
+  add_test(x, delete_handles_left_left_case);
   return x;
 }