feat: insert into red/black tree

1 files changed, 38 insertions, 0 deletions

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;
 }