Рубрика «никто не читает теги» - 18

Многие задачи на алгоритмы требуют знания определённых структур данных. Стек, очередь, куча, динамический массив, двоичное дерево поиска — нечасто решение алгоритмической задачи обходится без использования чего-либо из них. Однако, качественная их реализация — нетривиальная задача, и при написании кода всегда хочется по максимуму обойтись использованием стандартной библиотеки языка.

Что касается Python, то в нём есть почти всё.

• Динамический массив — встроенный тип list. Он же поддерживает и стековые операции: .append() и .pop().
• Хэш-таблица — встроенные типы set и dict, а также неизменяемый брат сета frozenset.
• Куча — list со специальными операциями вставки и удаления, реализованными в модуле heapq.
• Двусторонняя очередь — это описанный в модуле collections тип deque.

Но вот самобалансирующегося дерева поиска, как такового, в стандартной библиотеке нет. А жаль!

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