Detect scapegoat and rebalance the tree

3 files changed, 58 insertions, 48 deletions

diff --git a/src/02/03/btree.c b/src/02/03/btree.c
index 8601927..5a2e463 100644
--- a/src/02/03/btree.c
+++ b/src/02/03/btree.c
@@ -56,9 +56,9 @@ List *btree_to_list(BTree *tree)
     } else {
       tmp = stack_pop(stack);
       if (list)
-        list_add(list, tmp->data);
+        list_add(list, tmp);
       else
-        list = list_initialize(tree->data);
+        list = list_initialize(tree);
       tmp = tmp->right;
     }
   }
@@ -71,18 +71,40 @@ int btree_size(BTree *tree) {
   return list ? list_size(list) : 0;
 }
 
+bool btree_is_scapegoat(BTree *tree)
+{
+  int size = btree_size(tree);
+  int parent_size = btree_size(tree->parent);
+
+  return ((size * 3) > (parent_size * 2));
+}
+
+BTree *btree_rebuild(BTree *tree)
+{
+  List *list = btree_to_list(tree->parent);
+  int mid = (list_size(list) / 2) - 1;
+  List *new_root = list_get(list, mid);
+  int data = ((BTree*)new_root->data)->data;
+  BTree *new_broot = btree_initialize(NULL, data);
+
+  for (int i = 0; i < list_size(list); i++) {
+    if (i == mid) continue;
+
+    int data = ((BTree*)list_get(list, i)->data)->data;
+    btree_insert(new_broot, data);
+  }
+  return new_broot;
+}
+
 BTree *btree_rebalance(BTree *tree)
 {
   if (!tree->parent)
     return tree;
 
-  int size = btree_size(tree);
-  int parent_size = btree_size(tree->parent);
-  /*float ratio = size / parent_size;*/
-  float ratio = 0.0;
-  printf("%d / %d = %f\n", size, parent_size, ratio);
+  if (btree_is_scapegoat(tree))
+    return btree_rebuild(tree);
 
-  return tree;
+  return btree_rebalance(tree->parent);
 }
 
 /**
@@ -98,14 +120,15 @@ BTree *btree_insert(BTree *tree, int data) {
   if (data <= tree->data)
     if (tree->left)
       btree_insert(tree->left, data);
-    else
+    else {
       tree->left = btree_initialize(tree, data);
+    }
   else if (tree->right)
     btree_insert(tree->right, data);
-  else
+  else {
     tree->right = btree_initialize(tree, data);
+  }
 
-  /*return btree_rebalance(tree);*/
   return tree;
 }
 
diff --git a/src/02/03/btree_test.c b/src/02/03/btree_test.c
index 47cd438..9539f2b 100644
--- a/src/02/03/btree_test.c
+++ b/src/02/03/btree_test.c
@@ -81,21 +81,17 @@ Ensure(
 Ensure(BinaryTree, when_rebalancing_a_tree) {
   BTree *tree = btree_insert(NULL, 1);
   tree->right = btree_initialize(tree, 5);
-  tree->right->left = btree_initialize(tree, 2);
-  tree->right->left->right = btree_initialize(tree, 4);
-  tree->right->left->right = btree_initialize(tree, 4);
+  tree->right->left = btree_initialize(tree->right, 2);
+  tree->right->left->right = btree_initialize(tree->right->left, 4);
 
-  tree = btree_insert(tree, 2);
-  tree = btree_insert(tree, 4);
-  tree = btree_insert(tree, 3);
-
-  tree = btree_rebalance(tree);
+  tree = btree_rebalance(tree->right->left->right);
 
   assert_that(tree, is_not_equal_to(NULL));
+  assert_that(tree->data, is_equal_to(2));
 
-  /*printf("%d\n", tree->parent->data);*/
-  assert_that(tree->right->parent, is_not_equal_to(NULL));
-
+  assert_that(tree->left->data, is_equal_to(1));
+  assert_that(tree->right->data, is_equal_to(4));
+  assert_that(tree->right->right->data, is_equal_to(5));
 }
 
 Ensure(
@@ -108,18 +104,9 @@ Ensure(
   tree = btree_insert(tree, 3);
 
   assert_that(tree, is_not_equal_to(NULL));
-  assert_that(tree->data, is_equal_to(3));
-
-  assert_that(tree->left, is_not_equal_to(NULL));
-  assert_that(tree->left->data, is_equal_to(2));
-
-  assert_that(tree->left->left, is_not_equal_to(NULL));
-  assert_that(tree->left->left->data, is_equal_to(1));
-
-  assert_that(tree->right, is_not_equal_to(NULL));
+  assert_that(tree->data, is_equal_to(2));
+  assert_that(tree->left->data, is_equal_to(1));
   assert_that(tree->right->data, is_equal_to(4));
-
-  assert_that(tree->right->right, is_not_equal_to(NULL));
   assert_that(tree->right->right->data, is_equal_to(5));
 }
 
@@ -137,25 +124,25 @@ Ensure(BinaryTree, when_calculating_the_size_of_the_tree)
 TestSuite *binary_search_tree_tests() {
   TestSuite *suite = create_test_suite();
 
-  /*add_test_with_context(suite, BinaryTree, when_the_tree_is_NULL);*/
-  /*add_test_with_context(*/
-      /*suite, BinaryTree,*/
-      /*when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side);*/
-  /*add_test_with_context(*/
-      /*suite, BinaryTree,*/
-      /*when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side);*/
-  /*add_test_with_context(*/
-      /*suite, BinaryTree,*/
-      /*when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side);*/
-  /*add_test_with_context(*/
-      /*suite, BinaryTree,*/
-      /*when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position);*/
+  add_test_with_context(suite, BinaryTree, when_the_tree_is_NULL);
+  add_test_with_context(
+      suite, BinaryTree,
+      when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
+  add_test_with_context(
+      suite, BinaryTree,
+      when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side);
+  add_test_with_context(
+      suite, BinaryTree,
+      when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
+  add_test_with_context(
+      suite, BinaryTree,
+      when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position);
   add_test_with_context(suite, BinaryTree, when_rebalancing_a_tree);
   /*add_test_with_context(*/
       /*suite, BinaryTree,*/
       /*when_inserting_items_described_in_the_assignment_it_inserts_in_the_expected_position_in_the_tree);*/
 
-  /*add_test_with_context(suite, BinaryTree, when_calculating_the_size_of_the_tree);*/
+  add_test_with_context(suite, BinaryTree, when_calculating_the_size_of_the_tree);
   return suite;
 }
 
diff --git a/src/02/03/list.c b/src/02/03/list.c
index dc8b8c8..b7387e7 100644
--- a/src/02/03/list.c
+++ b/src/02/03/list.c
@@ -20,7 +20,7 @@ List *list_initialize(void *data) {
  *
  * @param head The head of a linked list
  * @param data The data to add to the tail of a linked list
- * @return Returns the new node tail node
+ * @return Returns the new tail node
  */
 List *list_add(List *head, void *data) {
   List *tail;