В каких языках ассоциативные массивы реализованы с использованием красного чёрного дерева вместо хеш-таблицы?

Question

В википедии: http://en.wikipedia.org/wiki/Red-black_tree#Applications_and_related_data_structures

красно-черное дерево - это тип самобалансирующегося двоичного дерева поиска, структура данных, используемая в вычислительной технике, обычно используемая для реализации ассоциативных массивов.

Кто-нибудь знает реализованный на языке ассоциативный массив, использующий красное дерево?

Answer 1

java.util.TreeMap - это реализация красно-черного дерева в Java.

Answer 2

C ++ std :: map часто реализуется как красно-черное дерево.Это основной ассоциативный массив.Другой (новый) является std :: unordered_map и фактически является хеш-картой.

Answer 3

Scala's scala.collection.immutable.TreeMap реализован с красно-черным деревом.

Answer 4

In C # SortedDictionary реализован в виде красно-черного дерева, в то время как Словарь использует хеш-таблицу и SortedList - это в основном список с двоичным поиском для поиска ключей.

Answer 5

Я не знаю, является ли это красно-черным деревом, но Данные Haskell. Карта является сбалансированным двоичным деревом:

РеализацияКарты основаны на сбалансированных по размеру двоичных деревьях (или деревьях с ограниченным балансом), как описано:

• Стивен Адамс, «Эффективные множества: действие балансировки», Журнал функционального программирования 3 (4):553-562, октябрь 1993 г., http://www.swiss.ai.mit.edu/~adams/BB/.
• J.Нивергельт и Э.М. Рейнгольд, «Деревья бинарного поиска с ограниченным балансом», Журнал вычислений SIAM 2 (1), март 1973 г. и бинарных деревьев .