 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Длительность операции поиска зависит от структуры дерева
|
|
Наибольший эффект использования дерева достигается в том случае,
когда дерево сбалансировано.
Поиск элемента в сбалансированном дереве называется бинарным поиском по дереву.
При бинарном поиске по дереву перебирается не больше log2N элементов. Другими словами, эффективность бинарного поиска по дереву имеет порядок O (log2N)
Алгоритм:
Пусть задан аргумент key
p = tree
whlie p <> nil do
if key = k(p) then
search = p
return
endif
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
search = nil
return
Поиск со вставкой (с включением)
o Для включения новой записи в дерево, прежде всего нужно найти тот узел, к которому можно присоединить новый элемент, не нарушив упорядоченности дерева.
o Модифицируем процедуру поиска по бинарному дереву так, чтобы фиксировалась ссылка на узел, после обработки которого поиск прекращается.
o С этой целью введем вспомогательный указатель q, отстающий от рабочего p на один шаг.
Алгоритм
p = tree
q = nil
while p <> nil do
q = p
if key = k(p) then
search = p
return
endif
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
v = maketree(key, rec)
if q = nil then
tree = v
else
if key < k(q) then
left(q) = v
else
right(q) = v
endif
endif
search = v
return
33. Сортировка методом прямого выбора
Этот метод основан на следующих принципах.
1. Выбирается элемент с наименьшим ключом.
2. Он меняется местами с первым элементом a1.
3. Затем этот процесс повторяется с оставшимися n -1 элементами, n -2 элементами и т.д. до тех пор, пока не останется один, самый "большой" элемент.
Алгоритм:
for i = 1 to n - 1
x = a(i)
k = i
for j = i + 1 to n
if a(j) < x then
k = j
x = a(k)
endif
next j
a(k) = a(i)
a(i) = x
next i
return
Эффективность:
► Число сравнений ключей C, очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для C при любом расположении ключей имеем: C = n (n -1)/2
► Порядок числа сравнений, таким образом, О(n 2)
► Число перестановок минимально Мmin = 3(n - 1) в случае изначально упорядоченных ключей
► и максимально, Мmax = 3(n - 1) + С, т.е. порядок О(n 2), если первоначально ключи располагались в обратном порядке.
► В худшем случае сортировка прямым выбором дает порядок n 2, как для числа сравнений, так и для числа перемещений.
Дата публикования: 2015-02-03; Прочитано: 242 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
