diff options
| author | mo khan <mo.khan@gmail.com> | 2020-09-26 19:42:02 -0600 |
|---|---|---|
| committer | mo khan <mo.khan@gmail.com> | 2020-09-26 19:42:02 -0600 |
| commit | c93020800e852b17f4cf30fb867bccac88d61cbd (patch) | |
| tree | e28c5b59533693b733c17c6c507838b8a818843a /src | |
| parent | bfcc2fa03262f728e0f0e718f93a229aef3f5a28 (diff) | |
Merge 02 -> README
Diffstat (limited to 'src')
| -rw-r--r-- | src/03/02/README.md | 46 | ||||
| -rw-r--r-- | src/03/README.md | 47 |
2 files changed, 47 insertions, 46 deletions
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`. |