实现一个平衡二叉搜索树？

Question

我已经实现了一个二叉搜索树，并想要在其插入功能中添加更多功能，以使其成为自平衡树。我正在使用C#进行编码。

请问有人能够向我推荐一些好的教程或链接吗？我做了一些搜索并找到了一些链接，但它们都不够详细。

谢谢。

- Lost

---

你在树中存储什么类型的数据，为什么？ - Lasse V. Karlsen

我建议查找红黑树。 - Jesus Ramos

我会选择AVL树。据我所知，它们比红黑树更容易实现。 - CodesInChaos

我建议查看 System.Collections.Generic.SortedList<T>。 - H H

好的，伙计们，我必须自己实现它，所以Collections.Generic.SortedList<T>对我来说不是一个好选择...有没有可用的算法？ - Lost

这里是关于自平衡二叉搜索树的MSDN库文档：http://msdn.microsoft.com/zh-cn/library/ms379573(v=vs.80).aspx - Annie

Answer 1

有很多用于自平衡搜索树的算法，其中许多算法都很复杂，而其他一些则相当简单（尽管有一些注意事项）。

Cormen、Leisserson、Rivest和Stein的书《算法导论》第二版是算法入门的绝佳教材，非常详细地介绍了红黑树。此外，它还是关于算法和数据结构的优秀书籍。

如果您对使用伸展树感兴趣，它们非常快速且实际上相当容易实现，该数据结构的原始论文非常易懂。此外，它还包括所有运行时界限的证明。

Treap是一种简单的随机平衡二叉搜索树，一旦您知道如何实现树旋转，就可以很容易地实现它。树旋转也用于伸展树中，因此值得探究。

对于AVL树，这个讲座似乎是一个不错的资源。

希望这能帮到您！

- templatetypedef

Answer 2

请查看http://code.google.com/p/self-balancing-avl-tree/，它在C#中实现了自平衡AVL树，并且还实现了连接和分割操作。

- cos