Implementing a Mahogany Tree or AVL in Java

Question

Is there any implementation of the Red Black Tree / AVL Tree data structure in the Java / collections in the Guava / Apache Commons library? If so, can you point them to me. Basically I am looking for a data structure in which requests should be executed in O (log n) time. There will also be some data structure updates, but not as often as queries.

Answer 1

I am mainly looking for a data structure in which requests should occur in O (lg n) time

Use TreeMap . It is supported by a red-black tree , so the access time is O(logN) (my emphasis is on the quote below)

public class TreeMap
extends AbstractMap tools
NavigableMap, Cloneable, Serializable

Implementation of NavigableMap based on Red-Black. The map is sorted in accordance with the natural order of its keys or the comparator, subject to the creation of a map, depending on which constructor is used.

This implementation provides a guaranteed log (n) time value for containsKey, get, put and remove.