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 /src/03/02 | |
| parent | 937998ed9985ba4a8babec55e9b7e17730d49d8f (diff) | |
docs: add visual for each AVL rotation
Diffstat (limited to 'src/03/02')
| -rw-r--r-- | src/03/02/README.md | 42 |
1 files changed, 42 insertions, 0 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`. |
