In what languages, associative arrays are implemented using redblack tree instead of hashtable?

Question

In wikipedia: http://en.wikipedia.org/wiki/Red-black_tree#Applications_and_related_data_structures

red-black tree is a type of self-balancing binary search tree, a data structure used in computing science, typically used to implement associative arrays.

Anyone know a language implemented associative array using redblack tree?

Answer 1

C++ std::map is often implemented as red-black tree. It's the basic associative array. The other one (new) is std::unordered_map and is in fact a hash-map.

Answer 2

java.util.TreeMap is an implementation of a red-black tree in Java.

Answer 3

I don't know if it's a red-black tree, but Haskell's Data.Map is a balanced binary tree:

The implementation of Map is based on size balanced binary trees (or trees of bounded balance) as described by:

• Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
• J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.

Ocaml has both a mapping type ontop of hashtables and a binary trees.

Answer 4

In C# SortedDictionary is implemented as Red-Black tree, while Dictionary uses hashtable and SortedList is basically list with binary search for keys lookup.

Answer 5

Scala's scala.collection.immutable.TreeMap is implemented with a Red-Black tree.