我有很多东西要收藏我需要找到一个项目,通过比较它与某个密钥,然后判断是否存在这样一个项目。我用二叉搜索树来做。
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
而不必担心它如何工作的细节。