feat: insert into red/black tree

3 files changed, 56 insertions, 2 deletions

diff --git a/src/03/rb_tree.c b/src/03/rb_tree.c
index 811192d..4185da9 100644
--- a/src/03/rb_tree.c
+++ b/src/03/rb_tree.c
@@ -1,5 +1,6 @@
 #include "rb_tree.h"
 #include <stdlib.h>
+#include <stdio.h>
 
 RBTree *rb_tree_initialize(int value) {
   RBTree *tree = malloc(sizeof(RBTree));
@@ -9,3 +10,17 @@ RBTree *rb_tree_initialize(int value) {
   tree->value = value;
   return tree;
 }
+
+RBTree *rb_tree_insert(RBTree *tree, int value) {
+  if (tree == NULL)
+    return rb_tree_initialize(value);
+
+  if (value < tree->value) {
+    tree->left = rb_tree_insert(tree->left, value);
+  } else if (value > tree->value) {
+    tree->right = rb_tree_insert(tree->right, value);
+  } else {
+    printf("KABOOM");
+  }
+  return tree;
+}
diff --git a/src/03/rb_tree.h b/src/03/rb_tree.h
index 0945c36..f818232 100644
--- a/src/03/rb_tree.h
+++ b/src/03/rb_tree.h
@@ -1,4 +1,4 @@
-enum colour {
+enum Colour {
   black = 0x01,
   red = 0x00,
 };
@@ -6,8 +6,9 @@ enum colour {
 typedef struct rb_node {
   struct rb_node *left;
   struct rb_node *right;
-  enum colour colour;
+  enum Colour colour;
   int value;
 } RBTree;
 
 RBTree *rb_tree_initialize(int value);
+RBTree *rb_tree_insert(RBTree *tree, int value);
diff --git a/src/03/rb_tree_test.c b/src/03/rb_tree_test.c
index 4d5d989..ebaa262 100644
--- a/src/03/rb_tree_test.c
+++ b/src/03/rb_tree_test.c
@@ -6,6 +6,22 @@
  * Root of the tree is always black.
  * There are no two adjacent red nodes. (red node cannot have red parent or child)
  * Every path from root to child NULL node has same # of black nodes.
+ *
+ *
+ * 1. every node is coloured red or black.
+ * 2. All leaves (nils) are black.
+ * 3. Every red node has black children. black nodes can have any color children.
+ * 4. From any node, the # of black nodes on any path to the leaves is the same. (same # of black nodes from top to bottom)
+
+height: logn if perfectly balanced.
+
+            (B)
+          /     \
+       (R)       (R)
+      /   \     /   \
+    (B)  (B)  (B)   (B)
+   /  \
+(nil) (nil)
  */
 
 Ensure(one_equals_one) {
@@ -20,9 +36,31 @@ Ensure(initialize_returns_a_new_tree) {
   assert_that(tree->colour, is_equal_to(black));
 }
 
+Ensure(insert_returns_a_new_tree_when_null) {
+  RBTree *tree = rb_tree_insert(NULL, 20);
+
+  assert_that(tree, is_not_equal_to(NULL));
+  assert_that(tree->value, is_equal_to(20));
+  assert_that(tree->colour, is_equal_to(black));
+}
+
+Ensure(insert_adds_a_new_item) {
+  RBTree *tree = rb_tree_initialize(10);
+
+  tree = rb_tree_insert(tree, 20);
+
+  assert_that(tree, is_not_equal_to(NULL));
+  assert_that(tree->value, is_equal_to(10));
+  assert_that(tree->colour, is_equal_to(black));
+  assert_that(tree->right, is_not_equal_to(NULL));
+  assert_that(tree->right->value, is_equal_to(20));
+}
+
 TestSuite *rb_tree_tests() {
   TestSuite *x = create_test_suite();
   add_test(x, one_equals_one);
   add_test(x, initialize_returns_a_new_tree);
+  add_test(x, insert_returns_a_new_tree_when_null);
+  add_test(x, insert_adds_a_new_item);
   return x;
 }