Презентация на тему Сбалансированные деревья поиска

порядке
Для решения данной задачи можно построить бинарное дерево поиска

друзьям, что он знает, как гравитация ведет себя, но

20, 30, 40, 50, 60, 70
Последовательная вставка элементов дает

30, 50, 70

порядка выполнения операций вставки и удаления элементов
Высота бинарного дерева,

вставки и удаления
Эффективность поиска в таких деревьев близка к

два значения
Узлы дерева делятся на две категории:
Листья
Промежуточные узлы: Если промежуточный

все значения, лежащие в левом поддереве, имеют значения, меньшие

означает следующее: Пусть А1 и А2– значения ключей элементов, хранящиеся

| 8
4 | 10
11 | 13
16 | 19
2
24

30
5 | 8
4 | 10
11 | 13
2
24

дерева находятся на одном и том же уровне
Высота 2-3

8
13
19
30
25
Высота дерева с точки зрения логической

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

8
4 | 10
11 | 12 |13
16 | 19
2
23

Переполнение узла

8
4 | 10
16 | 19
12
23 |24
Разбиваем на 2

13

11

2

Поднимаем вверх

8
4 | 10 | 12
16 | 19
23 |24
13
11
2

8
16 | 19
23 |24
13
11
2
10
12
4

узел

0 | 1
Ссылка на значение перемещается вместе со значением

в таком дереве имеет порядок O(log2(N))

с 2-3 деревом алгоритмы вставки и удаления элементов осуществляются

пусто
или имеет один из следующих видов:
r-узел, содержащий соответственно

1 элемент)
2) K(TL)

этом один из его элементов перемещается в родительский узел

имеет двухместого родителя
Узел имеет трехместного родителя

симметричным преемником (самый левый узел в правом поддереве)
Удаляем элемент

необходимо сразу преобразовать каждый двухместный узел в трех или

что они хорошо сохраняют баланс
Алгоритмы вставки и удаления в