.NET 4 中是否有二叉搜索树实现？

Question

我正在寻找.NET 4中内置的二叉搜索树实现。是否有这样的实现？

- Micah

Answer 1

SortedDictionary<K,V>类使用树结构，这符合您的要求吗？请参考这个回答中的讨论。

- H H

Answer 2

您可以使用 SortedDictionary<TKey, TValue>。

- Steve Townsend

Answer 3

另一种选择是使用列表并对其进行排序。然后您可以使用BinarySearch方法查找项目。为了维护排序列表，您可以使用BinarySearch返回的索引进行插入。如果返回的索引为负数，请使用补码（~运算符）作为插入位置，如果返回的索引为正数，则可以在该位置插入（除非您希望具有集合般的行为，在这种情况下不要插入任何内容）。

- pstrjds

---

这提供了相同的搜索语义，但底层结构仍然是一个普通的列表，而不是二叉搜索树。 - Steve Townsend

好的，我在发布那篇文章时没有仔细考虑（当时只喝了一杯咖啡）。我使用List和BinarySearch以及补充索引插入来获取BST搜索语义。我应该更仔细地阅读 :) - pstrjds

Answer 4

C5库：

类TreeDictionary实现接口ISortedDictionary，使用有序平衡红黑二叉树表示（key，value）对或条目的字典。访问、删除和插入条目的时间复杂度为O(logn)。枚举树形字典的键、值或条目遵循键比较器确定的键顺序。

- QrystaL

Answer 5

http://code.google.com/p/self-balancing-avl-tree/。基于AVL树实现平衡的AVL树，包括连接和分割操作，以及基于AVL树的SortedDictinary和SortedMultiDictionary。

- ros