搜索存儲在樹中的數據

我有這樣的數據是分層的，所以我把它存儲在一棵樹中。我想爲它提供搜索功能。我必須爲此創建一個二叉樹嗎？我不想有兩千個節點。是不是有一種樹讓我既按照給定的順序存儲數據，也爲我提供了像高效搜索設置這樣的二叉樹，而且幾乎沒有開銷？搜索存儲在樹中的數據

任何其他的數據結構建議也將被讚賞。

謝謝。

編輯：

一些細節：樹是一個非常簡單的「手工製作」樹，可認爲是非常非常基本的。事情是，有成千上萬的名字和其他文本將作爲我想要搜索的數據輸入，但我不想以傳統方式遍歷節點，並且需要像二進制搜索那樣的快速搜索。

此外，重要的是，用戶必須能夠看到他已輸入的結構，而不是已排序的結構。所以我不能保持排序以支持搜索。這就是爲什麼我說我不想有兩千個節點。

來源

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

搜索存儲在樹中的數據

回答

相關問題