<< Пред. стр. 7 (из 19) След. >>
Список литературы по разделу
С = 10.
Можно совместить бинарный и индексно-последовательный поиск (при больших объемах данных), учитывая, что последний также используется при отсортированном массиве.
5.7. Поиск по бинарному дереву
Назначение его в том, чтобы по заданному ключу осуществить поиск узла дерева. Длительность операции зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список, как правое на рис. 5.8.
В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. придется перебирать N/2 элементов.
Наибольшего эффекта использования дерева достигается в том случае, когда дерево сбалансировано.В этом случае для поиска придотся перебрать не больше 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
p := tree;
whlie p <> nil do
begin
if key = p^.k then
begin
search := p;
exit;
end;
if key < p^.k then
p := p^.left
else
p := p^.right;
end;
search := nil;
5.8 Поиск со вставкой (с включением)
Для вставки элемента в дерево, сначало нужно осуществить поиск в дереве по заданному ключу. Если такой ключ имеется, то программа завершается, если нет, то происходит вставка.
Для включения новой записи в дерево, прежде всего нужно найти тот узел, к которому можно присоединить новый элемент. Алгоритм поиска нужного узла тот же самый, что и при поиске узла с заданным ключом. Однако непосредственно использовать процедуру поиска нельзя, потому что по ее окончании не фиксирует тот узел, из которого была выбрана ссылка NIL (search = nil).
Модифицируем описание процедуры поиска так, чтобы в качестве ее побочного эффекта фиксировалась ссылка на узел, в котором был найден заданный ключ (в случае успешного поиска), или ссылка на узел, после обработки которого поиск прекращается (в случае неуспешного поиска).
Псевдокод:
P = tree
Q = nil
Whlie 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
Паскаль:
p := tree;
q := nil;
whlie p <> nil do
begin
q := p;
if key = p^.k then
begin
search := p;
exit;
end;
if key < p^.k then
p := p^.left
else
p := p^.right;
end;
v := maketree(key, rec)
if q=nil then
tree:=v
else
if key < q^.k then
q^.left := v
else
q^.right := v;
search := v;
5.9 Поиск с удалением
Удаление узла не должно нарушить упорядоченности дерева. Возможны три варианта:
1) Найденный узел является листом. Тогда он просто удаляется и все.
2) Найденный узел имеет только одного сына. Тогда сын перемещается на место отца.
3) У удаляемого узла два сына. В этом случае нужно найти подходящее звено поддерева, которое можно было бы вставить на место удаляемого. Такое звено всегда существует:
- это либо самый правый элемент левого поддерева (для достижения этого звена необходимо перейти в следующую вершину по левой ветви, а затем переходить в очередные вершины только по правой ветви до тех пор, пока очередная ссылка не будет равна NIL.
- либо самый левый элемент правого поддерева (для достижения этого звена необходимо перейти в следующую вершину по правой ветви, а затем переходить в очередные вершины только по левой ветви до тех пор, пока очередная ссылка не будет равна NIL
Предшественником удаляемого узла называют самый правый узел левого поддерева (для 12 - 11). Преемником - самый левый узел правого поддерева (для 12 - 13).
Будем разрабатывать алгоритм для преемника (рис.5.9).
p - рабочий указатель;
q - отстает от р на один шаг;
v - указывает на приемника удаляемого узла;
t - отстает от v на один шаг;
s - на один шаг впереди v (указывает на левого сына или пустое место).
На узел 13 в конечном итоге должен указывать v, а указатель s - на пустое место (как показано на рис. 5.9).
Псевдокод:
q = nil
p = tree
while (p <> nil) and (k(p) <> key) do
q = p
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
if p = nil then ‘Ключ не найден’
return
endif
if left(p) = nil then v = right(p)
else if right(p) = nil
then v = left(p)
else
‘У nod(p) - два сына’
‘Введем два указателя (t отстает от v на 1 ‘шаг, s - опережает)
t = p
v = right(p)
s = left(v)
while s <> nil do
t = v
v = s
s = left(v)
endwhile
if t <> p then
‘v не является сыном p’
left(t) = right(v)
right(v) = right(p)
endif
left(v) = left(p)
endif
endif
if q = nil then ‘p - корень’
tree = v
else if p = left(q)
then left(q) = v
else right(q) = v
endif
endif
freenode(p)
return
Паскаль:
q := nil;
p := tree;
while (p <> nil) and (p^.k <> key) do
begin
q := p;
if key < p^.k then
p := p^.left
else
p := p^.right;
end;
if p = nil then
WriteLn(‘Ключ не найден’);
exit;
end;
if p^.left = nil then
v := p^.right
else
if p^.right = nil then
v := p^.left
else
begin
{Введем два указателя (t отстает от v на 1 шаг, s - опережает)}
t := p;
v := p^.right;
s := v^.left;
while s <> nil do
begin
t := v;
v := s;
s := v^.left;
end;
if t <> p then
begin
WriteLn(‘v не является сыном p’);
t^.left := v^.right;
v^.right := p^.right;
end;
v^.left := p^.left;
end;
end;
if p = q^.left then
q^.left := v
else
q^.right := v;
end;
dispose(p);
end;
Контрольные вопросы
1. В чем состоит назначение поиска ?
2. Что такое уникальный ключ ?
3. Какая операция производится в случае отсутствия заданного ключа в списке ?
4. В чем разница между последовательным и индексно-последовательным поиском ?
5. Какой из них более эффективный и почему ?
6. Какие способы переупорядочивания таблицы вы знаете ?
7. Основные отличия метода перестановки в начало от метода транспозиции .
8. Где они будут работать быстрее, в массиве или списке ?
9. В каких списках они работают, упорядоченных или нет ?
10. В чем суть бинарного поиска?
11. Как можно обойти бинарное дерево?
12. Можно ли применять бинарный поиск к массивам ?
13. Если удалить корень в непустом бинарном дереве, какой элемент станет на его место ?
6. СОРТИРОВКА
При обработке данных важно знать информационное поле данных и размещение их в машине.
Различают внутреннюю и внешнюю сортировку:
- внутренняя сортировка - сортировка в оперативной памяти;
- внешняя сортировка - сортировка во внешней памяти.
Сортировка - это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание (убывание) значения ключа от начала к концу в массиве.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей, делают перестановку указателей, т.е. сам массив не перемещается. Это метод сортировки таблицы адресов.
При сортировке могут встретиться одинаковые ключи. В этом случае при сортировке желательно расположить после сортировки одинаковые ключи в том же порядке, что и в исходном файле. Это - устойчивая сортировка.
Эффективность сортировки можно рассматривать с нескольких критериев:
* время, затрачиваемое на сортировку;
* объем оперативной памяти, требуемой для сортировки;
* время, затраченное программистом на написание программы.
Выделяем первый критерий, поскольку будем рассматривать только методы сортировки «на том же месте», то есть не резервируя для процесса сортировки дополнительную память. Эквивалентом затраченного на сортировку времени можно считать количество сравнений при выполнении сортировки и количество перемещений.
Порядок числа сравнения при сортировке лежит в пределах от О (n log n) до О (n2); О (n) - идеальный и недостижимый случай.
Различают следующие методы сортировки:
* строгие (прямые) методы;
* улучшенные методы.
Строгие методы:
1) метод прямого включения;
2) метод прямого выбора;
3) метод прямого обмена.
Эффективность этих трех методов примерно одинакова.
6.1. Сортировка методом прямого включения
Такой метод широко используется при игре в карты. Элементы мысленно делятся на уже готовую последовательность a1,...,ai-1 и исходную последовательность. При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исхожной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.На рис. 6.2 показан в качестве примера процесс сортировки с помощью включения шести случайно выбранных чисел. Алгоритм этой сортировки таков:
for i = 2 to n
x = a(i)
находим место среди а(1)…а(i) для включения х
next i
Для сортировки методом прямого включения пользуются следующими приемами:
Псевдокод:
Без барьера:
for i = 2 to n
x = a(i)
for j = i - 1 downto 1
if x < a(j )
then a( j + 1) = a(j )
else go to L
endif
next j
L: a( j + 1) = x
next i
return
С барьером:
for i = 2 to n
x = a(i)
a(0) = x {a(0) - барьер}
j = i - 1
while x < a(j ) do
a( j +1) = a(j )
j = j - 1
endwhile
a( j +1) = x
next i
<< Пред. стр. 7 (из 19) След. >>
Список литературы по разделу