Start to build a red black tree

6 files changed, 35 insertions, 22 deletions

diff --git a/src/03/Makefile b/src/03/Makefile
index e87119a..e09138b 100644
--- a/src/03/Makefile
+++ b/src/03/Makefile
@@ -5,8 +5,8 @@ CC=clang
 TEST_LIBS = -lcgreen
 
 BUILDDIR := build
-OBJS := $(addprefix $(BUILDDIR)/,avl_tree.o)
-TEST_OBJS := $(addprefix $(BUILDDIR)/,avl_tree_test.o)
+OBJS := $(addprefix $(BUILDDIR)/,avl_tree.o rb_tree.o)
+TEST_OBJS := $(addprefix $(BUILDDIR)/,avl_tree_test.o rb_tree_test.o)
 
 $(BUILDDIR)/%.o : %.c
 	$(COMPILE.c) $(OUTPUT_OPTION) $<
diff --git a/src/03/avl_tree.c b/src/03/avl_tree.c
index c3b1d81..e1e3e66 100644
--- a/src/03/avl_tree.c
+++ b/src/03/avl_tree.c
@@ -74,7 +74,23 @@ int compare(int a, int b)
   return (a < b) ? -1 : ((a > b) ? 1 : 0);
 }
 
-AVLTree *rebalance(AVLTree *tree, int value) {
+AVLTree *avl_tree_insert(AVLTree *tree, int value) {
+  if (tree == NULL)
+    return avl_tree_initialize(value);
+
+  switch(compare(value, tree->value)) {
+    case -1:
+      tree->left = avl_tree_insert(tree->left, value);
+      break;
+    case 1:
+      tree->right = avl_tree_insert(tree->right, value);
+      break;
+    default:
+      return tree;
+  }
+
+  tree->height = 1 + max(height_of(tree->left), height_of(tree->right));
+
   int balance = balance_of(tree);
   if (balance > 1 && value < tree->left->value)
     return rotate_right(tree);
@@ -95,25 +111,6 @@ AVLTree *rebalance(AVLTree *tree, int value) {
   return tree;
 }
 
-AVLTree *avl_tree_insert(AVLTree *tree, int value) {
-  if (tree == NULL)
-    return avl_tree_initialize(value);
-
-  switch(compare(value, tree->value)) {
-    case -1:
-      tree->left = avl_tree_insert(tree->left, value);
-      break;
-    case 1:
-      tree->right = avl_tree_insert(tree->right, value);
-      break;
-    default:
-      return tree;
-  }
-
-  tree->height = 1 + max(height_of(tree->left), height_of(tree->right));
-  return rebalance(tree, value);
-}
-
 AVLTree *avl_tree_delete(AVLTree *tree, int value) {
   if (tree == NULL)
     return tree;
diff --git a/src/03/avl_tree_test.c b/src/03/avl_tree_test.c
index a8f838f..624c078 100644
--- a/src/03/avl_tree_test.c
+++ b/src/03/avl_tree_test.c
@@ -332,8 +332,11 @@ TestSuite *avl_tree_tests() {
   return x;
 }
 
+TestSuite *rb_tree_tests();
+
 int main(int argc, char **argv) {
   TestSuite *suite = create_test_suite();
   add_suite(suite, avl_tree_tests());
+  add_suite(suite, rb_tree_tests());
   return run_test_suite(suite, create_text_reporter());
 }
diff --git a/src/03/rb_tree.c b/src/03/rb_tree.c
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/03/rb_tree.c
diff --git a/src/03/rb_tree.h b/src/03/rb_tree.h
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/03/rb_tree.h
diff --git a/src/03/rb_tree_test.c b/src/03/rb_tree_test.c
new file mode 100644
index 0000000..6ce05f4
--- /dev/null
+++ b/src/03/rb_tree_test.c
@@ -0,0 +1,13 @@
+#include "rb_tree.h"
+#include <cgreen/cgreen.h>
+#include <string.h>
+
+Ensure(one_equals_one) {
+  assert_that(1, is_equal_to(1));
+}
+
+TestSuite *rb_tree_tests() {
+  TestSuite *x = create_test_suite();
+  add_test(x, one_equals_one);
+  return x;
+}