CODEWITHSUNDEEP
javaperformanceavl-treedata-storage
H. Wilde
H. Wilde

Reputation: 197

An alternative to two AVL trees

I currently have data that I need sorted in two different ways, from a time and space complexity PoV, is there any alternative to maintaining two trees, one sorted by date and one by ID number? I need to be able to return lists in order of data, and individual users by ID, and I would prefer not to have to traverse or even worse, traverse and then sort for the array returns.

Any insight or help is much appreciated, thanks!

Upvotes: 3

Views: 414

Answers (2)

bashnesnos
bashnesnos

Reputation: 816

You could do that in one tree, but you would get O(logN) performance only for the date. The ID direct retrieval would be O(N) (i.e. traversing the whole tree to find an exact match) anyway, since the order would be indetermined.

If your ID could be based on the date you need (I mean if the ID could be generated basing on the date) - then you could reduce the O(N) time-complexity to O(logN + M), where M - is a subset of ID's for a particular date.

So depending on your response time and memory requirements, you could keep just one tree, or pair it with a HashMap of ID's.

Upvotes: 2

Kiryl
Kiryl

Reputation: 111

TreeMap implements Red-Black tree which is an alternative to AVL.

Upvotes: 1

Related Questions