我正在尝试了解 b-tree，而我能找到的每个来源似乎都忽略了有关如何在保留 b-tree 属性的同时从树中删除元素的讨论。
有人可以解释算法或指向我解释它是如何完成的资源吗？
问问题
8085 次
4 回答
3
维基百科页面上有对它的解释。 B-tree - 删除
于 2011-03-03T20:16:29.110 回答
2
如果你还没有，我强烈推荐 Carmen & al Introduction to Algorithms 3rd Edition。
它没有被描述，因为这些操作自然源于 B-Tree 属性。
由于您对节点中的元素数量有一个下限，如果删除元素违反了这个不变量，那么您需要恢复它，这通常涉及与邻居合并（或窃取它的一些元素）。
如果与邻居合并，则需要删除父节点中的元素，这会触发相同的算法。然后你递归地应用，直到你到达顶部。
B-Tree 没有重新平衡（至少不是我看到的那些），因此维护红黑树或 AVL 树要简单得多，这可能是人们不觉得有必要写下有关删除的原因。
于 2011-03-03T20:15:33.580 回答
0
您在谈论哪些 b 树？是否有连叶？此外，还有不同的移除项目的方法（自上而下、自下而上等）。本文可能会有所帮助：B-trees、Shadowing 和 Clones（尽管有许多与文件系统相关的东西）。
于 2011-03-03T20:22:32.523 回答
0
CLRS（第 2 版）的删除示例可在此处获得：http: //ysangkok.github.io/js-clrs-btree/btree.html
按“初始化书”，然后按顺序按删除按钮。这将涵盖所有情况。在按下每个按钮之前尝试预测新的树状态，并尝试识别这些案例是如何独一无二的。
于 2013-12-29T23:50:39.677 回答