313
правок
Изменения
Бор
,→Использование бора в качестве ассоциативного массива
===Использование бора в качестве ассоциативного массива===
Благодаря тому, что бор позволяет решать задачу, описанную выше, он может выступать в качестве ассоциативного массива. Обычно, когда требуется такая структура, то используют [[Дерево поиска, наивная реализация | двоичное дерево поиска]] или [[Хеш-таблица | хеш-таблицу]]. Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности:
#Добавление элемента в ассоциативный массив за O(n), где n — длина строки (а дерево может за O(n log m).
#Получение всех ключей в отсортированном порядке за O(m), где m — число ключей (а хеш-таблица может только за O(m log m)).
Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующие недостатки:
# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки).
# Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти, а так же будет большая константа.
==См. также==
