.NET内置AVL树？

Question

在.NET库中有没有内置的AVL树？

我搜索了一下，但没有找到。

• 如果有，那么在哪里？哪个命名空间？
• 如果没有，是否有C#中优秀的AVL树实现？
• 如果还是没有！那么有没有简单的方法完成它？我知道它的工作原理，并且之前已经使用原生C++构建过一个，但现在我没有时间，如果自己做可能会导致性能不佳。

- Tamer Shlash

---

你想要实现什么目标？也许有一种内置的集合类型适合你的需求。 - Oded

我需要一个平衡的层次结构，普通的二叉树不适用，但欢迎任何建议 :) - Tamer Shlash

你没有解释你将用数据结构做什么，只是提供了数据结构的需求。提供更高层次的需求会更有帮助。 - Oded

你说得对，我需要一个层次化的数据结构，其中每个节点（假设是一个边界形状）包含它的子节点，而且这个层次结构应该是平衡的，以获得最佳性能，否则可能会出现最坏情况（例如线性树）。 - Tamer Shlash

这个注释轨迹在循环运行。AVL-Tree是一种实现方式，(std)库提供了按功能命名和分类的集合。SortedDictionary基于树，但这可能会改变... - H H

Answer 1

您可以使用 System.Collections.Generic.SortedSet<T>。我认为它是使用红黑树实现的，这种数据结构与 AVL 树非常相似。

- Josef Pfleger

Answer 2

快速搜索找到了一个实现在这里。代码看起来很干净，但我还没有尝试过。

如果没有其他的选择，你可以对SortedSet<T>进行快速性能测试（如@Josef所建议的）以查看在你的使用情况下是否有任何区别。

- Matthew Strawbridge

Answer 3

可以在http://code.google.com/p/self-balancing-avl-tree/找到C#实现。同时，concat和split操作也已经实现。

- cos