Найти-добавить-удалить

1. «Найти-добавить-удалить»

НАЙТИ-ДОБАВИТЬ-
«
УДАЛИТЬ»
© 2010, 2014, 2015, Serge Kashkevich

2. Постановка задачи

ПОСТАНОВКА ЗАДАЧИ
Задано множество S мощностью M. Требуется
предложить структуру данных для хранения
элементов этого множества, пригодную для
выполнения следующих операций:
поиск элемента по значению
добавление нового (возможно, уникального)
элемента (после поиска)
удаление элемента (после поиска)
Ни одна из этих операций не должна выполняться с
трудоёмкостью O(N), где N – количество хранимых элементов!

3. Допустимые структуры данных

ДОПУСТИМЫЕ СТРУКТУРЫ ДАННЫХ
Основные:
массив
бинарное поисковое дерево
хэш-таблица
Дополнительные (сбалансированные деревья):
АВЛ – деревья
сильно ветвящиеся деревья
красно-чёрные деревья

4. Использование массивов

ИСПОЛЬЗОВАНИЕ МАССИВОВ
Если величина M невелика, можно завести
булевский массив из M элементов, и обозначать в
этом массиве наличие или отсутствие
соответствующего элемента.
Вариант такого подхода – битовый массив.
Если уникальности элементов не требуется,
массив должен быть числовым, и в нём
обозначается количество хранимых элементов.

5. Корневое дерево

КОРНЕВОЕ ДЕРЕВО
Корневое дерево определяется как конечное
множество T одного или более узлов со
следующими свойствами:
существует один корень дерева T ;
остальные узлы (за исключением корня)
распределены среди непересекающихся
множеств T1,...,Tm, и каждое из множеств
является корневым деревом; деревья T1,...,Tm
называются поддеревьями корня T

6. Обход дерева

ОБХОД ДЕРЕВА
Обход дерева – операция, связанная с
посещением его вершин (под посещением
понимается любая операция над вершиной
дерева, не затрагивающая структуру дерева)
При обходе каждая вершина должна быть
посещена ровно один раз

7. Прямой обход дерева

ПРЯМОЙ ОБХОД ДЕРЕВА
посетить корень
обойти все поддеревья в направлении слева направо
1
2
3
4
5
8
9
6
7
11
10
12
14
13
15
16

8. Обратный обход дерева

ОБРАТНЫЙ ОБХОД ДЕРЕВА
обойти все поддеревья в направлении слева направо
посетить корень
16
6
5
1
2
9
7
4
3
15
8
10
11
14
12
13

9. Бинарное дерево

БИНАРНОЕ ДЕРЕВО
Бинарное (двоичное) дерево —
ориентированное дерево, в котором число
сыновей каждой вершины не превосходят 2.
На бинарном дереве основаны следующие
структуры данных:
бинарное поисковое дерево
двоичная куча
красно-чёрное дерево
АВЛ-дерево
Фибоначчиева куча

10. Структура бинарного поискового дерева

СТРУКТУРА БИНАРНОГО ПОИСКОВОГО
ДЕРЕВА
Сыновья каждой вершины различаются: выделяются
левый и правый сын
Значения хранятся в каждой вершине дерева
Для любого узла значения в левом поддереве меньше, а
значения в правом поддереве – больше значения,
хранящегося в корне
46
28
73
37
31
50
78

11. Концевой обход бинарного дерева

КОНЦЕВОЙ ОБХОД БИНАРНОГО ДЕРЕВА
Обойти левое поддерево
Посетить корень
Обойти правое поддерево
4
1
6
3
5
7
2
Если под посещением понимать вывод хранящегося в
вершине значения, то концевым обходом БПД можно
вывести отсортированное содержимое дерева.

12. Поиск значения в БПД

ПОИСК ЗНАЧЕНИЯ В БПД
Пусть K – искомое значение, T – значение в
корне дерева
if (K==T) поиск завершен успешно
else if (K<T)
if (есть левый сын)
выполнить поиск в левом поддереве
else
поиск завершен неудачно
else
if (есть правый сын)
выполнить поиск в правом поддереве
else
поиск завершен неудачно

13. Добавление значения в БПД

ДОБАВЛЕНИЕ ЗНАЧЕНИЯ В БПД
если БПД пусто, создаем единственную вершину и
делаем ее корнем;
иначе выполняем поиск вершины с добавляемым
значением;
если поиск успешен, вставка невозможна;
в противном случае добавляем новую вершину и делаем
ее сыном (левым или правым) той вершины, на которой
мы остановились в процессе поиска

14. Удаление вершины из БПД

УДАЛЕНИЕ ВЕРШИНЫ ИЗ БПД
Выполняем поиск удаляемой вершины. Если он
завершился неудачно, завершаем работу.
Если удаляемая вершина – лист, попросту удаляем её и
ссылку на неё
20
15
13
20
25
18
15
13
25

15. Удаление вершины из БПД (продолжение)

УДАЛЕНИЕ ВЕРШИНЫ ИЗ БПД
(ПРОДОЛЖЕНИЕ)
Если удаляемая вершина A имеет одного сына, делаем
этого сына сыном отца вершины A (или корнем, если
удаляемая вершина – корень). При этом тип сына
(левый или правый) может измениться
20
15
13
25
18
17
20
15
13
25
17

16. Удаление вершины из БПД (окончание)

УДАЛЕНИЕ ВЕРШИНЫ ИЗ БПД (ОКОНЧАНИЕ)
Если удаляемая вершина A имеет двух сыновей,
находим самую правую вершину в левом поддереве,
корнем которого является A (или самую левую – в
правом поддереве) – вершину B. Информацию из
вершины B переносим в A, а саму вершину B удаляем,
как было сказано ранее.
20
15
13
25
18
17
18
15
13
25
17

17. Реализация БПД

РЕАЛИЗАЦИЯ БПД
Реализация бинарного поискового дерева на C#
приведена в примере BST.zip

18. Хэширование

ХЭШИРОВАНИЕ
Пусть количество хранимых элементов N много меньше M
(мощности множества S). Введём хэш-функцию
h : S → [1..N]
и создадим массив из N элементов (хэш-таблицу).
Суть хэширования состоит в следующем: помещаем
элемент s из множества S в хэш-таблицу по индексу
h(s).
Ситуация, когда необходимо поместить элементы s1 и s2, но
h(s1) = h(s2), называется коллизией.
Для разрешения коллизий применяют:
открытое хэширование
закрытое хэширование

19. Открытое хэширование

ОТКРЫТОЕ ХЭШИРОВАНИЕ
Элементы, находящиеся в коллизии друг с другом,
образуют список. Хэш-таблица хранит лишь
информацию о начале списка.
Пусть хэш-функция возвращает остаток от деления на 10:
0
210
1
441
2
42
3
4
534
5
5
6
136
7
8
78
9
29
4
56

20. Примеры хэш-функций

ПРИМЕРЫ ХЭШ-ФУНКЦИЙ
остаток от деления на N – объём хэш-таблицы
(N лучше сделать простым, нежелательно делать N = 10k при
хранении числовых данных)
остаток от деления старших разрядов на N
сумма цифр числа
сумма квадратов цифр числа
Все эти хэш-функции некачественны,
поскольку при определённых условиях
вероятность коллизий будет велика!

21. Примеры хэш-функций (продолжение)

ПРИМЕРЫ ХЭШ-ФУНКЦИЙ
(ПРОДОЛЖЕНИЕ)
Полиномиальная хэш-функция
Пусть дана строка S = s1s2 ...sT, состоящая из цифр от 0 до 9.
Тогда значение полиномиальной хеш-функции H(S, x, N)
вычисляется следующим образом:
T
H ( S , x, N ) ( si x i 1 ) mod N
i 1
Расчёт контрольной суммы (CRC)

22. Неудобные операции для хэш-таблиц

НЕУДОБНЫЕ ОПЕРАЦИИ ДЛЯ ХЭШТАБЛИЦ
найти минимальный (максимальный) элемент;
вывести все элементы, соблюдая
упорядоченность;
найти элемент, ближайший к искомому (или
отстоящий от искомого не более чем на K);
выполнить поиск по началу строки.

23. Недостаток бинарных поисковых деревьев

НЕДОСТАТОК БИНАРНЫХ ПОИСКОВЫХ ДЕРЕВЬЕВ
При создании дерева последовательностью вставок
длины различных ветвей могут сильно
различаться:
2
9
3
4
8
5
6
БПД, созданное для последовательности
(2, 9, 3, 4, 8, 5, 6, 7)
7

24. Недостаток хэш-таблиц

НЕДОСТАТОК ХЭШ-ТАБЛИЦ
0
При неудачном выборе хэш-функции все
вставленные элементы вступят в коллизию друг с
другом
Пусть хэш-функция возвращает остаток от деления на 10, а
добавляются элементы с одинаковой последней цифрой:
1
2
3
4
5
6
7
8
9
42
132
52
212
532
2
72
22
442
62

25. Подходы к решению проблемы

ПОДХОДЫ К РЕШЕНИЮ ПРОБЛЕМЫ
Создать древовидные структуры, у которых
длины ветвей будут не сильно отличаться друг
от друга (сбалансированные деревья)
При этом поддержание сбалансированности
должно выполняться с трудоёмкостью не
большей, чем O(log N).
ВАРИАНТЫ РЕШЕНИЯ:
АВЛ-деревья;
сильно ветвящиеся деревья;
красно-чёрные деревья

26. ДВОИЧНАЯ КУЧА

27. Операции над двоичной кучей

ОПЕРАЦИИ НАД ДВОИЧНОЙ КУЧЕЙ
Двоичная куча – структура данных, хранящая
элементы, над которыми определено отношение
«меньше». Она предназначена для выполнения
следующего набора операций:
добавить новый элемент;
определить и, возможно, удалить минимальный
элемент.

28. Двоичная куча как дерево

ДВОИЧНАЯ КУЧА КАК ДЕРЕВО
Двоичная куча – это двоичное дерево, полностью
сбалансированное на всех уровнях, кроме
последнего. Все вершины последнего уровня
максимально прижаты влево.
Кроме того, выполняется следующее условие:
для каждого поддерева значение, хранящееся в
корне, не превосходит значений, хранящихся в
его потомках

29. Пример двоичной кучи

ПРИМЕР ДВОИЧНОЙ КУЧИ
2
21
17
21
27
22
24
90
27
29
28
32
27
31
28
38
45
57
40

30. Добавление нового элемента в двоичную кучу

ДОБАВЛЕНИЕ НОВОГО ЭЛЕМЕНТА В
ДВОИЧНУЮ КУЧУ
2
21
17
21
27
22
24
90
27
29
28
32
27
31
28
38
45
57
14
Добавляем новый элемент в конец дерева, а затем, поднимаясь
вверх к корню, меняем при необходимости значения элементов.
40

31. Добавление нового элемента в двоичную кучу (продолжение)

ДОБАВЛЕНИЕ НОВОГО ЭЛЕМЕНТА В
ДВОИЧНУЮ КУЧУ (ПРОДОЛЖЕНИЕ)
2
21
17
21
27
22
24
90
27
29
28
14
27
32
31
28
38
45
57
40

32. Добавление нового элемента в двоичную кучу (продолжение)

ДОБАВЛЕНИЕ НОВОГО ЭЛЕМЕНТА В
ДВОИЧНУЮ КУЧУ (ПРОДОЛЖЕНИЕ)
2
21
17
21
27
22
24
90
27
14
28
29
27
32
31
28
38
45
57
40

33. Добавление нового элемента в двоичную кучу (окончание)

ДОБАВЛЕНИЕ НОВОГО ЭЛЕМЕНТА В
ДВОИЧНУЮ КУЧУ (ОКОНЧАНИЕ)
2
21
14
21
27
22
24
90
27
17
28
29
27
31
28
38
45
32
Свойства кучи восстановлены. Трудоёмкость операции
добавления – O(log N), где N – объём кучи.
57
40

34. Удаление минимального элемента из двоичной кучи

УДАЛЕНИЕ МИНИМАЛЬНОГО ЭЛЕМЕНТА
ИЗ ДВОИЧНОЙ КУЧИ
2
21
17
21
27
22
24
90
27
29
28
32
31
28
38
45
57
40
27
Минимальный элемент всегда находится в корне. Помещаем в
корень значение из последнего элемента кучи, а сам этот элемент
удаляем.

35. Удаление минимального элемента из двоичной кучи (продолжение)

УДАЛЕНИЕ МИНИМАЛЬНОГО ЭЛЕМЕНТА
ИЗ ДВОИЧНОЙ КУЧИ (ПРОДОЛЖЕНИЕ)
27
21
17
21
27
22
24
90
27
29
32
31
28
38
45
57
40
28
Минимальный элемент всегда находится в корне. Помещаем в
корень значение из последнего элемента кучи, а сам этот элемент
удаляем.

36. Удаление минимального элемента из двоичной кучи (продолжение)

УДАЛЕНИЕ МИНИМАЛЬНОГО ЭЛЕМЕНТА
ИЗ ДВОИЧНОЙ КУЧИ (ПРОДОЛЖЕНИЕ)
17
21
27
21
27
22
24
90
27
29
32
31
28
38
45
57
40
28
После этого, если свойства кучи нарушены, меняем значение в
корне поддерева и минимальное из сыновей. Продолжаем спуск.

37. Удаление минимального элемента из двоичной кучи (продолжение)

УДАЛЕНИЕ МИНИМАЛЬНОГО ЭЛЕМЕНТА
ИЗ ДВОИЧНОЙ КУЧИ (ПРОДОЛЖЕНИЕ)
17
21
21
27
27
22
24
90
27
29
28
32
31
28
38
45
57
40

38. Удаление минимального элемента из двоичной кучи (продолжение)

УДАЛЕНИЕ МИНИМАЛЬНОГО ЭЛЕМЕНТА
ИЗ ДВОИЧНОЙ КУЧИ (ПРОДОЛЖЕНИЕ)
17
21
21
22
27
27
24
90
27
29
28
32
31
28
38
45
57
40

39. Удаление минимального элемента из двоичной кучи (окончание)

УДАЛЕНИЕ МИНИМАЛЬНОГО ЭЛЕМЕНТА
ИЗ ДВОИЧНОЙ КУЧИ (ОКОНЧАНИЕ)
17
21
21
22
27
24
27
90
27
29
32
31
28
38
45
57
40
28
Свойства кучи восстановлены. Трудоёмкость операции удаления
минимального элемента – также O(log N), где N – объём кучи.

40. Реализация двоичной кучи в виде массива

РЕАЛИЗАЦИЯ ДВОИЧНОЙ КУЧИ В ВИДЕ
МАССИВА
Создаём одномерный массив из N элементов.
Значение корня помещается в массив по индексу
0, а значения сыновей вершины, хранящейся по
индексу k, помещаются по индексам 2k+1 и
2k+2. Это соответствует обходу дерева по
уровням.

41. Пример реализации двоичной кучи в виде массива

ПРИМЕР РЕАЛИЗАЦИИ ДВОИЧНОЙ КУЧИ
В ВИДЕ МАССИВА
2
21
17
21
27
22
24
90
2
27
29
31
32
38
45
28
57
27
28
17
21
21
29
27 38 22
45 57
40
24
90
28
27
27
32
31
28
40

42. Использование двоичной кучи

ИСПОЛЬЗОВАНИЕ ДВОИЧНОЙ КУЧИ
Сортировка с гарантированной трудоёмкостью
O(N log N);
Алгоритм Дийкстры поиска кратчайшего пути
во взвешенном графе