algorithm - AVL 树 - 旋转奇怪 : Breaking BST property

Question

当我致力于 AVL 树实现时，我遇到了旋转破坏 BST 属性的情况。

我很确定我做错了什么，但我不知道它是什么。

我将 41、49、21 和 47 插入到 AVL 树中。当我再次添加 49 时，它发出“不平衡”信号，如下所示。

                 (Out of balance !!!)
                 (   at 49 L-R      )
     41                41
    /  \              /  \
   21   49  =>      21    49
       /                 /
      47               47
                         \
                          49

因此我尝试将 47 向左旋转，49 向右旋转，如下所示

          Rotate 47         Rotate 49
           to Left          to Right 
     41               41                 41
    /  \     =>      /  \      =>       /  \  
   21   49         21    49           21    49 
       /                /                  /  \
      47               49                47    49
        \             /
         49          47

树更加平衡，但我认为我在 49 的右侧有 49，从而破坏了右下子树中的 BST 属性

    49
   /  \
  47  49

我认为平衡这棵树的最佳方法如下

     47
    /  \
  41    49
  /    /
21   49

但我不知道如何使用 41-49-21-47-49 号码添加序列到达那里。也许这不是正确的结果，但我在这里迷失了。

最佳结果是什么？我应该如何实现？

有人可以告诉我我做错了什么吗？

非常感谢!!!

Answer 1

你实际上并没有做错任何事。

在评论中，你说“我认为 L 侧小于或等于当前节点值，R 侧更大。我对此有错吗？”

...是的，你错了。

对于具有重复值的树，右分支仅包含严格较大元素的条件与平衡操作不兼容。试试这个:将 20 个相同值的副本链接到一棵树中。如果您只能在左侧链接相等的值，那么您必须创建一个单链表。您的树将有 20 层深并且完全不平衡。

考虑树中重复值的方法是，树中确实没有任何重复值:-) BST 定义了总排序，以及有效的重新平衡操作，例如旋转< em>保留这个总排序。

当您将第二个 49 插入树中时，您会将其放置在第一个 49 的左侧或右侧。如果你把它放在左边，那么根据树的顺序它会更小，并且在任何重新平衡之后它总是会更小。如果你把它放在右边，那么它会更大，并且根据树的顺序保持更大。

如果你仔细想想，它一定是这样的，因为平衡操作甚至不考虑节点中的值。它们链接在一起的方式决定了顺序，并且顺序不会改变。