Have Geek Brain

Efficient data structure for a sorted list

I want to keep my objects according to the key in the attributes of my object in a sorted way. Later I will refer to these objects sequentially from max key to min key. I will also do some search tasks.

I am considering using either an AVL tree or an RB tree. As far as I know, they are almost equivalent in theory (both are O (logn)). But in practice it might be better in my situation. And is there any better alternative than those given that I am mainly doing insertion and sequential access to ds.

Edit: I am going to use java

+2


a source to share


3 answers


For what it's worth, in C # is SortedDictionary<K, V>

implemented as a red-black tree, and in many STL implementations in C ++ it std::map<K, T>

is implemented as a red-black tree.

Also, from Wikipedia on AVL and red-black trees:



The AVL tree is another structure supporting O (log n) search, insert, and delete. They are more tightly balanced than red-black trees, leading to slower insertions and deletions, but faster searches. This makes it attractive for data structures that can be built once and loaded without reconstruction, such as language dictionaries (or software dictionaries, such as assembler or interpreter order codes).

+4


a source


which is ever easier for you to implement, you won't get a better insert than log (n) with a sorted list, and we'll probably need a lot more detail than what you provided to decide if there are other factors that make another structure more suitable.



+1


a source


As you do in Java, consider using a TreeSet (although it's a set, so you can't duplicate entries) ...

+1


a source






More articles:


All Articles