搜索存储在树中的数据
问题描述:
我有这样的数据是分层的,所以我把它存储在一棵树中。我想为它提供搜索功能。我必须为此创建一个二叉树吗?我不想有两千个节点。是不是有一种树让我既按照给定的顺序存储数据,也为我提供了像高效搜索设置这样的二叉树,而且几乎没有开销?搜索存储在树中的数据
任何其他的数据结构建议也将被赞赏。
谢谢。
编辑:
一些细节:树是一个非常简单的“手工制作”树,可认为是非常非常基本的。事情是,有成千上万的名字和其他文本将作为我想要搜索的数据输入,但我不想以传统方式遍历节点,并且需要像二进制搜索那样的快速搜索。
此外,重要的是,用户必须能够看到他已输入的结构,而不是已排序的结构。所以我不能保持排序以支持搜索。这就是为什么我说我不想有两千个节点。
答
如果您不想更改树形层次结构,请使用map来存储指向顶点的指针:std::map<SearchKeyType,Vertex*> M
。
每当您将顶点添加到树中时,您也需要将它添加到您的地图中。这很简单:M[key]=&vertex
。如果您确定密钥存在,要查找元素请使用M.find(key);
或M[key];
。
如果你的树有重复键,那么你应该使用multimap。
编辑:如果你的关键的规模太大了,比你可以用指针键代替键:
inline bool comparisonFunction(SearchKeyType * arg1,SearchKeyType * arg2);
std::map<SearchKeyType *, Vertex *, comparisonFunction> M;
inline bool comparisonFunction(SearchKeyType * arg1,SearchKeyType * arg2)
{
return (*arg1)<(*arg2);
}
搜索元素与价值V
你必须写如下:
为什么你认为你会需要节点两次?当你说“我把它存放在树上”时 - 什么样的树?什么阻止你直接搜索?基本上,需要更多细节。 – 2011-02-03 12:02:19
它不一定是二叉树。它必须是[*搜索*树](http://en.wikipedia.org/wiki/Search_tree)。二叉树本身不提供快速搜索。 – 2011-02-03 12:02:32