Лекция 3+4. Деревья поиска

Август 23, 2022

Главная
Информатика
Лекция 3+4. Деревья поиска

Содержание

2. Дерево поиска Дерево, дерево с корнем. Высота дерева. Родительские и дочерние узлы, листья. Количество рёбер
3. Количество деревьев с пронумерованными вершинами Теорема Кэли Число деревьев на n вершинах, пронумерованных от 1 до
4. Код Прюфера Кодирование производится через последовательное удаление вершин дерева, имеющих наименьший номер и являющихся концевыми. При
5. Код Прюфера Любое дерево естественно переводится в Код Прюфера. Код имеет размер (n-2), всего кодов на
6. Обход в глубину Для бинарных деревьев -- pre-, post- и in-order
7. Обход в ширину
8. Деревья поиска Поиск ключа, вставка, удаление Необходимость балансировки
9. АВЛ-дерево Хотим поддерживать разницу между поддеревьями любой вершины |h(L)-h(R)| Для этого в процессе проведения операций будем
10. АВЛ-дерево
11. АВЛ-дерево Добавление элемента: сначала идём вниз от корня как при поиске, пока не дойдём до отсутствующей
12. АВЛ-дерево Удаление вершины. Если вершина -- лист, то просто удаляем. Если внутренняя, то найдём ближайшую по
13. Слияние двух АВЛ-деревьев Пусть есть деревья X и Y, все ключи X Пусть высота X меньше,
14. Высота АВЛ-дерева
15. Сплей-дерево Дерево, позволяющее получать быстрый доступ к элементам, которые были использованы последними
16. Эвристики moveToRoot(x) -- совершает повороты (x,p), где х -- вершина, p -- её предок, пока x
17. Операции над сплей-деревом merge -- запускаем splay от самого большого элемента X, подвешиваем справа Y (
19. Декартово дерево поиска -- хранит элементы (x,y), где x -- ключ, а y -- приоритет. Декартово
20. Операции над декартовым деревом split(x): пусть x больше корня, тогда в левом дереве окажется левое поддерево
21. Операции над декартовым деревом insert(x) -- разделим дерево по x, а потом сольём сначала T1 и
22. Построение По очереди вставим все элементы Пусть элементы отсортированы по возрастанию ключей. Смотрим на самый правый
23. Высота декартова дерева Теорема. В декартовом дереве на n узлов, у которого приоритеты -- равномерно распределённые
24. Красно-чёрное дерево Дерево поиска, вершины которого промаркированы определённым цветом: красным или чёрным Каждая вершина — либо
25. Высота красно-чёрного дерева Чёрная высота x -- количество чёрных вершин на пути из х в лист
26. Высота красно-чёрного дерева Лемма. Высота красно-чёрного дерева с N вершинами равна O(logn) Количество красных вершин не
27. Вставка элемента Идём от корня до листа по условиям деревья поиска. Вставляем вершину с красным цветом.
28. Удаление элемента Три варианта: Мы в листе -- изменяем указатель родителя на nul Есть один ребёнок
29. B-дерево
30. Операции над B-деревом
31. KD-дерево
33. Скачать презентацию

Слайд 2

Дерево поиска
Дерево, дерево с корнем. Высота дерева. Родительские и дочерние узлы,

листья. Количество рёбер

Слайд 3

Количество деревьев с пронумерованными вершинами
Теорема Кэли
Число деревьев на n вершинах, пронумерованных

от 1 до n, равно n^(n-2)
Для доказательства воспользуемся кодированием Прюфера для деревьев с пронумерованными вершинами

Слайд 4

Код Прюфера
Кодирование производится через последовательное удаление вершин дерева, имеющих наименьший номер

и являющихся концевыми. При этом в код записывается номер вершины, с которой удаляемая соединена. Когда остаётся две вершины, формирование кода заканчивается
Чтобы восстановить дерево по коду Прюфера, необходимо выписать код и множество номеров 0..n. Для каждого шага выбираем очередное число из кода и минимальное число из i..n, которое не встречается в коде. Построим ребро и вычеркнем их, а затем повторим процесс, пока не останется два незадействованных числа. Проведём между ними ребро

Слайд 5

Код Прюфера
Любое дерево естественно переводится в Код Прюфера. Код имеет размер

(n-2), всего кодов на n вершинах можно построить n^(n-2). Отсюда и получается оценка на количество пронумерованных деревьев

Слайд 6

Обход в глубину
Для бинарных деревьев -- pre-, post- и in-order

Слайд 7

Обход в ширину

Слайд 8

Деревья поиска
Поиск ключа, вставка, удаление
Необходимость балансировки

Слайд 9

АВЛ-дерево
Хотим поддерживать разницу между поддеревьями любой вершины |h(L)-h(R)| <= 1
Для этого

в процессе проведения операций будем использовать вращения двух типов:

Слайд 10

АВЛ-дерево

Слайд 11

АВЛ-дерево
Добавление элемента: сначала идём вниз от корня как при поиске, пока

не дойдём до отсутствующей вершины. Вставляем элемент и поднимаемся вверх.
Если поднялись из левого поддерева -- diff увеличивается на 1, если из правого -- уменьшается. Встретив ситуацию |h(L)-h(R)| > 1, совершаем необходимые повороты. Если после вращения diff стал равен 0, останавливаемся, иначе -- продолжаем подъём

Слайд 12

АВЛ-дерево
Удаление вершины.
Если вершина -- лист, то просто удаляем. Если внутренняя, то

найдём ближайшую по значению вершину, поменяем их местами и удалим. Далее поднимаемся из удалённой вершины и восстанавливаем баланс

Слайд 13

Слияние двух АВЛ-деревьев
Пусть есть деревья X и Y, все ключи X

<= любому ключу Y.
Пусть высота X меньше, чем у Y. Тогда удаляем у X самую правую вершину (b), а у Y спускаемся вниз влево, пока не дойдём до вершины, имеющей высоту как у X (c) . Делаем подвешиваем b вместо c, c делаем его правым поддеревом, а X -- левым. Поднимаемся наверх и балансируем дерево поворотами

Слайд 14

Высота АВЛ-дерева

Слайд 15

Сплей-дерево
Дерево, позволяющее получать быстрый доступ к элементам, которые были использованы последними

Слайд 16

Эвристики
moveToRoot(x) -- совершает повороты (x,p), где х -- вершина, p --

её предок, пока x не станет корнем дерева
splay(x) -- чередует 3 разновидности поворотов
zig(x) = (x,p) -- если p -- корень
zig-zig(x) = (p,q) + (x,p) -- если x и p -- правые либо левые дети
zig-zag(x) = (x,p) + (x,q) -- если х и р -- разные дети

Слайд 17

Операции над сплей-деревом
merge -- запускаем splay от самого большого элемента X,

подвешиваем справа Y ( Х <= Y)
split(x) -- запускаем splay(x), возвращаем левое и правое поддерево x
add(x) -- запускаем split(x), подвешиваем левое и правое поддерево к x в зависимости от того, больше или меньше корень, чем x
remove(x) -- запускаем splay(x), возвращаем merge его поддеревьев

Слайд 18

Слайд 19

Декартово дерево поиска
-- хранит элементы (x,y), где x -- ключ, а

y -- приоритет. Декартово дерево является деревом поиска по ключу и кучей по приоритету

Слайд 20

Операции над декартовым деревом
split(x): пусть x больше корня, тогда в левом

дереве окажется левое поддерево и левый результат операции split над правым поддеревом
Сложность -- высота дерева
merge(T1,T2) (все x1 < x2): Пусть у T1 корень больше по y. Тогда его левое поддерево -- левое поддерево результата, а правое поддерево результата -- слияние его правого поддерева и T2

Слайд 21

Операции над декартовым деревом
insert(x) -- разделим дерево по x, а потом

сольём сначала T1 и x, потом результат и T2
remove(x) -- разделяем дерево по х, удаляем x (он будет самым левым листом T2, сливаем результат

Слайд 22

Построение
По очереди вставим все элементы
Пусть элементы отсортированы по возрастанию ключей.

Смотрим на самый правый элемент в уже построенном дереве. Если можем -- добавляем. Если нет -- поднимаемся наверх до тех пор, пока не встретим больший приоритет. Тогда подвешиваем поддерево с меньшим приоритетом слева к вставляемому элементу, а сами становимся на его место. Всего к каждому элементу обратимся не более двух раз (если мы пробежали его, когда шли наверх -- больше не встретим). Итого асимптотика построения O(n)

Слайд 23

Высота декартова дерева
Теорема. В декартовом дереве на n узлов, у которого

приоритеты -- равномерно распределённые случайные величины, средняя глубина вершины -- O(logn)

Слайд 24

Красно-чёрное дерево
Дерево поиска, вершины которого промаркированы определённым цветом: красным или чёрным
Каждая

вершина — либо красная, либо черная
Каждый лист — черный
Если вершина красная, оба ее ребенка черные
Все пути, идущие от корня к листьям, содержат одинаковое количество черных вершин

Слайд 25

Высота красно-чёрного дерева
Чёрная высота x -- количество чёрных вершин на пути

из х в лист
Лемма. В КЧ-дереве с чёрной высотой Hb количество внутренних вершин не менее 2^(Hb-1)-1.
Докажем по индукции. Если одна чёрная вершина, то Hb=1. 2^(1-1)-1 = 0
Любая внутренняя вершина x имеет двух потомков -- их высоты на 1 меньше высоты x. Чёрные высоты потомков -- либо hb(x), либо hb(x)-1. Значит, в каждом из них не меньше 2^(hb(x)-2)-1 вершин. Суммарно + 1 за x -- 2*(2^hb(x)-2 - 1) + 1 = 2^(hb(x)-1)-1 вершин, чтд

Слайд 26

Высота красно-чёрного дерева
Лемма. Высота красно-чёрного дерева с N вершинами равна O(logn)
Количество

красных вершин не более h/2, чёрным -- не менее h/2-1
N>=2^(h/2 - 1)-1
log(N+1)>=h/2-1
h<=2(log(N+1)+1) => h = O(logn)

Слайд 27

Вставка элемента
Идём от корня до листа по условиям деревья поиска.
Вставляем вершину

с красным цветом. Если отец чёрный -- ничего не нарушено. Если отец красный -- смотрим на дядю: Дядя красный -- перекрашиваем отца и дядю в чёрный, деда в красный, балансируем дальше.
Дядя чёрный -- выполняем поворот между отцом и дедом, перекрашиваем обоих

Слайд 28

Удаление элемента
Три варианта:
Мы в листе -- изменяем указатель родителя на nul
Есть

один ребёнок -- вешаем его вместо вершины
Два ребёнка -- ищем вершину со следующим значением (самая левая в правом поддереве), копируем его в нашу вершину и удаляем одним из способов выше
Если удаляемая вершина была красной -- балансировка не нужна
Если чёрной, есть несколько случаев:

Слайд 29

B-дерево

Слайд 30

Операции над B-деревом

Слайд 31

Лекция 3+4. Деревья поиска

Содержание

Дерево поискаДерево, дерево с корнем. Высота дерева. Родительские и дочерние узлы,

Количество деревьев с пронумерованными вершинамиТеорема КэлиЧисло деревьев на n вершинах, пронумерованных

Код ПрюфераКодирование производится через последовательное удаление вершин дерева, имеющих наименьший номер

Код ПрюфераЛюбое дерево естественно переводится в Код Прюфера. Код имеет размер

Обход в глубинуДля бинарных деревьев -- pre-, post- и in-order

Обход в ширину

Деревья поискаПоиск ключа, вставка, удалениеНеобходимость балансировки

АВЛ-деревоХотим поддерживать разницу между поддеревьями любой вершины |h(L)-h(R)| <= 1Для этого

АВЛ-дерево

АВЛ-деревоДобавление элемента: сначала идём вниз от корня как при поиске, пока

АВЛ-деревоУдаление вершины.Если вершина -- лист, то просто удаляем. Если внутренняя, то

Слияние двух АВЛ-деревьевПусть есть деревья X и Y, все ключи X

Высота АВЛ-дерева

Сплей-деревоДерево, позволяющее получать быстрый доступ к элементам, которые были использованы последними

ЭвристикиmoveToRoot(x) -- совершает повороты (x,p), где х -- вершина, p --

Операции над сплей-деревомmerge -- запускаем splay от самого большого элемента X,

Декартово дерево поиска-- хранит элементы (x,y), где x -- ключ, а

Операции над декартовым деревомsplit(x): пусть x больше корня, тогда в левом

Операции над декартовым деревомinsert(x) -- разделим дерево по x, а потом

Построение По очереди вставим все элементыПусть элементы отсортированы по возрастанию ключей.

Высота декартова дереваТеорема. В декартовом дереве на n узлов, у которого

Красно-чёрное деревоДерево поиска, вершины которого промаркированы определённым цветом: красным или чёрнымКаждая

Высота красно-чёрного дереваЧёрная высота x -- количество чёрных вершин на пути

Высота красно-чёрного дереваЛемма. Высота красно-чёрного дерева с N вершинами равна O(logn)Количество

Вставка элементаИдём от корня до листа по условиям деревья поиска.Вставляем вершину

Удаление элементаТри варианта:Мы в листе -- изменяем указатель родителя на nulЕсть