Advertisement Jump to content
Sign in to follow this  
Pooya65

RB-Tree or AVL trees

This topic is 1792 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement

Go with hash tables if you don't need ordering.

 

edit:

The best way to find out is probably to just use each of them in your game, and see which one is better.

Theoretically, RB trees can have height that goes up to 2 * log(n), but it's still O(log(n)).

You can also look at AA trees, which are RB trees with the red nodes only on the right side (or left if you are left handed), so they have log(n) height on the left side and at most 2*log(n) height on the right side.

And also you can look into b-trees, a generalization of RB and AA trees.

Edited by ultramailman

Share this post


Link to post
Share on other sites

Impossible to answer as the question stands. It depends on what you want. There is no single best data structure.

 

If you do considerably more modifications, then red-black tree will be faster. If you do more lookups, an AVL tree will be faster. But it's not like one is 100 times faster than the other.

Both have identical big-O on all operations and are more or less on the same order of speed.

 

A hash table, as suggested by ultramailman may very well be the best choice, too -- depending on what you are doing.

Share this post


Link to post
Share on other sites

i think look-uping an item in a game is more often used than inserting or deleteing an item so with AVL trees we can get better results. 

Share this post


Link to post
Share on other sites

which is better ( faster ) for game programming?


Trick question. Don't use trees.

A closed hash table (or one using a perfect hash function, for static data sets) is one option. A flat map (sorted vector of key-value pairs) is another option.

Share this post


Link to post
Share on other sites

A while ago, I was learning B-trees and implemented my own. Then I made a very simple performance test that involves inserting many random integers into a data structure, do many look ups, and then removing all items, and timed it to see which one was faster. The input is the same for every data structure, so I could test them more fairly. The results were something like this (I don't have the files any more so I can't check):

 

RB tree: 19-20 seconds

B-tree with 16 slots per node: 5-6 seconds

hash table with separate chaining and size == number of inputs: 2 seconds

 

These only apply to my own implementations however, but I still trusted enough to not bother with trees when I don't need them. If I had to guess why the results turned out like that, it was probably because RB had more cache misses than B-tree, and trees had require more exploring to find the target.

Share this post


Link to post
Share on other sites
What Sean said -- it depends entirely on the situation.
Often a flat, unsorted, unpartitioned, plain old array can be the fastest choice in practice, even if in theory it should be a terrible choice.
Likewise, theoretically great structures can perform relatively terribly in practice, depending on the situation.

Share this post


Link to post
Share on other sites

are you know any good article from implementing hash tables?

 

as i considred, hash function is most important thing in hash table, how can i implement a good hash function for unicode strings ( a good algortim or ... )

Share this post


Link to post
Share on other sites

"Implementing hash tables" is, again, something you can write entire books about, and not something that you "get right" easily (it's easy to get something that works, though). You either need to define very exactly what you need first, or you should simply use whatever implementation the standard library offers to you. For the general case, that's probably as good as you can get.

 

Generally, a good hash function is better than a bad hash function, but in practice a good hash table (such as e.g. the one used in GCC's unordered_map) proves widely immune to bad input, surprising as it is. It is very hard to feed GCC's std::unordered_map with something that causes 2x slower lookup times (quite different story on at least one other popular compiler!).

 

Creating a bad hash function is easy, creating a good hash function is hard. Creating a hash function that looks good is easy. Usually std::hash works just fine, if that isn't applicable, simple good old DJB2 works wonders. There are much "better" functions, but in my experience they are only better in theory (or by their statistical properties), not in practice, when it comes to looking up values in a hash table fast.

 

Hash functions have several things to consider and what's best depends a lot on what you need:

  •  Cost of hash function and compare: Hash lookups are O(1) but the hash function is O(N) in respect to the key length, and due to the possibility of collisions, a hash always needs an extra O(N) compare. For that reason, hash functions may be super good or super bad compared to trees, depending on what kind of keys you feed it (this is one reason why e.g. radix trees are so awesome at matching text -- they only compare as many characters as are different from one end, and only once).
  •  Load ("becoming full"), and collisions. Collisions may not just happen, they will happen. And they need to be dealt with. Among the solutions are chaining several objects with identical hashes, linear probing ("simply use next slot"), hashing twice, and more exotic approaches such as cuckoo hashing. They all have very different advantages and disadvantages (for example, cuckoo hashing is slower overall, but it lets you use very high loads and has a guaranteed O(1) worst case access time with exactly defined number of operations -- whereas the others are O(1) average and generally faster, but O(N) worst case).
  •  Cache effects, rehashing effects. Memory fragmentation and other not immediately obvious things.
  •  Only insert/lookup, or delete and other operations? Some approaches make these easy, others make these hard. Need to decide what you urgently need. This may make 1-2 orders of magnitude difference in runtime.

If any or all of these causes a "Uh... I dunno..." inside your head, you're probably best with using the implementation offered by the standard library. It is maybe not perfect for every case, but it works and it works well for most cases.

Edited by samoth

Share this post


Link to post
Share on other sites
Very recently I spoke to a developer of Warhammer Online who now works at Google. According to him, RB trees are quite slow as well as cache inefficient (sometimes even page faults).

The best way IMO would be to have a fixed size tree that is linear in memory, similar to how L. Spiro did her instant insertion quadtree.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!