test: convert large avl tree to rb tree

3 files changed, 18 insertions, 6 deletions

diff --git a/src/03/avl_tree_test.c b/src/03/avl_tree_test.c
index 95e52a3..44c84ed 100644
--- a/src/03/avl_tree_test.c
+++ b/src/03/avl_tree_test.c
@@ -335,18 +335,21 @@ Ensure(to_rb_tree_returns_a_new_red_black_tree) {
 
 Ensure(to_rb_tree_handles_trees_with_a_large_depth) {
   AVLTree *subject = NULL;
-  RBTree *expected = NULL;
+  int n = 100;
 
-  for (int i = 0; i < 5; i++) {
+  for (int i = 0; i < n; i++)
     subject = avl_tree_insert(subject, i);
-    expected = rb_tree_insert(expected, i);
-  }
 
   RBTree *actual = avl_tree_to_rb_tree(subject);
 
-  assert_that(rb_equals(expected, actual), is_equal_to(true));
   assert_that(rb_tree_is_valid(actual), is_equal_to(true));
-  assert_that(rb_tree_is_valid(expected), is_equal_to(true));
+
+  for (int i = 0; i < n; i++) {
+    RBTree *node = rb_tree_find(actual, i);
+
+    assert_that(node, is_not_equal_to(NULL));
+    assert_that(node->value, is_equal_to(i));
+  }
 }
 
 TestSuite *avl_tree_tests() {
diff --git a/src/03/rb_tree.c b/src/03/rb_tree.c
index b6d0700..27430f7 100644
--- a/src/03/rb_tree.c
+++ b/src/03/rb_tree.c
@@ -268,3 +268,11 @@ int rb_tree_height(RBTree *tree) {
 
   return 1 + max(rb_tree_height(tree->left), rb_tree_height(tree->right));
 }
+
+RBTree *rb_tree_find(RBTree *t, int value) {
+  if (!t)
+    return NULL;
+
+  int x = compare(value, t->value);
+  return x == 0 ? t : rb_tree_find(x < 0 ? t->left : t->right, value);
+}
diff --git a/src/03/rb_tree.h b/src/03/rb_tree.h
index ca423a4..047873e 100644
--- a/src/03/rb_tree.h
+++ b/src/03/rb_tree.h
@@ -16,6 +16,7 @@ typedef struct rb_node {
 RBTree *rb_tree_initialize(int value);
 RBTree *rb_tree_initialize_with(int value, enum Colour colour);
 RBTree *rb_tree_insert(RBTree *tree, int value);
+RBTree *rb_tree_find(RBTree *tree, int value);
 bool rb_equals(RBTree *tree, RBTree *other_tree);
 bool rb_tree_is_valid(RBTree *tree);
 int rb_tree_size(RBTree *tree);