保持AVL树平衡而不旋转

B树是像AVL树一样的自平衡树。 HERE我们可以看到左右旋转是如何保持AVL树平衡的。保持AVL树平衡而不旋转

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

问：是否有任何类似的（或没有使用旋转的其他技术）保持avl树平衡？

2015-02-23 Andy897

B树不是二叉树。 – amit 2015-02-23 19:00:43

（在geeksforgeeks（2nd [这里]（http://www.geeksforgeeks.org/b-tree-set-1-insert-2/）的示例中，“插入90之后”的图似乎不合时宜。）有[2-3树]（http://en.wikipedia.org/wiki/2%E2%80%933_tree） - 看看那里和B树中的删除。 – greybeard 2015-02-23 19:45:45

@greybeard他们不是二叉树 – amit 2015-02-23 20:11:37

答案是......是，否。

B树不需要执行旋转，因为它们有一些松散的问题，它们可以将多少个不同的密钥打包到节点中。随着您将越来越多的密钥添加到B树中，您可以通过将这些密钥吸收到节点本身中来避免树变得不平衡。

二叉树没有这种奢侈品。如果将密钥插入到二叉树中，则会将该树中某个分支的高度增加1，因为该密钥需要进入其自己的节点。轮作与树的整体生长作斗争，确保如果某些分支长得太多，那么高度就会被洗进树的其余部分。

大多数均衡的BST具有某种涉及轮换的重新平衡策略，但并非全部都是。一个不直接涉及旋转的策略的一个值得注意的例子是scapegoat tree，它通过将巨大的子树从主树中撕掉，最优地重建它们，然后将子树粘贴回主树来重新平衡。这种方法在技术上不涉及涉及任何旋转，并且是实现平衡树的相当干净的方式。这就是说 - 替罪羊树的空间效率最高的实现确实使用旋转将不平衡的树转换为完全平衡的树。你不要有使用旋转来做到这一点，但如果空间很短，这可能是最好的方式。

希望这会有所帮助！

来源

2015-02-23 20:15:24 templatetypedef

你好Templatetypedef，你有很大的帮助。最后一件事，在这里的例子 - http://www.geeksforgeeks.org/b-tree-set-1-insert-2/ ...我我无法理解插入“90”的方式，您可以好好看看它。 – Andy897 2015-02-24 06:05:07

保持AVL树平衡而不旋转

回答

相关问题