1

我想知道我是否在 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
4

1 回答 1

0

有两种情况需要轮换：

                         ___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
于 2021-06-30T14:03:09.203 回答