Bee：一套基于自平衡二叉树的字典
4.90/5 (9投票s)
C# 中的 B 树、AVL 树和 Splay 树
引言
虽然 .NET 的 Dictionary<TKey,TValue> 类不像 BCL 的集合系列那样被广泛使用，但 SortedDictionary<TKey, TValue> 却是 BCL 集合系列中一个重要的组成部分。
然而，框架类在排序和搜索二叉树方面只提供了红黑树算法供你使用。
有时，B 树、AVL 树或 Splay 树会更合适。但如果需要这些，BCL 就无能为力了。
因此，我开发了一些类来填补这个空白，主要是通过移植、调试和重写 https://www.geeksforgeeks.org 中的大量代码（源代码中包含不同部分的具体链接），以便我能够学习这些算法。
背景
二叉树在许多（如果不是大多数）搜索和排序算法中至关重要，因为分而治之是遍历有序数据的有效策略。多年来，已经开发出几种变体，以优化它们在特定类型搜索中的性能。
二叉树垂直排序项目，形成一种二维遍历图，这样在最坏情况下无需比较所有项目，而只需比较 N 个项目，其中 N 是树的高度。上面的树最多需要 4 次比较。
有很多方法可以构建上述树的等效结构，但所有替代方案的最大高度都会高于此树，需要更多的比较。这棵树是理想的。它被称为平衡。平衡树能够将最少的比较次数分布到所有项目中。
假设我们要将 15 添加到上面的图中。有两个有效的位置可以添加它。可以将其添加到 7 的下方，14 的右侧，或者可以将其添加到 14 的下方。后者会使树更高，这不是我们想要的。
我们想要的是一个算法，能够始终将节点添加到最优化位置，或者始终保持树的平衡或尽可能短。提供的每种算法都有其独特的方法来实现这一点。
B 树的诀窍在于它将二叉树“压缩”成不再是纯粹的二叉结构。
请注意，有些节点包含多个数字/键。B 树这样做是为了保持树的矮胖，并最大程度地减少对叶节点的访问。数据库喜欢它们，因为数据库索引中的叶节点通常与磁盘块相关联，因此访问次数越少越好。
B 树真正的优势在于搜索和排序大量项目，这就是为什么 B 树是数据库系统的基础组成部分。其性能在处理大约 30,000 个项目后开始显现。达到一百万个项目时，即使 Dictionary<TKey,TValue> 执行的工作量远少于 B 树（因为它不需要排序），B 树的性能也能超越它。它在大约 100 个项目后就能超越 SortedDictionary<TKey,TValue>。但是，添加和删除操作速度较慢。它并非严格意义上的二叉树，但使用了许多相同的基本原理，并且非常相似。其主要区别在于每个节点可以存储两个以上的键和项目，并且倾向于变胖而不是变高。
AVL 树看起来像标准的二叉树，但在插入或删除时会旋转树的部分，以保持树的平衡。
AVL 树的优势与 B 树类似，但规模较小。它在大约 10 个项目后就能追上 SortedDictionary<TKey, TValue>，在 100 个项目后就能超越它。当你进行插入和删除操作的次数远少于搜索操作时，使用它会很有好处。
Splay 树看起来与标准二叉树完全相同，但它会旋转子部分，甚至整个树。最后操作（插入、删除或搜索）的节点将成为根节点。这为 Splay 树提供了极佳的局部性，因为其键和相邻键都非常靠近根节点。
如前所述，Splay 树的优势在于其极佳的局部性。这意味着如果你频繁搜索相同的项目或彼此靠近的项目，Splay 树可能是你的最佳选择。我提供的实现目前无法处理大量项目。在项目数量介于 5,000 到 10,000 之间时，由于算法的工作方式，你会遇到堆栈溢出异常。我计划最终将有问题的例程转换为非递归形式，但目前此限制仍然存在。无论如何，这些树都不太适合处理大量项目。它是否能超越 SortedDictionary<TKey, TValue> 取决于其使用方式。我提供的性能测试更像是这些树的中等或最差情况场景，所以在查看数据时，请牢记这一点。
Using the Code
使用这些代码几乎与使用任何 IDictionary<TKey,TValue> 类完全相同。这些类中的每一个都实现了该接口，公开了标准的字典操作，如 ContainsKey() 和 TryGetValue()，主要附加的限制是项目始终以键的顺序返回，就像 SortedDictionary<TKey,TValue> 那样。然而，有一个主要的区别。这些字典要求提供一个 IComparable<TKey> 实例，或者要求 TKey 类型是可比较的，而不仅仅是可相等。此限制也与 SortedDictionary<TKey, TValue> 共享。
像这样使用它们：
var d = new SortedBTreeDictionary<int,string>();
d.Add(1,"foo");
d.Add(100,"bar");
Console.WriteLine(d[100]);
历史
- 2019 年 9 月 13 日 - 首次提交