何时选择红黑树、B-树或AVL树？

Question

何时选择红黑树、B-树或AVL树？

data-structurestreeb-treeavl-treered-black-tree

88

作为一名程序员，我何时应该考虑使用红黑树、B树或AVL树？在决定选择之前需要考虑哪些关键因素？

有人能否针对每种树结构解释一个场景，说明为什么选择它而不是其他树结构，并引用关键因素？

- Palladin

10

我很感激这个问题——目前可以选择使用fastutil IntAVLTreeSet或IntRBTreeSet。 - Yang

4个回答

20

我认为B+树是一种很好的通用有序容器数据结构，即使在主存中也是如此。即使虚拟内存不是问题，缓存友好性通常也是一个问题，而B+树对于顺序访问非常好-与链表相同的渐近性能，但缓存友好性接近简单数组。所有这些和O(log n)搜索、插入和删除。

然而，B+树确实存在问题-例如，在插入/删除时项目在节点内移动，从而使指向这些项目的指针无效。我有一个容器库，可以进行“光标维护”-光标附加到它们当前在链接列表中引用的叶节点上，因此它们可以自动修复或使无效。由于很少有一个或两个光标，所以它工作得很好-但仍然需要额外的工作。

另一件事是B+树本质上就是这样。我猜你可以根据需要剥离或重新创建非叶节点，但是使用二叉树节点可以获得更多的灵活性。二叉树可以转换为链表，然后再转换回来而不复制节点 - 你只需改变指针，然后记住你现在正在处理不同的数据结构。除此之外，这意味着您可以相对容易地进行O(n)合并树 - 将两个树转换为列表，合并它们，然后再转换回树。

还有一件事是内存分配和释放。在二叉树中，这可以与算法分开 - 用户可以创建一个节点，然后调用插入算法，删除可以提取节点（将它们从树中分离出来，但不释放内存）。在B树或B+树中，这显然行不通 - 数据将位于多项节点中。编写插入方法以“规划”操作，直到它们知道需要多少新节点并且可以分配它们为止，这是一个挑战。

红黑树 vs AVL？我不确定它是否有任何大的区别。我的自己的库有一个基于策略的“工具”类来操作节点，包括双向链表、简单二叉树、伸展树、红黑树和treaps，以及各种转换方法。其中一些方法只是因为我在某个时候感到无聊而实现的。我甚至不确定我是否测试过treap方法。我选择红黑树而不是AVL的原因是因为我个人更好地理解算法——这并不意味着它们更简单，只是历史的偶然性让我更熟悉它们。

最后一件事——我最初只是开发了我的B+树容器作为一个实验。它是那些从未真正结束的实验之一，但这不是我鼓励其他人重复的事情。如果你需要的只是一个有序容器，最好的答案是使用你现有的库提供的容器——例如C++中的std::map等。我的库经过多年的发展，花了相当长的时间才稳定下来，我最近才相对较新地发现它在技术上是不可移植的（依赖于关于offsetof的一点未定义行为）。

- user180247

5

当项目数量超过32000时，内存B-树具有优势...请查看speedtest.pdf自stx-btree。

- stan5

0

在选择数据结构时，您需要权衡以下因素：

检索速度与更新速度之间的平衡
结构处理最坏情况操作的能力，例如按排序顺序插入记录
浪费的空间

我建议首先阅读Robert Harvey引用的维基百科文章。

实际上，在使用Java等语言时，普通程序员倾向于使用提供的集合类。如果在性能调整活动中发现集合性能有问题，则可以寻找替代实现。这很少是业务驱动开发需要考虑的第一件事。极少需要手动实现此类数据结构，通常可以使用库。

- djna

1

公平地说，OP问的是“何时应该考虑使用”，而不是“何时应该考虑实现”。尽管最后一段是正确的，但在这个问题的背景下并没有提供太多价值。即使使用库，您也需要了解算法，以便有效地选择最适合您业务需求的结构。 - Dan Bechard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- blwy10 · Accepted Answer

带着一定的怀疑：

当你需要管理超过数千个项目并且从磁盘或某些较慢的存储介质进行页面处理时，请使用B-树。

当您在树上进行相当频繁的插入、删除和检索操作时，请使用RB树。

当您的插入和删除相对于检索不频繁时，请使用AVL树。