From c93020800e852b17f4cf30fb867bccac88d61cbd Mon Sep 17 00:00:00 2001 From: mo khan Date: Sat, 26 Sep 2020 19:42:02 -0600 Subject: Merge 02 -> README --- src/03/02/README.md | 46 ---------------------------------------------- src/03/README.md | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 47 insertions(+), 46 deletions(-) delete mode 100644 src/03/02/README.md (limited to 'src') diff --git a/src/03/02/README.md b/src/03/02/README.md deleted file mode 100644 index f60b1ec..0000000 --- a/src/03/02/README.md +++ /dev/null @@ -1,46 +0,0 @@ -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/README.md b/src/03/README.md index 9036d27..d5f2305 100644 --- a/src/03/README.md +++ b/src/03/README.md @@ -49,3 +49,50 @@ Step 6: / \ \ (10:r) (17:r) (35:r) ``` + +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`. -- cgit v1.2.3