diff options
| author | mo khan <mo.khan@gmail.com> | 2020-09-20 19:33:31 -0600 |
|---|---|---|
| committer | mo khan <mo.khan@gmail.com> | 2020-09-20 19:33:31 -0600 |
| commit | 2b736960d962bb4ef51d8308c7a3ea3eca5cfdaf (patch) | |
| tree | bbfb3687d1bfd0408437beebcab562a225971d15 | |
| parent | 937998ed9985ba4a8babec55e9b7e17730d49d8f (diff) | |
docs: add visual for each AVL rotation
| -rw-r--r-- | src/03/02/README.md | 42 | ||||
| -rw-r--r-- | src/03/avl_tree_test.c | 2 |
2 files changed, 43 insertions, 1 deletions
diff --git a/src/03/02/README.md b/src/03/02/README.md index eebaa47..f60b1ec 100644 --- a/src/03/02/README.md +++ b/src/03/02/README.md @@ -1,4 +1,46 @@ Illustrate that via AVL single rotation, any binary search tree T1 can be transformed into another search tree T2 (with the same items). +Left rotation: + +```plaintext + (10) (20) + \ / \ + (20) -> (10) (30) + \ + (30) +``` + +Right rotation: + +```plaintext + (30) (20) + / / \ + (20) --> (10) (30) + / +(10) +``` + +Left-Right rotation: + +```plaintext + (30) (20) + / / \ +(10) -> (10) (30) + \ + (20) +``` + +Right-Left rotation: + +```plaintext +(10) (20) + \ / \ + (30) --> (10) (30) + / +(20) +``` + Give an algorithm to perform this transformation using O(N log N) rotation on average. + +See `./../avl_tree.c`. diff --git a/src/03/avl_tree_test.c b/src/03/avl_tree_test.c index d0c675e..2c375cc 100644 --- a/src/03/avl_tree_test.c +++ b/src/03/avl_tree_test.c @@ -94,7 +94,7 @@ Ensure(insert_performs_a_right_left_rotation) { \ / \ (30) --> (10) (30) / - (20) +(20) */ AVLTree *tree = avl_tree_initialize(10); tree = avl_tree_insert(tree, 30); |
