搜索存储在树中的数据

我有这样的数据是分层的，所以我把它存储在一棵树中。我想为它提供搜索功能。我必须为此创建一个二叉树吗？我不想有两千个节点。是不是有一种树让我既按照给定的顺序存储数据，也为我提供了像高效搜索设置这样的二叉树，而且几乎没有开销？搜索存储在树中的数据

任何其他的数据结构建议也将被赞赏。

谢谢。

编辑：

一些细节：树是一个非常简单的“手工制作”树，可认为是非常非常基本的。事情是，有成千上万的名字和其他文本将作为我想要搜索的数据输入，但我不想以传统方式遍历节点，并且需要像二进制搜索那样的快速搜索。

此外，重要的是，用户必须能够看到他已输入的结构，而不是已排序的结构。所以我不能保持排序以支持搜索。这就是为什么我说我不想有两千个节点。

来源

2011-02-03 Dirt

为什么你认为你会需要节点两次？当你说“我把它存放在树上”时 - 什么样的树？什么阻止你直接搜索？基本上，需要更多细节。 – 2011-02-03 12:02:19

它不一定是二叉树。它必须是[*搜索*树]（http://en.wikipedia.org/wiki/Search_tree）。二叉树本身不提供快速搜索。 – 2011-02-03 12:02:32

如果您不想更改树形层次结构，请使用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:29:43 UmmaGumma

搜索存储在树中的数据

回答

相关问题