summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authormo khan <mo.khan@gmail.com>2020-09-20 19:33:31 -0600
committermo khan <mo.khan@gmail.com>2020-09-20 19:33:31 -0600
commit2b736960d962bb4ef51d8308c7a3ea3eca5cfdaf (patch)
treebbfb3687d1bfd0408437beebcab562a225971d15
parent937998ed9985ba4a8babec55e9b7e17730d49d8f (diff)
docs: add visual for each AVL rotation
-rw-r--r--src/03/02/README.md42
-rw-r--r--src/03/avl_tree_test.c2
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);