Вставка и удаление деревьев AVL

Question

Я хотел бы знать, правильно ли я применяю следующие операции вставки и удаления в дереве AVL:

                                 62
                          /  \
                        44    78
                       /  \     \
                     17    50    88
                          /  \
                        48    54

• вставка (42)
• вставка (90)
• удалить (62)
• вставка (92)
• удалить (50)

В этом вопросе при удалении удаленный элемент заменяется его преемником .

Вот как, я думаю, эти операции должны изменять дерево:

вставка (42) и вставка (90)

                                 62
                          /  \
                        44    78
                       /  \     \
                     17    50    88
                       \   /  \    \
                       42 48  54    90

       

удалить (62)

                                 78
                          /  \
                        44    88
                       /  \     \
                     17    50    90
                       \   /  \    
                       42 48  54    

вставка (92)

                                 78
                          /  \
                        44    88
                       /  \     \
                     17    50    90
                       \   /  \    \  
                       42 48  54    92

удалить (50)

                                 78
                          /  \
                        44    88
                       /  \     \
                     17    54    90
                       \   /       \  
                       42 48        92

Answer 1

Есть два случая, когда необходимы ротации:

                               ___62___
                        /        \
                     __44__      78
                    /      \       \
                   17      50      88
                          /  \
                         48  54

Вы подали заявку insert(42) правильно, но insert(90) создает несбалансированное поддерево с корнем 78(отмечено звездочкой): его правая сторона имеет высоту 2, а его левая сторона пуста:

                               ___62___
                        /        \
                     __44__      78*
                    /      \       \
                   17      50      88
                     \    /  \       \
                     42  48  54       90

Так что так не останется: простое вращение влево переместит на 88 вверх и на 78 вниз:

                               ___62___
                        /        \
                     __44__      88
                    /      \    /  \
                   17      50  78  90
                     \    /  \    
                     42  48  54    

У вас это было правильно для delete(62): это заменит корень на его преемника, который равен 78, а затем 62 удаляется:

                               ___78___
                        /        \
                     __44__      88
                    /      \       \
                   17      50      90
                     \    /  \    
                     42  48  54   

insert(92) принесет дисбаланс в узле 88:

                               ___78___
                        /        \
                     __44__      88*
                    /      \       \
                   17      50      90
                     \    /  \       \
                     42  48  54      92

И снова применяется простое левое вращение:

                               ___78___
                        /        \
                     __44__      90
                    /      \    /  \
                   17      50  88  92
                     \    /  \       
                     42  48  54      

delete(50)был правильно выполнен. Учитывая вышеуказанное состояние, мы получаем:

                               ___78___
                        /        \
                     __44__      90
                    /      \    /  \
                   17      54  88  92
                     \    /         
                     42  48