logic - 如何确定是否需要右转或右转

Question

我正在尝试实现 AVL 树，但我很难知道何时需要 RR 或 RL 轮换（LL 和 LR 相同）。

每个的先决条件是什么，它们有何不同。我知道当我看到树的图片时（直观地），但实际情况是什么？

这是一个逻辑问题，不需要代码，谢谢。

我所知道的是它涉及到左重或右重的树。但是你怎么确定呢？

Answer 1

可能有不同的解决方案，但一个如下：

递归添加项目时，在每次递归调用时，您应该跟踪该调用是将节点添加到左子树还是右子树（例如，通过让 add 函数返回它）。在递归调用之后，您检查高度不变量。如果在插入后发现在该节点处违反了它，那么您将知道不平衡的路径。

一些（不完整的）伪代码：

add(item, node):
  if item < node.value //should add to left subtree
    if node.left is empty
      //add item here
    else
      addedLeft := add(item, node.left)
      if node.left.height - node.right.height > 1
        if addedLeft
          //you know the path to the subtree causing the imbalance is LL, do a RR (single-right) rotation
        else
          //path is LR, do a LR (double-right) rotation
  ...

递归调用将从添加的节点自下而上展开，一般的想法是检查不变量在哪个节点被违反（如果有的话）。当发现该节点时，您需要知道导致不平衡的子树的路径。必须以某种方式解决该问题，这是一种解决方案。