feat: prove that height of binary tree is greater than or equal to log2(k) where k is the # of leaves in the tree

8 files changed, 141 insertions, 46 deletions

diff --git a/src/03/08/README.md b/src/03/08/README.md
index b2eecc3..3cf319c 100644
--- a/src/03/08/README.md
+++ b/src/03/08/README.md
@@ -1,45 +1,23 @@
-
 Prove that a binary tree with `k` leaves has height at least `log k`.
 
-```plaintext
-tree = h(k)
-assert(height(tree) == log k)
-
-for each positive natural number this is true.
-```
-
-```c
-BTree *h(int k)
-{
-  BTree *tree = rb_tree_initialize();
-  // assert(true == true);
-  // generate k leaves with random data
-  return tree;
-}
-
-for (int k = 0; k < 1000; k++) {
-  assert(height(h(k)) >= log(k))
-}
-```
+The proof can be derived with the following.
+Suppose we have a function `h` that takes input `k`
+and returns a tree with `k` leaves.
 
+For each positive natural number we can
+assert that the height of the tree must greater
+than or equal to `log2(k)`.
 
 ```plaintext
-n: 3
-h: 3
-
-(x)
-  \
-  (y)
-    \
-    (z)
-
-n: 3
-k: 2
-h: 2
+for each positive natural number
+  assert(height(h(k)) >= log2(k))
+```
 
-    (y)
-   /   \
-(x)     (z)
+An example test is provided in `btree_test.c` that
+asserts that this holds true for the first
+500 positive integers.
 
-2^x == 2
+```c
+for (int k = 0; k < 500; ++k)
+  assert_that(btree_height(btree_generate(k)) >= log2(k), is_equal_to(true));
 ```
diff --git a/src/03/Makefile b/src/03/Makefile
index c3aae26..5c796a1 100644
--- a/src/03/Makefile
+++ b/src/03/Makefile
@@ -2,18 +2,18 @@
 SHELL=/bin/sh
 
 CC=clang
-TEST_LIBS = -lcgreen
+TEST_LIBS = -lcgreen -lm
 
 BUILDDIR := build
-OBJS := $(addprefix $(BUILDDIR)/,avl_tree.o rb_tree.o sort.o graph.o matrix.o meldable_heap.o)
-TEST_OBJS := $(addprefix $(BUILDDIR)/,avl_tree_test.o rb_tree_test.o sort_test.o graph_test.o matrix_test.o meldable_heap_test.o)
+OBJS := $(addprefix $(BUILDDIR)/,avl_tree.o rb_tree.o sort.o graph.o matrix.o meldable_heap.o btree.o)
+TEST_OBJS := $(addprefix $(BUILDDIR)/,avl_tree_test.o rb_tree_test.o sort_test.o graph_test.o matrix_test.o meldable_heap_test.o btree_test.o)
 
 $(BUILDDIR)/%.o : %.c
 	$(COMPILE.c) $(OUTPUT_OPTION) $<
 
 .PHONY: all
 all: $(OBJS) $(BUILDDIR)/main.o
-	$(CC) $(OBJS) $(BUILDDIR)/main.o -o $(BUILDDIR)/program
+	$(CC) $(OBJS) $(BUILDDIR)/main.o $(TEST_LIBS) -o $(BUILDDIR)/program
 
 .PHONY: test
 test: $(OBJS) $(TEST_OBJS)
diff --git a/src/03/avl_tree_test.c b/src/03/avl_tree_test.c
index 857ae7c..3eb3bec 100644
--- a/src/03/avl_tree_test.c
+++ b/src/03/avl_tree_test.c
@@ -379,15 +379,17 @@ TestSuite *avl_tree_tests() {
   return x;
 }
 
+TestSuite *btree_tests();
 TestSuite *graph_tests();
 TestSuite *matrix_tests();
+TestSuite *meldable_heap_tests();
 TestSuite *rb_tree_tests();
 TestSuite *sort_tests();
-TestSuite *meldable_heap_tests();
 
 int main(int argc, char **argv) {
   TestSuite *suite = create_test_suite();
   add_suite(suite, avl_tree_tests());
+  add_suite(suite, btree_tests());
   add_suite(suite, graph_tests());
   add_suite(suite, matrix_tests());
   add_suite(suite, meldable_heap_tests());
diff --git a/src/03/btree.c b/src/03/btree.c
new file mode 100644
index 0000000..a7b960d
--- /dev/null
+++ b/src/03/btree.c
@@ -0,0 +1,70 @@
+#include "btree.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+static void inspect(BTree *tree, int level) {
+  if (!tree)
+    return;
+
+  for (int i = 0; i < level; i++)
+    printf("  ");
+
+  printf("%2d\n", tree->data);
+  inspect(tree->left, level + 1);
+  inspect(tree->right, level + 1);
+}
+
+BTree *btree_initialize(int data) {
+  BTree *tree = malloc(sizeof(BTree));
+  tree->left = NULL;
+  tree->right = NULL;
+  tree->data = data;
+  return tree;
+}
+
+BTree *btree_insert(BTree *tree, int data) {
+  if (!tree)
+    return btree_initialize(data);
+
+  if (data <= tree->data)
+    if (tree->left)
+      btree_insert(tree->left, data);
+    else
+      tree->left = btree_initialize(data);
+  else if (tree->right)
+    btree_insert(tree->right, data);
+  else
+    tree->right = btree_initialize(data);
+
+  return tree;
+}
+
+int btree_height(BTree *tree) {
+  if (tree == NULL)
+    return 0;
+
+  int left = btree_height(tree->left);
+  int right = btree_height(tree->right);
+
+  return (left > right) ? left + 1 : right + 1;
+}
+
+void btree_inspect(BTree *tree) { inspect(tree, 0); }
+
+int btree_leaves(BTree *tree) {
+  if (tree == NULL)
+    return 0;
+
+  if (tree->left == NULL && tree->right == NULL)
+    return 1;
+
+  return btree_leaves(tree->left) + btree_leaves(tree->right);
+}
+
+BTree *btree_generate(int leaves) {
+  BTree *tree = NULL;
+
+  while (btree_leaves(tree) < leaves)
+    tree = btree_insert(tree, rand());
+  return tree;
+}
diff --git a/src/03/btree.h b/src/03/btree.h
new file mode 100644
index 0000000..ab08b9f
--- /dev/null
+++ b/src/03/btree.h
@@ -0,0 +1,11 @@
+typedef struct node {
+  struct node *left;
+  struct node *right;
+  int data;
+} BTree;
+
+BTree *btree_initialize(int data);
+BTree *btree_insert(BTree *tree, int data);
+int btree_height(BTree *tree);
+void btree_inspect(BTree *tree);
+BTree *btree_generate(int leaves);
diff --git a/src/03/btree_test.c b/src/03/btree_test.c
new file mode 100644
index 0000000..167bc2a
--- /dev/null
+++ b/src/03/btree_test.c
@@ -0,0 +1,37 @@
+#include "btree.h"
+#include "rb_tree.h"
+#include <cgreen/cgreen.h>
+#include <string.h>
+#include <math.h>
+
+Ensure(initialize_returns_new_btree) {
+  BTree *tree = btree_initialize(10);
+
+  assert_that(tree, is_not_equal_to(NULL));
+  assert_that(tree->data, is_equal_to(10));
+}
+
+Ensure(height_returns_height_of_tree) {
+  BTree *tree = NULL;
+
+  int n = 10;
+  for (int i = 0; i < n; ++i)
+    tree = btree_insert(tree, i);
+
+  assert_that(btree_height(tree), is_equal_to(n));
+}
+
+Ensure(tree_with_k_leaves_has_height_of_log_k) {
+  for (int k = 0; k < 500; ++k)
+    assert_that(btree_height(btree_generate(k)) >= log2(k), is_equal_to(true));
+}
+
+TestSuite *btree_tests() {
+  TestSuite *x = create_test_suite();
+
+  add_test(x, initialize_returns_new_btree);
+  add_test(x, height_returns_height_of_tree);
+  add_test(x, tree_with_k_leaves_has_height_of_log_k);
+
+  return x;
+}
diff --git a/src/03/matrix_test.c b/src/03/matrix_test.c
index 0958df7..9397070 100644
--- a/src/03/matrix_test.c
+++ b/src/03/matrix_test.c
@@ -24,9 +24,8 @@ Ensure(every_edge_is_traversed_in_both_directions_at_least_once) {
     {0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0},
   };
 
-  matrix_inspect(n, graph);
   matrix_traverse(n, graph, visited, 0);
-  matrix_inspect(n, graph);
+  printf("\n");
 
   for (int i = 0; i < n; ++i)
     for (int j = 0; j < n; ++j)
diff --git a/src/03/meldable_heap_test.c b/src/03/meldable_heap_test.c
index a8503e0..f3115af 100644
--- a/src/03/meldable_heap_test.c
+++ b/src/03/meldable_heap_test.c
@@ -73,9 +73,7 @@ Ensure(remove_removes_the_node_from_the_tree) {
   for (int i = 1; i <= 10; ++i)
     heap = meldable_heap_add(heap, i);
 
-  meldable_heap_inspect(heap);
   meldable_heap_remove(heap->right->left);
-  meldable_heap_inspect(heap);
 
   assert_that(heap->value, is_equal_to(1));