如何，如果你需要一个右右旋转或向右向左旋转

我想实现的AVL树，我有一个很难知道什么时候我需要一个RR或RL旋转（同为LL和LR）确定的。如何，如果你需要一个右右旋转或向右向左旋转

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

这是一个逻辑问题，没有必要的代码，谢谢。

我所知道的是它涉及到树被留下重或右重。但你如何确定？

来源

2012-07-01 Kalec

你具有一定的操作，例如考虑向树添加一个节点，然后保持平衡属性？ – niklon

无论是在添加还是删除，但如果我理解了其中一个，我可以想象其他人也同样容易。我希望树在任何时候都能保持平衡，但是由于它唯一修改的时间是通过添加或移除元素，所以我看不到任何其他必要的时刻。 **但我宁愿专注于现在添加元素** – Kalec

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

当添加的项目递归，在每次递归调用你应该保持的该呼叫是否添加的节点向左或右子树的轨道（通过让例如，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 
    ...

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

来源

2012-07-01 09:50:55 niklon

，所以我必须跟踪添加节点时所走的路径。这是否意味着我需要记住最后2条路径？（LL或LR等）？ – Kalec

嗯，是的，没有。是的，因为它是必要的，以便确定要执行什么旋转，不因为你并不需要“记住”它比上面pseude码 - 逻辑是这里要说的是，如果我们决定将节点添加到左子树并且添加的递归调用也决定将该项添加到其左侧子树，导致不平衡的子树必须从当前节点左移左侧。这有帮助吗？ – niklon

是的，我想我明白了。我需要首先实现这一点，但如果它确实有效（意思是我明白了你的意思），我会选择你的答案，否则我会更新这个问题。无论如何，谢谢。 – Kalec

如何，如果你需要一个右右旋转或向右向左旋转

回答

相关问题