AVL树平衡

下面给出的AVL树：AVL树平衡

它是确定只是做一个旋转40，右边？使得它是这样的：

它仍然符合托特他AVL具有财产 - 相比于左子树+ 1米的高度。

在回答它的双重旋转，在上述35的子树是这样的后：

我不明白什么时候做一个双旋转时，如果要做一个旋转他们都不违反高度属性。

来源

2011-06-14 bigubosu

+1只为凉爽的小树。 – mdm 2011-06-14 13:52:41

双转可能是由于使用了特定的AVL算法。这两个答案看起来像对我有效的AVL树。

来源

2011-06-14 14:21:11 Eric

如果原始问题仅与非平衡AVL树（而不是添加或删除节点之前的平衡树）一起提供，那么单次旋转是一个有效答案。

如果在添加或删除节点之后，问题提供了和之前的AVL树，则重新平衡算法可能会导致发生双重旋转。

来源

2011-06-14 14:24:43 monofonik

你是对的，它是继续。这是avl平衡的最后一步。在此之前还有其他步骤。好吧，我做了这个，再举几个例子。我想到在进一步继续之前可能需要填充所有具有节点的行。因此，与不填充该节点的旋转相比，填充空节点的旋转可能是有利的，但仍然不会违反 - + 1高度属性。 – bigubosu 2011-06-14 14:29:09

这两个答案是正确的，但根据我使用文献：

的四种类型的旋转LL，RR，LR和RL的。 这些旋转被特征在于最近的祖先A，所插入的节点N中的，其平衡系数变为2。

获得旋转类型的以下特征：

LL：N被插入在甲

LR的左子树的左子树：N被插入到

RR的左子树的右子树：N被插入到
的右子树的右子树
RL：N被插入的

右子树根据这些规则，最近的祖先，其平衡因子变为2是40在你的例子，和插入在制成的左子树40的左子树的左子树，因此您必须执行LL旋转。遵循这些规则，您的第一个答案将是选定的操作。

不过，两个答案都是正确的，取决于您使用的算法及其遵循的规则。

来源

2012-07-21 18:38:51 PALEN

回答

相关问题