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