Преимущества BST перед хеш-таблицей


Сложный уровень Легко
Часто спрашивают в Амазонка GE Healthcare Компания Qualcomm
Бинарный поиск Двоичное дерево Hash теория дерево

Наиболее часто используемые операции с любой структурой данных - это вставка, удаление и поиск. Хеш-таблица может выполнять эти три операции со средней временной сложностью O (1), при этом самобалансирующийся двоичный поиск Деревья взять O (log n) временную сложность.

Сначала кажется, что хеш-таблицы лучше, чем самобалансирующиеся BST во всех форматах, поскольку временная сложность операций в хэш-таблице меньше, чем в BST. Но есть некоторые условия или требования, при которых мы предпочитаем BST хеш-таблицам.

Преимущества BST перед хеш-таблицей

Преимущества BST перед хеш-таблицей

  1. Самобалансирующиеся бинарные деревья поиска хранят данные в отсортированном виде, то есть мы можем получить отсортированные данные, просто выполнив упорядоченный пересечение в BST. Но в хэш-таблицах мы должны пройти по всем элементам и отсортировать их с помощью некоторой техники сортировки.
    Сложность времени (хеш-таблица) = O (п журнал (п))
    Сложность времени (BST) = О (п)
  2. Найдите максимальный узел, минимальный узел, узел, ближайший к заданному значению, или узел, который немного больше заданного значения, и т. Д. Все операции могут быть выполнены за время O (log n) в самобалансирующемся двоичном дереве поиска. Но в случае с хеш-таблицами мы должны пройти по всем элементам, чтобы получить ответ на упомянутые запросы.
    Сложность времени (хеш-таблица) = О (п)
    Сложность времени (BST) = O (журнал n)
  3. Реализация настраиваемого двоичного дерева поиска намного проще, чем реализация настраиваемой хэш-таблицы. Различные языки предоставляют встроенные библиотеки для реализации настраиваемых хэш-таблиц.
  4. Верхний предел для всех операций, таких как вставка, удаление, обновление и поиск в самобалансирующемся двоичном дереве поиска, составляет O (log n). Но в случае хеш-таблиц нет верхней границы. Операции выполняются со средней сложностью O (1), но в некоторых случаях сложность может увеличиваться. Увеличение может произойти из-за того, как библиотека реализует хеш-таблицу. В частности, когда выполняется изменение размера хеш-таблицы, это очень дорогостоящая операция.

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

Ссылка1    ссылка2