我有很多东西要收藏我需要找到一个项目,通过比较它与某个密钥,然后判断是否存在这样一个项目。我用二叉搜索树来做。

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++ ALLON更适用于更多的语言。
如果你提供的链接可以帮助我,谢谢!

最佳答案

如果您不想使用自平衡树(红黑、avl等),那么“简单”的解决方案是在将集合插入树之前对其进行无序处理。
如果需要一个完全平衡的树,可以从排序的集合开始,然后将该列表的中间元素插入树中,并递归地对其余两个排序的子集合执行相同的操作。
我知道你正在研究算法,但在现实生活中,你可能只想使用std::map而不必担心它如何工作的细节。

07-24 09:46
查看更多