二叉搜索树，如何旋转这棵树来实现平衡

Question

我正在尝试旋转一棵树来保持其平衡，但我在这个例子中遇到了困难。我不太确定我在这里做错了什么。

我有一棵树，节点30的左右高度差为1。因此，我猜测这棵树是平衡的。

     30
    /  \
   20  60
  /  \
 10  25 

我在这里加了22，加完后得到了这个结果。

     30
    /  \
   20  60
  /  \
 10  25
    /
   22

在节点20处，左右高度差为1，但在节点30处高度差为2。所以，我猜它不再平衡。我试图右旋树来平衡它，但我得到了下面的树。

    20
   /  \
  10  30
     /  \
    25  60
   /
  22

旋转后，节点20仍然具有2的L/R高度差。

我做错了什么？这棵树能用旋转平衡吗？

我可以使用排序数组方法来平衡这棵树，就像下面这样，但是我对这个例子中的旋转平衡非常困惑。

     22              25
    /  \            /  \
   20   30         20   30
  /    /  \       /  \   \
 10   25  60     10  22   60

这里我做错了什么？

谢谢！

- Kay

Answer 1

这种情况需要进行双旋转：将25向上旋转两次。我假设您正在考虑AVL树，但所有标准的平衡二叉树在某些情况下都需要进行双旋转。

- David Eisenstat

Answer 2

AVL树基本上有四种旋转类型。

• 右-左
• 左-右
• 左-左
• 右-右

在你的情况下，应该使用左-右旋转。

在这里，您需要执行两个步骤。

1：从20节点左旋转。所以您的树应该如下所示。

         30
        /  \
      25  60
     / 
   20 
  /  \
 10  22

2：- 从30个节点进行右旋转。因此，您的树应如下所示。

     25
    /  \
   20   30 
  /  \   \
 10  22  60

您可以参考N网站了解其行为。这是一个关于AVL树插入的最佳链接

- Dhiral Kaniya

---

非常感谢您详细的解释，真的帮了我很多！ - Kay