Как пронумеровать все двоичные деревья? Как на КДПВ: “дерево” из одного листа будет первым, дерево из двух листов вторым, второе дерево с ещё одной веткой, исходящей из корня – третьим. А как найти номер произвольного дерева в такой схеме?
Рубрика «двоичные деревья»
Нумерация двоичных деревьев
2018-04-12 в 8:08, admin, рубрики: двоичные деревья, Занимательные задачки, математика, никто не читает теги
Решаем задачи без самобалансирующихся деревьев в Python
2018-03-13 в 7:19, admin, рубрики: heapq, python, а для индексации поиском, Алгоритмы, двоичные деревья, куча, ненормальное программирование, никто не читает теги, но они не для чтения, Программирование, так что это нормальноМногие задачи на алгоритмы требуют знания определённых структур данных. Стек, очередь, куча, динамический массив, двоичное дерево поиска — нечасто решение алгоритмической задачи обходится без использования чего-либо из них. Однако, качественная их реализация — нетривиальная задача, и при написании кода всегда хочется по максимуму обойтись использованием стандартной библиотеки языка.
Что касается Python, то в нём есть почти всё.
- Динамический массив — встроенный тип
list. Он же поддерживает и стековые операции:.append()и.pop(). - Хэш-таблица — встроенные типы
setиdict, а также неизменяемый брат сетаfrozenset. - Куча —
listсо специальными операциями вставки и удаления, реализованными в модулеheapq. - Двусторонняя очередь — это описанный в модуле
collectionsтипdeque.
Но вот самобалансирующегося дерева поиска, как такового, в стандартной библиотеке нет. А жаль!
В этой статье я разберу несколько алгоритмических задачек, подразумевающих решение с помощью двоичного дерева, и покажу, чем в разных ситуациях его можно заменить в Питоне.
Читать полностью »