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

AVL树的插入和删除

AVL trees insertion and deletion

tree

data-structures

tree-rotation