Заключение по реализациям АТД Map

На протяжении двух последних глав мы рассмотрели несколько структур данных, подходящих для реализации АТД Map: бинарный поиск на списках, хэш-таблицы, двоичное дерево поиска и сбалансированное двоичное дерево поиска. В заключение этого раздела, давайте подытожим производительности для каждой из перечисленных структур данных (см. таблицу 1).

Table 1: Comparing the Performance of Different Map Implementations
Операция Сортированный список Хэш-таблица Бинарное дерево поиска АВЛ-дерево
put \(O(n)\) \(O(1)\) \(O(n)\) \(O(\log_2{n})\)
get \(O(\log_2{n})\) \(O(1)\) \(O(n)\) \(O(\log_2{n})\)
in \(O(\log_2{n})\) \(O(1)\) \(O(n)\) \(O(\log_2{n})\)
del \(O(n))\) \(O(1)\) \(O(n)\) \(O(\log_2{n})\)
Next Section - Заключение