From 00b9cfeabb70cd3db932273ddf96f705844fdf06 Mon Sep 17 00:00:00 2001
From: mo khan <mo.khan@gmail.com>
Date: Sun, 30 Aug 2020 13:20:56 -0600
Subject: feat: add function to convert avl tree to rb tree

---
 src/03/avl_tree.c      | 12 +++++++++++-
 src/03/avl_tree.h      |  3 +++
 src/03/avl_tree_test.c | 24 ++++++++++++++++++++++++
 3 files changed, 38 insertions(+), 1 deletion(-)

(limited to 'src/03')

diff --git a/src/03/avl_tree.c b/src/03/avl_tree.c
index bafe319..79205e3 100644
--- a/src/03/avl_tree.c
+++ b/src/03/avl_tree.c
@@ -168,7 +168,7 @@ static void print_tree(AVLTree *tree, int level) {
     printf(" ");
 
   if (tree) {
-    printf("(%d)\n", tree->value);
+    printf("(%d:%d)\n", tree->value, tree->height);
 
     if (!tree->left && !tree->right)
       return;
@@ -180,6 +180,16 @@ static void print_tree(AVLTree *tree, int level) {
   }
 }
 
+RBTree *avl_tree_to_rb_tree(AVLTree *tree) {
+  if (!tree)
+    return NULL;
+
+  RBTree *rb_tree = rb_tree_initialize(tree->value);
+  rb_tree->left = avl_tree_to_rb_tree(tree->left);
+  rb_tree->right = avl_tree_to_rb_tree(tree->right);
+  return rb_tree;
+}
+
 void avl_tree_inspect(AVLTree *tree) {
   print_tree(tree, 0);
 }
diff --git a/src/03/avl_tree.h b/src/03/avl_tree.h
index 66b89ad..7bc9270 100644
--- a/src/03/avl_tree.h
+++ b/src/03/avl_tree.h
@@ -1,3 +1,5 @@
+#include "rb_tree.h"
+
 typedef struct node {
   struct node *left;
   struct node *right;
@@ -10,3 +12,4 @@ int avl_tree_size(AVLTree *tree);
 AVLTree *avl_tree_insert(AVLTree *tree, int value);
 AVLTree *avl_tree_delete(AVLTree *tree, int value);
 void avl_tree_inspect(AVLTree *tree);
+RBTree *avl_tree_to_rb_tree(AVLTree *tree);
diff --git a/src/03/avl_tree_test.c b/src/03/avl_tree_test.c
index 624c078..ffe5cfc 100644
--- a/src/03/avl_tree_test.c
+++ b/src/03/avl_tree_test.c
@@ -308,6 +308,28 @@ Ensure(delete_returns_a_null_root) {
   assert_that(tree, is_equal_to(NULL));
 }
 
+Ensure(to_rb_tree_returns_a_new_red_black_tree) {
+/*
+        (20:3)                      (20:b)
+        /    \       -->            /    \
+    (15:2)    (30:2)           (15:r)    (30:r)
+    /    \        \            /   \         \
+(10:1) (17:1)     (35:1)  (10:b) (17:b)      (35:b)
+ */
+  AVLTree *tree = NULL;
+  RBTree *expected = NULL;
+  int items[] = { 20, 15, 30, 10, 17, 35};
+  int length = sizeof(items) / sizeof(items[0]);
+
+  for (int i = 0; i < length; i++) {
+    tree = avl_tree_insert(tree, items[i]);
+    expected = rb_tree_insert(expected, items[i]);
+  }
+
+  RBTree *rb_tree = avl_tree_to_rb_tree(tree);
+  assert_that(rb_equals(expected, rb_tree), is_equal_to(true));
+}
+
 TestSuite *avl_tree_tests() {
   TestSuite *x = create_test_suite();
   add_test(x, initialize_returns_new_tree);
@@ -329,6 +351,8 @@ TestSuite *avl_tree_tests() {
   add_test(x, delete_handles_a_complicated_and_large_tree);
   add_test(x, delete_handles_a_complicated_and_small_tree);
   add_test(x, delete_returns_a_null_root);
+
+  add_test(x, to_rb_tree_returns_a_new_red_black_tree);
   return x;
 }
 
-- 
cgit v1.2.3