Skip to content

Instantly share code, notes, and snippets.

@eduardoleon

eduardoleon/DELETE

Created March 31, 2015 11:19
Show Gist options
  • Save eduardoleon/af86424c778cd294c3e7 to your computer and use it in GitHub Desktop.
Save eduardoleon/af86424c778cd294c3e7 to your computer and use it in GitHub Desktop.
Download ZIP
2-3 tree rotations
Raw
DELETE
In all cases, the subtree marked with an asterisk is one level shallower than its siblings.
CASE 1:
--------- ---------
| 1 | 4 | | 1 | 3 |
--------- ---------
/ | \ / | \
a | e* a | \
--------- ===> ----- -----
| 2 | 3 | | 2 | | 4 |
--------- ----- -----
/ | \ / | | \
b c d b c d e
CASE 2:
--------- -----
| 1 | 3 | | 1 |
--------- -----
/ | \ / \
a ----- d* ===> a ---------
| 2 | | 2 | 3 |
----- ---------
/ \ / | \
b c b c d
CASE 3:
----- -----
| 3 | | 2 |
----- -----
/ \ / \
--------- d* ----- -----
| 1 | 2 | ===> | 1 | | 3 |
--------- ----- -----
/ | \ / | | \
a b c a b c d
CASE 4:
-----
| 2 |
----- ---------*
/ \ | 1 | 2 |
----- c* ---------
| 1 | ===> / | \
----- a b c
/ \
a b
Raw
INSERT
In all cases, the subtree marked with an asterisk is one level deeper than its siblings.
CASE 1:
--------- -----*
| 1 | 2 | | 2 |
--------- -----
/ | \ / \
a b -----* ===> ----- -----
| 3 | | 1 | | 3 |
----- ----- -----
/ \ / | | \
c d a b c d
CASE 2:
-----
| 1 |
----- ---------
/ \ | 1 | 2 |
a -----* ===> ---------
| 2 | / | \
----- a b c
/ \
b c
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment