Двоичное дерево — зачем оно нужно и как оно получается?

Question

[Влад]

Всем привет!
Объясните, пожалуйста, вот вообще любая структура данных - это ведь не тип данных. Как образуются структуры данных?
Они как-то "зашиты" под капотом в интерпретаторах языков программирования? Я просто окончательно запутался.

Например, цитата из википедии:

Двоичное дерево поиска применяется для построения более абстрактных структур, таких, как множества, мультимножества, ассоциативные массивы.

Но, разве ассоциативный массив- это в случае, к примеру, с языком Python не словарь? А словарь- это разве не структура данных хэш таблица? Я уже кучу статей перечитал, но везде только объясняется какие бывают деревья, но откуда они так сказать "появляются" нигде не сказано.

Прошу прощения, знаю вопрос тупой. Я честно читал к примеру "Грокаем алгоритмы", но там тоже ничего не нашёл про то откуда берутся структуры данных.

Заранее большое спасибо за помощь!

Answer 1

[Wataru]

Для начала поймите, как реализованы связные списки. Вот двоичное дерево - это почти тоже самое, только у каждого элемента 2 ссылки а не одна. Просто способ организации данных, который обладает какими-то полезными свойствами.

Все внутри реализовано на указателях, массивах и структурах (тупо группа различных переменных, объедененных в один тип).

Словарь в питоне, он же ассоциативный массив, действительно, реализован на основе хеш таблицы. Реализован внутри интерпретатора Питон. Это другая структура данных, сделанная на основе массивов и списков (которые реализованы на указателях).

Но ассоциативный массив можно реализовывать и двоичными деревьями поиска. Например структура set в языке C++ - реализована деревом. Такой ассоциативный массив работает ассимптотически медленнее (логарифм операций вместо константы для поиска/вставки/удаления). Но обладает важным свойством - элементы там упорядочены. Можно найти минимальный ключ, обойти все ключи в порядке возрастания, подсчитать что-то на отрезке ключей. Плюс не нужно придумывать хороший хеш. В хеш-таблицах, если хеш плохой - можно получить O(n) операции. Или может не повести и будет куча коллизий даже для хорошего хеша. В двоичных деревьях поиска (большинстве) гарантирован худший случай за логарифм. В некоторых задачах лучше использовать именно эту структуру, чем хеш-таблицу.

Плюс есть всякие другие структуры данных на основе деревьев: дерево отрезков, двоичная куча, бор.