From 16e6a203e6c6ff0eab758a47aa651e6f36d9ce59 Mon Sep 17 00:00:00 2001
From: mo khan <mo.khan@gmail.com>
Date: Mon, 31 Aug 2020 12:06:02 -0600
Subject: docs: document algorithm to convert AVL to Red-Black tree

---
 src/03/01/README.md | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)

(limited to 'src')

diff --git a/src/03/01/README.md b/src/03/01/README.md
index e87168f..32ada6c 100644
--- a/src/03/01/README.md
+++ b/src/03/01/README.md
@@ -1,3 +1,62 @@
 Illustrate that the nodes of any AVL tree T can be
 colored "red" and "black" so that T becomes a
 red-black tree.
+
+```plaintext
+       AVL Tree                   Red-Black Tree
+        (20:3)                      (20:r)
+        /    \          -->         /    \
+    (15:2)    (30:2)           (15:b)    (30:b)
+    /    \        \            /   \         \
+(10:1) (17:1)     (35:1)  (10:r) (17:r)      (35:r)
+
+* perform in order traversal
+* add node to red/black tree
+* assign colour of Red/Black node based on height of AVL node
+
+Step 1:
+          (20:r)
+
+Step 2:
+          (20:r)
+          /
+      (15:b)
+
+Step 3:
+          (20:r)
+          /    \
+      (15:b)    (30:b)
+
+Step 4:
+          (20:r)
+          /    \
+      (15:b)    (30:b)
+      /
+  (10:r)
+
+Step 5:
+          (20:r)
+          /    \
+      (15:b)    (30:b)
+      /   \
+  (10:r) (17:r)
+
+Step 6:
+          (20:r)
+          /    \
+      (15:b)    (30:b)
+      /   \         \
+  (10:r) (17:r)      (35:r)
+```
+
+```c
+RBTree *avl_tree_to_rb_tree(AVLTree *t) {
+  if (!t)
+    return NULL;
+
+  RBTree *r = rb_tree_initialize_with(t->value, t->height % 2 == 0 ? black : red);
+  r->left = avl_tree_to_rb_tree(t->left);
+  r->right = avl_tree_to_rb_tree(t->right);
+  return r;
+}
+```
-- 
cgit v1.2.3