Рубрики

Обзор структур данных | Набор 2 (двоичное дерево, BST, куча и хэш)

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

5. Двоичное дерево
6. Двоичное дерево поиска
7. Двоичная куча
9. Хеширование

Бинарное дерево
В отличие от массивов, связанных списков, стека и очередей, которые являются линейными структурами данных, деревья являются иерархическими структурами данных.
Бинарное дерево — это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левым и правым дочерними элементами. Это реализовано в основном с использованием ссылок.

Представление двоичного дерева: дерево представлено указателем на самый верхний узел дерева. Если дерево пусто, тогда значение root равно NULL. Узел двоичного дерева содержит следующие части.
1. Данные
2. Указатель на левого ребенка
3. Указатель на правильного ребенка

Двоичное дерево можно пройти двумя способами:
Первый проход по глубине: Inorder (левый-корень-правый), Preorder (корень-левый-правый) и Postorder (левый-правый-корневой)
Ширина первого обхода: уровень порядка обхода

Свойства бинарного дерева:

The maximum number of nodes at level ‘l’ = 2l-1.

Maximum number of nodes = 2h + 1 – 1.
Here h is height of a tree. Height is considered 
as the maximum number of edges on a path from root to leaf.

Minimum possible height =  ceil(Log2(n+1)) - 1  

In Binary tree, number of leaf nodes is always one 
more than nodes with two children.

Time Complexity of Tree Traversal: O(n)

Примеры. Одна из причин использования бинарного дерева или дерева в целом — для вещей, которые образуют иерархию. Они полезны в файловых структурах, где каждый файл находится в определенном каталоге и существует определенная иерархия, связанная с файлами и каталогами. Другой пример, где деревья полезны, — это хранение иерархических объектов, таких как объектная модель JavaScript, которая рассматривает HTML-страницу как дерево с вложенными тегами как родительские дочерние отношения.

Двоичное дерево поиска
В Binary Search Tree есть Binary Tree со следующими дополнительными свойствами:
1. Левое поддерево узла содержит только узлы, ключи которых меньше ключа узла.
2. Правое поддерево узла содержит только узлы с ключами, которые больше ключа узла.
3. Левое и правое поддерево каждого также должны быть двоичным деревом поиска.

Сложности времени:

Search :  O(h)
Insertion : O(h)
Deletion : O(h)
Extra Space : O(n) for pointers

h: Height of BST
n: Number of nodes in BST

If Binary Search Tree is Height Balanced, 
then h = O(Log n) 

Self-Balancing BSTs such as AVL Tree, Red-Black
Tree and Splay Tree make sure that height of BST 
remains O(Log n)

BST обеспечивает умеренный доступ / поиск (быстрее, чем связанный список и медленнее, чем массивы).
BST обеспечивает умеренную вставку / удаление (быстрее, чем массивы и медленнее, чем связанные списки).

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

Двоичная куча
Двоичная куча — это двоичное дерево со следующими свойствами.
1) Это полное дерево (все уровни полностью заполнены, за исключением, возможно, последнего уровня, и на последнем уровне все ключи как можно левее). Это свойство Binary Heap делает их пригодными для хранения в массиве.
2) Двоичная куча — это либо минимальная куча, либо максимальная куча. В минимальной двоичной куче ключ в корневом каталоге должен быть минимальным среди всех ключей, присутствующих в двоичной куче. Одно и то же свойство должно быть рекурсивно истинным для всех узлов в двоичном дереве. ФИЛЬМЫ ПОХОЖИЕ НА Min Heap В основном это реализовано с использованием массива.

Get Minimum in Min Heap: O(1) [Or Get Max in Max Heap]
Extract Minimum Min Heap: O(Log n) [Or Extract Max in Max Heap]
Decrease Key in Min Heap: O(Log n)  [Or Extract Max in Max Heap]
Insert: O(Log n) 
Delete: O(Log n)

Пример: используется для реализации эффективных очередей приоритетов, которые, в свою очередь, используются для планирования процессов в операционных системах. Очереди приоритетов также используются в алгоритмах графа Диджстры и Прима.
Структура данных Heap может использоваться для эффективного поиска k наименьших (или наибольших) элементов в массиве, объединения k отсортированных массивов, медианы потока и т. Д.
Куча — это особая структура данных, и ее нельзя использовать для поиска определенного элемента.

Функция хеширования : функция, которая преобразует заданную большую клавишу ввода в небольшое практическое целое значение. Отображенное целочисленное значение используется в качестве индекса в хэш-таблице. Хорошая хеш-функция должна иметь следующие свойства
1) Эффективно вычислимо.
2) Должны равномерно распределять ключи (каждая позиция таблицы одинаково вероятна для каждого ключа)

Хеш-таблица: массив, в котором хранятся указатели на записи, соответствующие данному номеру телефона. Запись в хэш-таблице равна NIL, если ни один из существующих телефонных номеров не имеет значения хэш-функции, равного индексу для записи.

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

Цепочка: идея состоит в том, чтобы каждая ячейка хеш-таблицы указывала на связанный список записей, имеющих одинаковое значение хеш-функции. Цепочка проста, но требует дополнительной памяти вне таблицы.
Открытая адресация. При открытой адресации все элементы хранятся в самой хеш-таблице. Каждая запись в таблице содержит либо запись, либо NIL. При поиске элемента мы один за другим проверяем слоты таблицы, пока не будет найден нужный элемент или пока не станет ясно, что элемента нет в таблице.

Space : O(n)
Search    : O(1) [Average]    O(n) [Worst case]
Insertion : O(1) [Average]    O(n) [Worst Case]
Deletion  : O(1) [Average]    O(n) [Worst Case]

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

Пример: хеширование можно использовать для удаления дубликатов из набора элементов. Также можно использовать поиск частоты всех предметов. Например, в веб-браузерах мы можем проверять посещенные URL-адреса с помощью хеширования. В брандмауэрах мы можем использовать хеширование для обнаружения спама. Нам нужно хешировать IP-адреса. Хеширование может быть использовано в любой ситуации, где требуется search () insert () и delete () за O (1) раз.

Эта статья предоставлена Абхираджем Смитом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Обзор структур данных | Набор 2 (двоичное дерево, BST, куча и хэш)

0.00 (0%) 0 votes