B树是像AVL树一样的自平衡树。 这里我们可以看到左右旋转是如何用来保持AVL树平衡的。
并且HERE是解释B树中插入的链接。如果我没记错的话，这种插入技术不涉及任何旋转来保持树平衡。因此它看起来更简单。
问题：是否有任何类似的（或任何其他不使用旋转的技术）来保持 avl 树平衡？
答案是......是和否。
B 树不需要执行旋转，因为它们在可以将多少个不同的键打包到一个节点中方面有一定的余量。当您将越来越多的键添加到 B 树中时，您可以通过将这些键吸收到节点本身来避免树变得不平衡。
二叉树没有这种优势。如果将一个键插入二叉树，则在所有情况下都会将该树中某些分支的高度增加 1，因为该键需要进入其自己的节点。旋转可以确保如果某些树枝生长过多，则该高度会被转移到树的其余部分中，从而抑制树的整体生长。
大多数平衡的 BST 都有某种涉及轮换的再平衡策略，但并非全部都有。不直接涉及旋转的策略的一个值得注意的例子是“替罪羊树”，它通过从主树中撕下巨大的子树，以最佳方式重建它们，然后将子树粘回主树来重新平衡。这种方法技术上不涉及任何旋转，并且是实现平衡树的一种非常干净的方法。 也就是说，替罪羊树的最节省空间的实现确实使用旋转将不平衡的树转换为完美平衡的树。您没有
必须使用旋转来执行此操作，但如果空间有限，这可能是最好的方法。 希望这有帮助！
如果插入流量剩余，则余额-1为红灯。
如果插入流量正确，则余额1为红灯。
这是归一化基本 AVL 平衡的（简化）粗粒度（2-adic 舍入）：
{左、偶、右} ~ {低、偶、高} ~ {绿、绿、红}
沿着插入路线行走并在每个红灯处旋转（插入之前）。如果下一盏灯是绿灯，您只需旋转红灯 1 或 2 次即可。您可能必须在每次旋转之前重新平衡下一个子树，因为内部子树是不变的。这很简单，但是需要很长时间。每次旋转前您都必须沿着绿灯移动。您始终可以将绿灯向下移动到根部，并且可以旋转树顶以生成新的绿灯。
红灯旋转自然地向下移动绿灯。
此时，插入只有绿灯。
这种朴素方法的成本结构在拓扑上简化为
df(h)/dh=∫f(h)dh
如sin(h),sinh(h)等