If you can suffer the extra storage cost while building the tree, place all of the pointers into an array initially, shuffle the array randomly, then do the insertion:
{
std::vector<mesh_t> v(62500);
std::fill_n(v.begin(), v.size(), next_mesh());
std::random_shuffle(v.begin(), v.end());
for (auto mesh : v)
tree.add(mesh);
}
Given a basic binary search tree, your best bet is simply to ensure that the items are inserted in a reasonably random order. This produces the average case of a well (if not ideally) balanced tree.
Narue
Bad Cop
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
Put simply, if your data can arrive in sorted order, a basic binary search tree is the wrong data structure. You can certainly make it work, but there's a cost. Since high performance is clearly one of your goals, my recommendation is do it right from the beginning rather than try to "fix" a broken design, even if you have to write your own balanced tree (though your group member shouldn't have trouble doing it).
Narue
Bad Cop
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
If you can suffer the extra storage cost while building the tree, place all of the pointers into an array initially, shuffle the array randomly, then do the insertion:
{
std::vector<mesh_t> v(62500);
std::fill_n(v.begin(), v.size(), next_mesh());
std::random_shuffle(v.begin(), v.end());
for (auto mesh : v)
tree.add(mesh);
}
Given a basic binary search tree, your best bet is simply to ensure that the items are inserted in a reasonably random order. This produces the average case of a well (if not ideally) balanced tree.
I really don't know if thats a better solution than just inserting it into a tree, unless I missed something.
If OP really wants to do operations before insert, then sort the mesh by some comparison, then start adding the median into the tree one by one.
Another thought is how about using std::map? Its usually created via red-black trees, which has good balancing.
firstPerson
Senior Poster
3,923 posts since Dec 2008
Reputation Points: 841
Solved Threads: 608
I really don't know if thats a better solution than just inserting it into a tree, unless I missed something.
What happens when you insert a sorted sequence of items into a binary search tree?
Narue
Bad Cop
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
Maybe I missed something here, but if you have a sorted sequence of items, isn't it super easy to determine the BST order of insertion? You insert the middle item (median) first, then the median of each half and the median of each quarter and so on, so forth. But, of course, if you have a sorted sequence already, wouldn't you just keep that sequence and use a binary-search algorithm on it, instead of constructing a BST? Of course, if you don't have a random-access sequence, you might want to either transfer that sorted sequence into a random-access container, or build a BST (where each indexing operation during the insertions into the BST would be in linear-time, but you only do that BST construction once).
Also, you have mentioned that the application is for looking up meshes distributed over a heightmap, that suggest a geometric structure, in which case a simple BST is probably not the best option. Typically people use binary space-partitioning techniques for that. Easy methods for cartesian spaces include BSP trees, quadtrees, octrees, or Kd-trees, and for more general metric-spaces, you can use a dynamic vantage-point tree (DVP-tree) (I implemented a DVP-tree in a day or so, it's not hard).
mike_2000_17
Posting Virtuoso
2,139 posts since Jul 2010
Reputation Points: 1,634
Solved Threads: 457
What happens when you insert a sorted sequence of items into a binary search tree?
Thats the thing though, who says his items are being inserted in sorted order? Wouldn't insertion for him be just be 'as random'?
firstPerson
Senior Poster
3,923 posts since Dec 2008
Reputation Points: 841
Solved Threads: 608
Thats the thing though, who says his items are being inserted in sorted order?
He did, in the first post.
Narue
Bad Cop
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
He did, in the first post.
Oh i see, your right. Anyways, as suggested, inserting the median would produce the most optimal tree for that case. I don't see why OP cannot do that.
firstPerson
Senior Poster
3,923 posts since Dec 2008
Reputation Points: 841
Solved Threads: 608
So, I have ordered data... Will either:
a. map be faster
b. map and balanced tree will be pretty much as fast as each other
c. balanced tree will be faster
You'll have a difficult time beating the performance of std::map (or std::set if the value and key are the same object). Implementations typically use a red black tree as the underlying data structure of std::set and std::map (a balanced tree is practically required), and they're written byvery good programmers.
he was like *grumpy face* you should never use code you can't see's implimentation because It might not be what you need...
He sounds like a complete idiot.
Narue
Bad Cop
15,460 posts since Sep 2004
Reputation Points: 6,464
Solved Threads: 1,401
>>you should never use code you can't see's implimentation because It might not be what you need.
That's idiotic, as Narue said. The interface, the behaviour and the performance of each operation on std::map or std::set are very strictly specified, and their performance specifications (time-complexity of insertion (logN) and look-ups (logN)) implies that a balanced BST must be used in the implementation. When you have good specification of the interface, behaviour and performance, there is no need to be aware of its implementation details to be able to use it and have a clear idea of the resulting behaviour.
mike_2000_17
Posting Virtuoso
2,139 posts since Jul 2010
Reputation Points: 1,634
Solved Threads: 457
