I would like to know whether I am applying the following insertion and deletion operations correctly on an AVL tree:
62
/ \
44 78
/ \ \
17 50 88
/ \
48 54
For this question, a deletion replaces the deleted item with its successor.
This is how I think the tree should be modified by those operations:
insert(42) and insert(90)
62
/ \
44 78
/ \ \
17 50 88
\ / \ \
42 48 54 90
delete(62)
78
/ \
44 88
/ \ \
17 50 90
\ / \
42 48 54
insert(92)
78
/ \
44 88
/ \ \
17 50 90
\ / \ \
42 48 54 92
delete(50)
78
/ \
44 88
/ \ \
17 54 90
\ / \
42 48 92
There are a two cases where rotations are needed:
___62___
/ \
__44__ 78
/ \ \
17 50 88
/ \
48 54
You had applied insert(42) correctly, but insert(90) creates an unbalanced subtree rooted at 78 (marked with asterisk): its right side has a height of 2, while its left side is empty:
___62___
/ \
__44__ 78*
/ \ \
17 50 88
\ / \ \
42 48 54 90
So, this will not stay like that: a simple left rotation will move 88 up, and 78 down:
___62___
/ \
__44__ 88
/ \ / \
17 50 78 90
\ / \
42 48 54
You had it correct for delete(62): that will swap the root with its successor, which is 78, and then 62 is removed:
___78___
/ \
__44__ 88
/ \ \
17 50 90
\ / \
42 48 54
insert(92) will bring an unbalance at node 88:
___78___
/ \
__44__ 88*
/ \ \
17 50 90
\ / \ \
42 48 54 92
And so a simple left rotation is again applied:
___78___
/ \
__44__ 90
/ \ / \
17 50 88 92
\ / \
42 48 54
delete(50) was correctly executed. Given the above state, we get:
___78___
/ \
__44__ 90
/ \ / \
17 54 88 92
\ /
42 48