diff options
| author | mo khan <mo.khan@gmail.com> | 2020-09-26 19:41:17 -0600 |
|---|---|---|
| committer | mo khan <mo.khan@gmail.com> | 2020-09-26 19:41:17 -0600 |
| commit | bfcc2fa03262f728e0f0e718f93a229aef3f5a28 (patch) | |
| tree | c5c76b139bf81baf23e86cf31df6aff53aa4cace /src/03/README.md | |
| parent | 36d01edd61921f98a81ffabbc6abac3cf4503381 (diff) | |
01 -> README
Diffstat (limited to 'src/03/README.md')
| -rw-r--r-- | src/03/README.md | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/src/03/README.md b/src/03/README.md new file mode 100644 index 0000000..9036d27 --- /dev/null +++ b/src/03/README.md @@ -0,0 +1,51 @@ +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:b) + / \ --> / \ + (15:2) (30:2) (15:b) (30:b) + / \ \ / \ \ +(10:1) (17:1) (35:1) (10:r) (17:r) (35:r) + +* perform pre order traversal +* assign colour of Red/Black node based on height of each AVL node + +Step 1: + (20:b) + +Step 2: + (20:b) + / + (15:b) + +Step 3: + (20:b) + / + (15:b) + / + (10:r) + +Step 4: + (20:b) + / + (15:b) + / \ + (10:r) (17:r) + +Step 5: + (20:b) + / \ + (15:b) (30:b) + / \ + (10:r) (17:r) + +Step 6: + (20:b) + / \ + (15:b) (30:b) + / \ \ + (10:r) (17:r) (35:r) +``` |