Бинарного поиск (3)
|
|
|
|
|
|
|
Искомый элемент x = 9 |
Самостоятельно: |
|||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
поиск 4, 15. |
1 |
2 |
3 |
4 |
5 |
7 |
8 |
10 |
11 |
14 |
16 |
18 |
l = 1, u = 12, 1+[(12-1)/2] = 6 |
|
1 2 3 4 5
1 
2 
3 
4 
5 x x x x x
1 2 3 4 5
1 
2 
3 
4 
5 x x x x x
1 2 3 4 5
1 
2 
3 
4 
5 x x x x x
6 |
7 |
8 |
9 |
10 |
11 |
12 |
7 
8 
10 
11 
14 
16 
18 
x
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
7 |
8 |
10 |
11 |
14 |
16 |
18 |
|
x |
|
|
x |
x |
x |
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
7 |
8 |
10 |
11 |
14 |
16 |
18 |
|
x |
|
x |
x |
x |
x |
x |
|
l = u, al ≠ x |
l = 7, u = 12, 7+[(12-7)/2] = 9
l= 7, u = 9, 7+[(9-7)/2] = 8
l= 7, u = 7, 7+[(7-7)/2] = 7
31
Алгоритм бинарного поиска
BINARY_SEARCH(a, x)
1l ← 1, u ← n
2do
3 |
i ← l + [ (u – l)/2 ] |
4 |
if x < ai then ← i – 1 |
5else x > ai then l ← i + 1
6 |
while (l ≤ u и ai x) |
7 |
if l ≤ u then i ← 0 |
8return i
32
Дерево сравнений бинарного алгоритма
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
1 |
2 |
3 |
4 |
5 |
7 |
8 |
10 |
11 |
14 |
16 |
18 |
3 |
1 |
4 |
0 |
2 |
3 |
5 |
6
9 |
7 |
11 |
6 |
8 |
10 |
12 |
|
|
|
|
|
|
|
1 |
|
2 |
|
4 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
х |
– Реальный узел, хранит индекс |
|
элемента последовательности |
||
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
8 |
|
10 |
|
11 |
|
10 |
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
– Псевдоузел, соответствует
хнеудачному поиску
33
Количество шагов бинарного алгоритма
3 |
1 |
4 |
0 |
2 |
3 |
|
5 |
1 |
|
2 |
4 |
5 |
6
9 |
7 |
11 |
8 |
10 |
12 |
|
|
|
|
|
|
|
|
|
|
|
7 |
|
8 |
|
10 |
|
11 |
|
10 |
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№ элемента |
Число шагов |
№ элемента |
Число шагов |
6 |
1 |
2,5,8,10,12 |
4 |
3,9 |
2 |
не вх. |
3 или 4 |
1,4,7,11 |
3 |
|
|
34
Бинарные деревья
Бинарное дерево представляет собой структуру, в которой каждый узел (вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева называется корневым (или корнем) и является единственным узлом без родителя. Узлы, не имеющие потомков называются листьями.
Бинарное дерево с N узлами имеет не менее log2N+1 уровней (при
максимальной упаковке узлов), где x – округление в меньшую сторону. Например, у дерева, изображенного на рисунке N=15, а количество уровней – log215+1 = 3,9+1 = = 4.
35
Полное бинарное дерево
В полном бинарном дереве с j уровнями все листья расположены на уровне j, а у каждого узла на уровнях c 1 по (j – 1) в точности два непосредственных потомка.
Полные деревья |
Неполные деревья |
36
Свойства полных бинарных деревьев
Рассмотрим свойства полных деревьев:
1.Сбалансированное дерево с N узлами имеет log2N+1 уровней.
2.Количество элементов в полном дереве из k уровней: 2k – 1.
3.Количество Nkэлементов на k-м уровне (разность полных дер.): lev(k) = (2k – 1) – (2k–1 – 1) = 2k – 2k–1 = 2∙2k–1 – 2k–1 = 2k–1
37
Особенности деревьев поиска
Дерево поиска, состоящее из k уровней, отличается по структуре от полного дерева такой же высоты только последним уровнем. При этом поддереву, состоящему из реальных узлов (круглой формы), не достает ((2 log2N+1 – 1) – N) узлов до полного дерева с k = log2N+1 уровнями.
3 |
1 |
4 |
0 |
2 |
3 |
5 |
9 |
7 |
11 |
6 |
8 |
10 |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
|
4 |
|
5 |
|
7 |
|
8 |
|
10 |
|
11 |
|
10 |
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
38
Анализ алгоритма бинарного поиска (худший случай)
3 |
1 |
4 |
0 |
2 |
3 |
|
5 |
1 |
|
2 |
4 |
5 |
6
9 |
7 |
11 |
8 |
10 |
12 |
|
|
|
|
|
|
|
|
|
|
|
7 |
|
8 |
|
10 |
|
11 |
|
10 |
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Как и для последовательных алгоритмов, худшим является случай поиска несуществующего элемента. Для этого требуется пройти (k – 1) или k уровней, при k = log2n+1 .
При достаточно больших n трудоемкость алгоритма составляет:
Tбин(худш) = O(log2n)
39
Анализ алгоритма бинарного поиска (средний случай)
Возможно два средних случая:
1.Поиск всегда завершается успешно, то есть искомый элемент всегда присутствует в последовательности a. В данном случае считается, вероятность появления каждого элемента последовательности на входе а одинакова.
2.Поиск может окончиться неудачей. Существует некоторый диапазон R значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого диапазона.
40