c++ - 当以有序方式添加项目时，二叉搜索树有效地充当链表

Question

我有大量项目要存储在一个集合中。我需要通过将它与某个键进行比较来定位一个项目，然后判断是否存在这样的项目。我使用二叉搜索树来这样做。

class node
{
    public:
    node(const char *p_name) :
        greater(NULL),
        smaller(NULL),
        name(p_name)
    {}
    node *find(const char *p_name)
    {
        node *l_retval = this;

        for(; l_retval != NULL;)
        {
            int l = strcmp(p_name, l_retval->name.c_str());
            if (l == 0) break; // found it
            else
            if (l > 0) l_retval = greater; // the node searched for is in the 'greater' branch
            else l_retval = smaller; // or in the 'smaller' branch
        }
        return l_retval;
    }
    node *greater, *smaller;
    std::string name; // or any other type of data you would like to store
};

如果项目以随机方式添加，一切都很好。如果有时以有序方式添加项目，我的 BST 将充当链表(慢)。

问题是:给定一个 BST(平衡或链表样式)，我如何“平衡”BST，使其重新排列而不是有效地充当链表？

该示例是用 C++ 编写的，但该问题适用于比 C++ 本身更多的语言。

如果您提供可以帮助我的链接，谢谢!

Answer 1

如果您不想使用自平衡树(红黑树、AVL 等)，那么“简单”的解决方案是在将集合插入树之前对集合进行洗牌。

如果您想要一棵完美平衡的树，您可以从一个已排序的集合开始，然后将该列表的中间元素插入到树中，然后递归地对其余两个已排序的子集合执行相同的操作。

我知道您正在研究算法，但在现实生活中您可能只想使用 std::map 而不必担心它如何工作的细节。