Hi there! I'm interested to know what other people would have a solution to one this: What I need is to store a rather large (5,000 - 10,000 entries) list of ID's--just numbers--that I can quickly search, add, and delete. I thought about using a radix sort, but I don't want to redo it every frame. Also, I don't know how I would quickly search through this to find an "empty" slot or an arbitrary value. I was also thinking of using a binary tree because it would allow very fast insertion and searching, but deletion is somewhat difficult and slow. Of course, a linked list search is out of the question! I have quite a few other ways that could work, but because this system will play a vital role in a project, I thought I'd get some input. Any help would be greatly appreciated. Thanks! Edited by - User_Name on August 11, 2001 12:55:11 AM

A tree of some sort is definately the way to go. First off, deletions in a BST are O(lg n) just like searches and inserts, when the tree is kept balanced. They''re really pretty easy, too. Just three cases, but I don''t feel like explaining them at the moment. A good data structures book makes it pretty clear.

By the way... 5,000 to 10,000 isn''t big. In fact, it''s kind of small. If you had a few billion elements, I''d suggest looking into B-trees, as they work well with memory paging systems. But for small sets like you''re talking about, balanced BST''s are the way to go. The three variants I''d recommend considering are (in order of increasing implementation difficulty), splay trees, Red-Black trees, and AVL trees.

Look into the strengths and weaknesses of each.

The STL map class is implemented with red-black trees. So if you''re using C++ go with that.