Организация поиска

Июль 28, 2022

Главная
Информатика
Организация поиска

Содержание

2. Поисковое дерево называется 2-3-деревом, если оно обладает следующими свойствами: каждая вершина x, не являющаяся листом, содержит
3. Каждая внутренняя вершина 2-3 –дерева является справочной и содержит две метки: а=left_max_val(v) – максимальное значение ключа
4. Если в 2-3-дереве только один лист, (например, 4), то это дерево имеет следующий вид: 4 3:4
5. ФПМИ БГУ Пример
6. ТЕОРЕМА Пусть n – общее количество вершин в 2-3-дереве (включая корень и листья); l – количество
7. Первое неравенство доказано. ФПМИ БГУ Предположим, что теорема верна для деревьев высоты h и докажем её
8. ФПМИ БГУ Неравенство (2) также доказано.
9. Как следует из левой части неравенства (2): ТЕОРЕМА Пусть n – общее количество вершин в 2-3-дереве
10. Поиск элемента с ключом x Двигаемся от корня. Пусть t – текущая вершина. ФПМИ БГУ
11. 10:99 18 17 11 10 8 7 3 1 11:17 8:10 1:3 84 70 25 18:25
12. 10:99 18 17 11 10 8 7 3 1 11:17 8:10 1:3 84 70 25 18:25
13. Добавление элемента 10:99 18 17 11 10 8 7 3 1 8:10 1:3 84 70 25
14. 10:99 18 17 11 10 8 4 1 11:17 8:9 1:4 84 70 25 18:25 4:10
15. f v Случай увеличения высоты дерева после добавления элемента. ФПМИ БГУ Insert (9)
16. Удаление элемента 10:99 18 17 11 10 8 7 3 1 11:17 8:10 1:3 84 70
17. v=f рекурсивно продолжаем удаление: v=f f=f’ g1 ФПМИ БГУ случай, когда у отца f удаляемой вершины
18. После удаления вершины v высота дерева может уменьшится на 1: ФПМИ БГУ v f
19. Оценки Поиск элемента Добавление элемента Удаление элемента ФПМИ БГУ O(lоg n)
20. Важными дополнительными операциями, которые можно эффективно выполнять для 2-3-дерева являются: Join (T1,T2) – объединение двух 2-3-деревьев,
21. Join (T1,T2) – объединение двух 2-3-деревьев, при условии, что все ключи в дереве T1 меньше, чем
22. Split (x)– разделение дерева Т по ключу x на два дерева T1 и T2, при этом
23. 8:15 10:15 9:10 3 4 5 7 8 2 1 9 10 11 13 15 17
24. Удаление из дерева непрерывного участка ключей, лежащих в интервале [a,b] ФПМИ БГУ
25. 8:15 3:5 1:2 4:5 7:8 10:15 9:10 11:13 56:76 17:40 60:70 3 4 5 7 8
27. Скачать презентацию

Слайд 2

Поисковое дерево называется 2-3-деревом, если оно обладает следующими свойствами:
каждая вершина x,

не являющаяся листом, содержит два или три сына (левый l(x), средний m(x) и (возможно) правый сын r(x);
все висячие вершины находятся на одной глубине и содержат сами элементы;
внутренние вершины ) – справочные(внутренние – это все вершины дерева за исключением листьев.

10:99

1
11:17

8:10

1:3

18:25

7:10

84:99
17:70

ФПМИ БГУ

так как дерево поисковое, то ключи всех листьев идут слева направо по возрастанию

Слайд 3

Каждая внутренняя вершина 2-3 –дерева является справочной и содержит две метки:
а=left_max_val(v)

– максимальное значение ключа в поддереве, корень которого – левый сын вершины v;
b=midl_max_val(v) – максимальное значение ключа в поддереве, корень которого – средний сын вершины v;

a : b

ФПМИ БГУ

Слайд 4

Если в 2-3-дереве только один лист, (например, 4), то это дерево

имеет следующий вид:

3:4

ФПМИ БГУ

Если в 2-3-дереве только два листа (например, 3 и 4) , то это дерево имеет следующий вид:

Слайд 5

ФПМИ БГУ
Пример

Слайд 6

ТЕОРЕМА
Пусть
n – общее количество вершин в 2-3-дереве (включая корень

и листья);
l – количество листьев;
h – высота дерева.
Тогда справедливы следующие неравенства:

Доказательство проводится, используя метод математической индукции.
База индукции: h=1. Утверждение верно.

ФПМИ БГУ

Слайд 7

Первое неравенство доказано.
ФПМИ БГУ
Предположим, что теорема верна для деревьев высоты h

и докажем её для деревьев высоты h+1.
Сначала докажем первое неравенство.
При увеличении высоты дерева на 1 минимальное число листьев получаем, когда у дерева высоты h с минимальным числом листьев к каждому листу добавляем 2 сына, а максимальное, когда у дерева высоты h с максимальным числом листьев к каждому листу добавляем 3 сына:

Слайд 8

ФПМИ БГУ

Неравенство (2) также доказано.

Слайд 9

Как следует из левой части неравенства (2):
ТЕОРЕМА
Пусть
n –

общее количество вершин в 2-3-дереве (включая корень и листья);
l – количество листьев;
h – высота дерева.
Тогда справедливы следующие неравенства:

Слайд 10

Поиск элемента с ключом x
Двигаемся от корня.
Пусть t – текущая

вершина.

ФПМИ БГУ

Слайд 11

10:99
18
17
11
10
8
7
3
1
11:17
8:10
1:3
84
70
25
18:25
7:10
84:99
17:70
99
ФПМИ БГУ
? 25

Слайд 12

10:99
18
17
11
10
8
7
3
1
11:17
8:10
1:3
84
70
25
18:25
7:10
84:99
17:70
99
ФПМИ БГУ
?= 9
НЕТ
? 9

Слайд 13

Добавление элемента
10:99
18
17
11
10
8
7
3
1
8:10
1:3
84
70
25
18:25
7:10
84:99
17:70
:
99
Insert (13)
13
ФПМИ БГУ
f
x
у вершины f после добавления становится 3 сына,

что допустимо;
корректируем метки справочных вершин вдоль пути поиска;
завершаем процедуру добавления элемента x;

Сначала осуществляем поиск отца f для добавляемого элемента x (в качестве f берём отца вершины t):
11:17
11:13

Слайд 14

10:99
18
17
11
10
8
4
1
11:17
8:9
1:4
84
70
25
18:25
4:10
84:99
17:70
99
9
5
5:8
ФПМИ БГУ
Insert (5)
4:8

Слайд 15

f
v
Случай увеличения высоты дерева после добавления элемента.
ФПМИ БГУ
Insert (9)

Слайд 16

Удаление элемента
10:99
18
17
11
10
8
7
3
1
11:17
8:10
1:3
84
70
25
18:25
7:10
84:99
17:70
99
Удаляем вершину.
Если у отца f удаляемой вершины останется 2

сына, то это допустимо для 2-3-дерева.
Корректируем метки справочных вершин вдоль пути поиска.
Завершаем процедуру удаления.

ФПМИ БГУ

Delete (25)

18:70

Слайд 17

v=f
рекурсивно продолжаем удаление:
v=f
f=f’
g1
ФПМИ БГУ
случай, когда у отца f удаляемой вершины v

останется только один сын x :

или

корректируем метки на пути от корня до f;
удаление завершено;

f=f’

Слайд 18

После удаления вершины v высота дерева может уменьшится на 1:
ФПМИ БГУ
v
f

Слайд 19

Оценки
Поиск элемента
Добавление элемента
Удаление элемента
ФПМИ БГУ
O(lоg n)

Слайд 20

Важными дополнительными операциями, которые можно эффективно выполнять для 2-3-дерева являются:
Join (T1,T2)

– объединение двух 2-3-деревьев, при условии, все ключи в дереве T1 меньше, чем ключи в дереве T2
Split (x)– разделение дерева Т по ключу x на два дерева T1 и T2, при этом ключи всех вершин в дереве T1 меньше x, а в дереве T2– больше x

ФПМИ БГУ

Слайд 21

Join (T1,T2) – объединение двух 2-3-деревьев, при условии, что все ключи

в дереве T1 меньше, чем ключи в дереве T2

h-2

h-1

Т1

h-2

Т2

Время работы пропорционально модулю разности высот объединяемых деревьев:
|h(T1)- h(T2)|

ФПМИ БГУ

Слайд 22

Split (x)– разделение дерева Т по ключу x на два дерева

T1 и T2, при этом ключи всех вершин в дереве T1 меньше ключа x, а в дереве T2 – больше x

8:15

10:15

9:10

количество деревьев в каждой из полученных частей не превосходит - log n
при слиянии деревьев в левой (правой) частях будем всегда выполнять процедуру Join над деревьями меньшей высоты, тогда время, затраченное на построение каждого из деревьев Т1 и Т2 - O(log n)

ФПМИ БГУ

Split(10)

Время выполнения Split (x)
O(log n)

Слайд 23

8:15
10:15
9:10
3
4
5
7
8
2
1
9
10
11
13
15
17
40
56
70
60
76
ФПМИ БГУ
3
4
5
7
8
2
1
9
11
13
15
17
40
56
70
60
76
T1
T2
Split (10)
продолжение

Слайд 24

Удаление из дерева непрерывного участка ключей, лежащих в интервале [a,b]
ФПМИ БГУ

Слайд 25

8:15
3:5
1:2
4:5
7:8
10:15
9:10
11:13
56:76
17:40
60:70
3
4
5
7
8
2
1
9
10
11
13
15
17
40
56
70
60
76
3:5
1:2
4:5
7:8
60:70
3
4
5
7
8
2
1
40
56
70
60
76
9
40:56
56:76
9:76
Время работы:
О(log n)
ФПМИ БГУ
не зависит от размера удаляемого участка

Организация поиска

Содержание

Поисковое дерево называется 2-3-деревом, если оно обладает следующими свойствами:каждая вершина x,

Каждая внутренняя вершина 2-3 –дерева является справочной и содержит две метки:а=left_max_val(v)

Если в 2-3-дереве только один лист, (например, 4), то это дерево

ФПМИ БГУПример

ТЕОРЕМА Пусть n – общее количество вершин в 2-3-дереве (включая корень

Первое неравенство доказано.ФПМИ БГУПредположим, что теорема верна для деревьев высоты h

ФПМИ БГУ Неравенство (2) также доказано.

Как следует из левой части неравенства (2): ТЕОРЕМА Пусть n –

Поиск элемента с ключом xДвигаемся от корня. Пусть t – текущая

10:9918171110873111:178:101:384702518:257:1084:9917:7099ФПМИ БГУ ? 25

10:9918171110873111:178:101:384702518:257:1084:9917:7099ФПМИ БГУ ?= 9 НЕТ ? 9

Добавление элемента10:991817111087318:101:384702518:257:1084:9917:70:99Insert (13)13ФПМИ БГУfxу вершины f после добавления становится 3 сына,

10:991817111084111:178:91:484702518:254:1084:9917:7099955:8ФПМИ БГУInsert (5)4:8

fvСлучай увеличения высоты дерева после добавления элемента. ФПМИ БГУInsert (9)

Удаление элемента10:9918171110873111:178:101:384702518:257:1084:9917:7099Удаляем вершину. Если у отца f удаляемой вершины останется 2

v=fрекурсивно продолжаем удаление:v=ff=f’g1ФПМИ БГУслучай, когда у отца f удаляемой вершины v

После удаления вершины v высота дерева может уменьшится на 1:ФПМИ БГУvf

ОценкиПоиск элемента Добавление элемента Удаление элементаФПМИ БГУO(lоg n)

Важными дополнительными операциями, которые можно эффективно выполнять для 2-3-дерева являются:Join (T1,T2)

Join (T1,T2) – объединение двух 2-3-деревьев, при условии, что все ключи

Split (x)– разделение дерева Т по ключу x на два дерева

8:1510:159:103457821910111315174056706076ФПМИ БГУ34578219111315174056706076T1T2 Split (10)продолжение

Удаление из дерева непрерывного участка ключей, лежащих в интервале [a,b]ФПМИ БГУ

8:153:51:24:57:810:159:1011:1356:7617:4060:7034578219101113151740567060763:51:24:57:860:7034578214056706076940:5656:769:76Время работы:О(log n)ФПМИ БГУне зависит от размера удаляемого участка

Похожие презентации

Поисковое дерево называется 2-3-деревом, если оно обладает следующими свойствами:
каждая вершина x,

Каждая внутренняя вершина 2-3 –дерева является справочной и содержит две метки:
а=left_max_val(v)

ФПМИ БГУ
Пример

ТЕОРЕМА
Пусть
n – общее количество вершин в 2-3-дереве (включая корень

Первое неравенство доказано.
ФПМИ БГУ
Предположим, что теорема верна для деревьев высоты h

ФПМИ БГУ

Неравенство (2) также доказано.

Как следует из левой части неравенства (2):
ТЕОРЕМА
Пусть
n –

Поиск элемента с ключом x
Двигаемся от корня.
Пусть t – текущая

10:99
18
17
11
10
8
7
3
1
11:17
8:10
1:3
84
70
25
18:25
7:10
84:99
17:70
99
ФПМИ БГУ
? 25

10:99
18
17
11
10
8
7
3
1
11:17
8:10
1:3
84
70
25
18:25
7:10
84:99
17:70
99
ФПМИ БГУ
?= 9
НЕТ
? 9

Добавление элемента
10:99
18
17
11
10
8
7
3
1
8:10
1:3
84
70
25
18:25
7:10
84:99
17:70
:
99
Insert (13)
13
ФПМИ БГУ
f
x
у вершины f после добавления становится 3 сына,

10:99
18
17
11
10
8
4
1
11:17
8:9
1:4
84
70
25
18:25
4:10
84:99
17:70
99
9
5
5:8
ФПМИ БГУ
Insert (5)
4:8

f
v
Случай увеличения высоты дерева после добавления элемента.
ФПМИ БГУ
Insert (9)

Удаление элемента
10:99
18
17
11
10
8
7
3
1
11:17
8:10
1:3
84
70
25
18:25
7:10
84:99
17:70
99
Удаляем вершину.
Если у отца f удаляемой вершины останется 2

v=f
рекурсивно продолжаем удаление:
v=f
f=f’
g1
ФПМИ БГУ
случай, когда у отца f удаляемой вершины v

После удаления вершины v высота дерева может уменьшится на 1:
ФПМИ БГУ
v
f

Оценки
Поиск элемента
Добавление элемента
Удаление элемента
ФПМИ БГУ
O(lоg n)

Важными дополнительными операциями, которые можно эффективно выполнять для 2-3-дерева являются:
Join (T1,T2)

8:15
10:15
9:10
3
4
5
7
8
2
1
9
10
11
13
15
17
40
56
70
60
76
ФПМИ БГУ
3
4
5
7
8
2
1
9
11
13
15
17
40
56
70
60
76
T1
T2
Split (10)
продолжение

Удаление из дерева непрерывного участка ключей, лежащих в интервале [a,b]
ФПМИ БГУ

8:15
3:5
1:2
4:5
7:8
10:15
9:10
11:13
56:76
17:40
60:70
3
4
5
7
8
2
1
9
10
11
13
15
17
40
56
70
60
76
3:5
1:2
4:5
7:8
60:70
3
4
5
7
8
2
1
40
56
70
60
76
9
40:56
56:76
9:76
Время работы:
О(log n)
ФПМИ БГУ
не зависит от размера удаляемого участка