AVL trees insertion and deletion

Question

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

• insert(42)
• insert(90)
• delete(62)
• insert(92)
• delete(50)

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

Answer 1

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