Многие задачи на алгоритмы требуют знания определённых структур данных. Стек, очередь, куча, динамический массив, двоичное дерево поиска — нечасто решение алгоритмической задачи обходится без использования чего-либо из них. Однако, качественная их реализация — нетривиальная задача, и при написании кода всегда хочется по максимуму обойтись использованием стандартной библиотеки языка.
Что касается Python, то в нём есть почти всё.
- Динамический массив — встроенный тип
list
. Он же поддерживает и стековые операции:.append()
и.pop()
. - Хэш-таблица — встроенные типы
set
иdict
, а также неизменяемый брат сетаfrozenset
. - Куча —
list
со специальными операциями вставки и удаления, реализованными в модулеheapq
. - Двусторонняя очередь — это описанный в модуле
collections
типdeque
.
Но вот самобалансирующегося дерева поиска, как такового, в стандартной библиотеке нет. А жаль!
В этой статье я разберу несколько алгоритмических задачек, подразумевающих решение с помощью двоичного дерева, и покажу, чем в разных ситуациях его можно заменить в Питоне.
Читать полностью »