1

我有以下 AVL 树：

                               10
                             /    \
                            5     12
                           / \   /  \
                          2  8   11  13
                        /  \ /\   
                        1  4 7 9

如果我插入 3 那么我得到：

                               10
                             /    \
                            5     12
                           / \   /  \
                          2  8   11  13
                        /  \ /\   
                        1  4 7 9
                          /
                         3

如果我计算每个节点的平衡因子，似乎每个 BF 都是有效的： (Node:BF) -> 10:1, 5:0, 2:-1, 1:0, 4:-1, 8:0, 7:0, 9:0, 3:0, 12:0, 11:0, 13:0 但显然这棵树需要重新平衡。哪里有无效的BF，然后如何进行必要的旋转。

4

1 回答 1

1

10 的平衡因子应为 2，其左子树为 5-2-4-3，右子树为 12-13。单次旋转后的有效树可能看起来像 5 | 2 10 | 1 4 8 12 | 无 无 3 无 7 9 11 13。

一种可能的重新平衡方法是 cut-link-algorithm： 1. 将不平衡节点命名为 z，其中一个是它的子节点 y，另一个是它的子节点的子节点 x。2. 将节点重命名为a, b, c inorder-traversal 并让它们的子节点从左到右分别为T0, T1, T2, T3。3. 设置 b 为新根，a 为其左孩子，c 为其右孩子。4. 追加从左到右对应的四个子树T0、T1、T2和T3。

于 2011-02-02T22:59:14.703 回答