ВУЗ:
Составители:
Рубрика:
40
мерно
nnkn
2
log⋅≈⋅ . Ровно такая оценка была получена в алгоритме быстрой сор-
тировки; для произвольных данных улучшить эту оценку нельзя.
При выводе этой оценки мы исходили из того, что БДП является достаточно
сбалансированным. Это не всегда так. Например, при добавлении возрастающей
последовательности элементов каждый следующий элемент добавляется в правое
поддерево листа и дерево
вырождается в список:
3
8
12
99
...
Это – самый плохой случай: количество операций при вставке имеет порядок n, а
не
n
2
log , поэтому количество операций в алгоритме сортировки деревом состав-
ляет примерно
2
n .
Однако в среднем (если данные случайны и добавляются в случайном поряд-
ке) количество операций при сортировке деревом составляет примерно
nn
2
log
⋅
.
Отметим также, что мы получили компактный рекурсивный алгоритм сортировки
всего с одним циклом (!), совпадающий по оценке количества операций с одним
из самых производительных алгоритмов сортировки – быстрой сортировкой:
r:=nil;
for i:=1 to 10 do
Add(r);
InfixPrintTree(r);
Поиск элемента в БДП
Поиск в БДП осуществляется по той же схеме, что и добавление. Пусть
ищется элемент со
значением x. Если дерево пусто, то элемент не найден. Если
значение x совпадает со значением корневого элемента, то элемент найден. Если
значение x меньше значения корневого элемента, то рекурсивно ищем x в левом
поддереве, а если больше, то в правом поддереве. В случае успешного поиска бу-
дем возвращать указатель на
элемент, в противном случае будем возвращать nil:
function Search(x: DataType; r: PNode): PNode;
begin
if r=nil then
Result:=nil
else if r.data=x then
Result:=r
else if r.data<x then
Result:=Search(x,r.right)
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »
