Основы программирования. Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы - 37 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

39
БДП обладают одним замечательным свойством: при их обходе в инфиксном
порядке мы получаем неубывающую последовательность. Так, инфиксный обход
дерева, приведенного на рисунке, даст следующую последовательность:
3 8 12 17 27 29 39 41 42 60 70 73 81 90 99
Основными операциями при работе с БДП являются добавление, удаление и
поиск элемента. Все указанные операции реализуются рекурсивно.
Добавление элемента в БДП
При добавлении элемента в
дерево возможно несколько ситуаций. Если де-
рево пусто, то элемент необходимо добавить в его корень. В противном случае,
если значение элемента меньше значения поля данных в корне, элемент необхо-
димо добавить в левое поддерево, а если больше, то в правое поддерево:
procedure Add(x: DataType; var r: PNode);
begin
if r=nil then
r:=NewNode(x,nil,nil)
else if x<r.data then
Add(x,r.left)
else if x>r.data then
Add(x,r.right)
end;
Заметим, что после добавления элемента дерево остается деревом поиска.
Заметим также, что при таком алгоритме добавления мы получим БДП без повто-
ряющихся элементов. Чтобы получить БДП с повторяющимися элементами, дос-
таточно удалить отрезок кода if x>r.data then.
Оценим количество операций при добавлении в
БДП. Мы знаем, что в пол-
ном дереве с k уровнями количество элементов n =
12
1
−
+k
. Очевидно, если дерево
близко к полному (в частности, если оно идеально сбалансировано), то
k
n 2≈ ,
следовательно, количество уровней
nk
2
log
≈
. Например, при n = 1024 элемента
глубина хорошо сбалансированного дерева близка к 10. Поскольку при каждом
рекурсивном шаге операции добавления мы спускаемся вниз по дереву на один
уровень и делаем одну операцию, глубина рекурсии и количество операций при
добавлении равны глубине дерева k, т.е. составляют примерно
n
2
log .
На алгоритме добавления в БДП основана очень эффективная сортировка
деревом. В ней используется свойство БДП выдавать отсортированную последо-
вательность при инфиксном обходе. Алгоритм такой сортировки прост: в перво-
начально пустое БДП с повторяющимися элементами добавляем все элементы с
помощью процедуры Add, после чего выдаем все элементы, обходя дерево в ин-
фиксном
порядке. Если в процессе добавления дерево остается сбалансирован-
ным, то при добавлении в него n элементов количество операций составляет при-

Страницы