algorithm - 在没有旋转的情况下保持avl树平衡

Question

B树和AVL树一样是自平衡树。 HERE我们可以看到如何使用左右旋转来保持 AVL 树平衡。

和HERE是解释 B 树中插入的链接。如果我没记错的话，这种插入技术不涉及任何旋转以保持树平衡。因此它看起来更简单。

问题:是否有任何类似的(或任何其他不使用旋转的技术)来保持 avl 树平衡？

Answer 1

答案是……是也不是。

B 树不需要执行轮换，因为它们对可以将多少不同的键打包到一个节点有一些松弛。当您向 B 树中添加越来越多的键时，您可以通过将这些键吸收到节点本身来避免树变得不平衡。

二叉树没有这种奢侈。如果您将一个键插入二叉树，在所有情况下它都会将该树中某个分支的高度增加 1，因为该键需要进入它自己的节点。旋转通过确保如果某些 Twig 长得太多，该高度会被混入树的其余部分，从而阻止树的整体生长。

大多数平衡的 BST 都有某种涉及轮换的再平衡策略，但并非所有人都这样做。 scapegoat tree 不直接涉及轮换的策略的一个显着示例是，它通过从主树中撕下巨大的子树，优化重建它们，然后将子树粘回主树来重新平衡。这种方法技术上不涉及任何旋转，是实现平衡树的一种非常干净的方法。

也就是说 - 替罪羊树的最节省空间的实现确实使用旋转将不平衡的树转换为完美平衡的树。您必须使用旋转来执行此操作，但如果空间有限，这可能是最好的方法。

希望这对您有所帮助!