作为程序员，我什么时候应该考虑使用 RB 树、B-树或 AVL 树？在决定选择之前需要考虑哪些关键点？
有人可以为每个树结构解释一个场景，为什么参考关键点选择它而不是其他树结构？
问问题
29749 次
4 回答
116
用一小撮盐吃这个：
当您管理超过数千个项目并从磁盘或某些慢速存储介质中分页时，B 树。
RB 树，当您在树上进行相当频繁的插入、删除和检索时。
当您的插入和删除相对于您的检索不频繁时，AVL 树。
于 2009-10-19T16:02:25.493 回答
20
我认为 B+ 树是一种很好的通用有序容器数据结构，即使在主内存中也是如此。即使虚拟内存不是问题，缓存友好性通常也是如此，并且 B+ 树对于顺序访问特别好 - 与链表相同的渐近性能，但缓存友好性接近简单数组。所有这些和 O(log n) 搜索、插入和删除。
但是，B+ 树确实存在问题 - 例如，当您进行插入/删除时，项目在节点内移动，从而使指向这些项目的指针无效。我有一个执行“游标维护”的容器库 - 游标将自身附加到它们当前在链表中引用的叶节点，因此它们可以自动修复或失效。由于很少有超过一两个游标，所以它运行良好 - 但它仍然需要额外的工作。
另一件事是 B+ 树本质上就是这样。我想你可以根据你是否需要它们来剥离或重新创建非叶节点，但是使用二叉树节点你可以获得更多的灵活性。二叉树可以在不复制节点的情况下转换为链表并返回 - 您只需更改指针然后记住您现在将其视为不同的数据结构。除其他外，这意味着您可以相当容易地 O(n) 合并树 - 将两棵树都转换为列表，合并它们，然后再转换回树。
还有一件事是内存分配和释放。在二叉树中，这可以从算法中分离出来——用户可以创建一个节点然后调用插入算法，删除可以提取节点（将它们从树中分离，但不释放内存）。在 B-tree 或 B+-tree 中，这显然是行不通的——数据将存在于一个多项目节点中。编写插入方法来“计划”操作而不修改节点，直到他们知道需要多少新节点并且可以分配它们是一个挑战。
红黑与AVL？我不确定这有什么大的不同。我自己的库有一个基于策略的“工具”类来操作节点，具有用于双链表、简单二叉树、展开树、红黑树和陷阱的方法，包括各种转换。其中一些方法只是因为我有时感到无聊而实施。我不确定我什至测试过陷阱方法。我选择红黑树而不是 AVL 的原因是因为我个人对算法的理解更好——这并不意味着它们更简单，我对它们更熟悉只是历史的侥幸。
最后一件事——我最初只是开发我的 B+ 树容器作为一个实验。这是从未真正结束的实验之一，但我不鼓励其他人重复。如果您只需要一个有序容器，最好的答案是使用您现有库提供的容器 - 例如 C++ 中的 std::map 等。我的库经过多年的发展，花了很长时间才稳定下来，而且我最近才发现它在技术上是不可移植的（依赖于一些未定义的行为 WRT offsetof）。
于 2009-11-04T23:19:59.040 回答
5
在内存中 B-Tree 在项目数超过 32000 时具有优势...查看stx -btree中的speedtest.pdf。
于 2014-01-08T00:20:08.533 回答
0
在选择数据结构时，您需要权衡一些因素，例如
- 检索速度 v 更新速度
- 结构如何处理最坏情况的操作，例如插入以排序顺序到达的记录
- 空间浪费
我将从阅读 Robert Harvey 引用的 Wikipedia 文章开始。
务实地说，当使用 Java 等语言工作时，普通程序员倾向于使用提供的集合类。如果在性能调整活动中发现收集性能存在问题，则可以寻求替代实现。这很少是业务主导的开发必须考虑的第一件事。需要手动实现这样的数据结构是非常罕见的，通常有可以使用的库。
于 2009-10-19T16:13:13.710 回答