我有一个具有浮点距离属性的节点类。
我想要一个可以将所有节点放入其中的数据结构，并且它们将按顺序存储（例如在 AVL 树或红黑树中）。
我尝试使用排序字典，但事实证明它完全没用，因为他不能容纳两个具有相同距离的项目。
使用列表和排序 i 是不可能的，因为删除是 (O(n)) 并且找到最小值也是 (O(n))
我需要的是一个简单的通用红黑树结构，它将按我将提供的一些谓词进行排序（即比较节点内的距离）
BCL 中有这样的数据结构吗？
您想使用 c5 Collections Library 的TreeBag<T>类。它是一棵允许重复的红黑树（因此是bag而不是set）。通过项目值的索引访问是 O(log n); 插入和删除是 O(log n) 摊销的。
C5 Collection Library 由微软资助；它是开源的并且免费提供。价格合适。
实际上，您可以使用SortedDictionary它。但是你需要的（假设距离是int）是一个SortedDictionary<int, List<Item>>.
当您想添加字典中还没有的距离时，您插入一个List包含单个项目的新距离。如果要添加字典中已有的距离，请找到正确的列表并将项目添加到其中。
要删除最小的项目，请找到List具有最小键的 并从中删除一个项目。如果List变为空，则将其从字典中删除。
由于从 a 的开头删除List效率低下，您需要从 the 的末尾删除List（导致具有相同键的项目的 LIFO 顺序），或者使用 aQueue而不是List。
这可能不是最有效的解决方案，但插入、查找最小项和删除最小项都是 O(log n)。
另一种选择是跳过列表。.NET Framework 没有，但不久前我在 C# 中实现了一个。请参阅内存效率更高的跳过列表。
跳过列表具有 O(log n) 的插入、搜索和删除，以及 O(1) 的顶部项目删除。
如果您想要一个堆，请参阅A Generic Binary Heap Class。