Вы когда‑нибудь задумывались, почему результаты поиска файлов появляются так быстро? В этой статье мы рассмотрим удивительную структуру данных, известную как двоичное дерево (бинарное дерево), и узнаем, как именно она позволяет достичь такой быстрой обработки и поиска.
list. Он же поддерживает и стековые операции: .append() и .pop().set и dict, а также неизменяемый брат сета frozenset.list со специальными операциями вставки и удаления, реализованными в модуле heapq.collections тип deque.
Как-то раз я делал задание для приёма на работу после собеседования, что-то вроде тестового задания только не на дом. Был интернет и я гуглил код на языке Си и нашел какой-то код который содержал ошибки, из-за этого я не смог сделать задание на которое выделили час. Почему так случилось скажу лишь то, что по программированию у меня было все плохо по минимуму и своего кода для деревьев у меня не было и для графов тоже.
И так приступим с основ:
Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным ориентированным деревом.[1]
На заметку сразу скажу, что совершенно не обязательно думать про кучу исключительно как структуру, у которой родитель больше, чем его потомки. Никто не запрещает взять противоположный вариант и считать, что родитель меньше потомков — главное, выберите что-то одно для всего дерева. Для нужд этой статьи гораздо удобнее будет использовать вариант со знаком «больше».
c. Игреки нужны только для балансировки, это внутренние детали структуры данных, ненужные пользователю. Иксов на самом деле нет в принципе, их хранить не нужно.
Двоичным деревьям поиска посвящено множество глав учебников и статей (например, раз, два, три), но они все концентрируются на общих идеях и поддержании баланса для сохранения эффективности. Методы неточного поиска, без которых двоичное дерево вообще не имеет преимущества перед реализациями без упорядочения ключей (как хэш-таблица), обычно не расписываются даже в учебниках. А в них есть интересные моменты...
Сравним стили реализации такого поиска: