B 树是类似于 AVL 树的自平衡树。在这里，我们可以看到如何使用左右旋转来保持 AVL 树的平衡。
这里是一个解释插入 B 树的链接。如果我没记错的话，这种插入技术不涉及任何旋转，以保持树平衡。因此它看起来更简单。
问题：是否有任何类似的（或任何其他不使用旋转的技术）来保持 avl 树的平衡？
问问题
2448 次
2 回答
5
答案是……是的，不是的。
B-trees 不需要执行旋转，因为它们在可以将多少个不同的键打包到一个节点中时有一些松弛。随着您将越来越多的键添加到 B 树中，您可以通过将这些键吸收到节点本身来避免树变得不平衡。
二叉树没有这种奢侈。如果您将一个键插入二叉树，它会在所有情况下将该树中某个分支的高度增加 1，因为该键需要进入它自己的节点。旋转通过确保如果某些树枝长得太多，则该高度被拖入树的其余部分来对抗树的整体生长。
大多数平衡的 BST 都有某种涉及轮换的再平衡策略，但并非所有人都这样做。不直接涉及旋转的策略的一个值得注意的例子是替罪羊树，它通过从主树中撕下巨大的子树来重新平衡，优化重建它们，然后将子树粘回到主树中。这种方法在技术上不涉及任何旋转，并且是实现平衡树的一种非常干净的方法。
也就是说 - 替罪羊树的最节省空间的实现确实使用旋转将不平衡的树转换为完美平衡的树。您不必使用旋转来执行此操作，但如果空间很短，这可能是最好的方法。
希望这可以帮助！
于 2015-02-23T20:15:24.660 回答
0
旋转可以变得简单（如果您只需要简单）。
如果留下插入流量，则余额-1 是红灯。
如果插入流量正确，则余额 1 是红灯。
这是归一化基本 AVL 平衡的（简化）粗粒度（2-adic 四舍五入）：
{left,even,right} ~ {low,even,high} ~ {green,green,red}
走插入路线并旋转每个红灯（插入前）。如果下一个灯是绿色的，您只需将红灯旋转 1 或 2 次。您可能必须在每次旋转之前重新平衡下一个子树，因为内部子树是不变的。这很简单，但需要很长时间。您必须在每次旋转之前向下移动绿灯。您始终可以将绿灯向下移动到根部，并且可以旋转树顶以生成新的绿灯。
红灯旋转自然地向下移动绿灯。
此时，您只有插入的绿灯。
这种朴素方法的成本结构在拓扑上简化为
df(h)/dh=∫f(h)dh
如 sin(h)、sinh(h) 等。
于 2021-10-25T00:41:35.103 回答