При описанном построении дерева поиск оказывается довольно простым делом: сначала мы сравниваем искомый ключ с ключом корня дерева. Если эти два ключа совпадают, то элемент найден, в противном случае выполняем поиск в левом поддереве, иначе – в правом, далее в выбранном поддереве вновь выполняем сравнение его корня с искомым ключом, и т. д. Этот процесс закончится либо когда мы нашли ключ, либо когда очередное поддерево оказалось пустым (это означает, что такой ключ в дереве отсутствует).
Для реализации двоичного дерева сначала рассмотрим его описание на Паскале:
type tNodePtr = ^tNode; {указатель на вершину}
tNode = record
data: tMyData;
left,right: tNodePtr;
end;
tTree = tNodePtr; {для доступа к дереву достаточно хранить
указатель на его корень}
Под данными (tMyData) будем понимать запись, состоящую из ключа, необходимого для сравнений, и собственно данных:
type tMyData = record
key: tKey;
data: tData;
end;
Для того чтобы реализовать действия с двоичным дерево, нам понадобятся так называемые рекурсивные процедуры. Функция или процедура называется рекурсивной, если она вызывает сама себя. Такой вариант рекурсии называется прямым. Кроме того, бывает и косвенная рекурсия, когда одна процедура вызывает другую, а та в свою очередь вызывает первую.
В качестве примера рассмотрим функцию для вычисления факториала, в которой мы заменим цикл (или итерацию) рекурсией. Её идея проста: если аргумент равен нулю, то возвращаем значение 1, в противном случае возвращаем значение аргумента, умноженное на факториал (то есть ту же функцию) от числа, на единицу меньшего. На Паскале всё это будет выглядеть следующим образом:
function factorial(x: byte): longint;
begin
if x=0 then factorial:=1
else factorial:=x*factorial(x-1);
end;
Подобным образом можно применить рекурсию для вычисления n-го числа Фибоначчи, хотя этот способ требует много лишних действий:
function fib(n: integer): integer;
begin
if n<=1 then fib:=1 else fib:=fib(n-1)+fib(n-2);
end;
Косвенная рекурсия может появиться, например при проверке правильности арифметических выражений. Подробно рассматривать этот вопрос сейчас мы не будем.
Возвращаясь к деревьям, заметим, что добавление элемента является рекурсивной процедурой:
procedure InsertNode(t: tTree; key: tKey; data: tData);
begin
if t=nil then begin
new(t);
t^.key:=key;
t^.data:=data;
end
else if key<t^.key then InsertNode(t^.left,key,data)
else InsertNode(t^.right,key,data);
end;
После того как дерево построено, можно выполнять поиск (также рекурсивный):
function Search(t: tree; key: tKey; var data: tData): boolean;
{возвращает значение найден / не найден}
begin
if t=nil then Search:=false
else if key = t^.key then begin
data:=t^.data;
Search:=true;
end
else if key<t^.key then Search:=Search(t^.left,key,data)
else Search:=Search(t^.right,key,data);
end;
Легко заметить, что элементы данных, «уложенные» в двоичное дерево можно выводить в отсортированном порядке:
procedure Traversal(t: tTree); {обход дерева}
begin
if t<>nil then begin
Traversal(t^.left);
writeln('Key:',t^.key,' Data:',t^.data);
Traversal(t^.right);
end;
end;
Лекция 18. Таблицы и простейшие алгоритмы поиска.
1. Определения и описания структур данных
Таблицей будем называть структуру данных, пригодную для хранения набора данных, имеющих одинаковые типы. Простейшим примером такой структуры может служить массив, поскольку тип всех его элементов один и тот же. Чаще всего элемент таблицы состоит из нескольких частей, одна из которых имеет наибольшее значение (называется ключом), а остальные содержат информацию, связанную с этим ключом, или собственно данные. Если всё это изобразить графически, то получится то, что называется таблицей в обычном смысле:
| Ф. И. О. | Адрес | Телефон | Год рождения |
| Петров Ф. М. | Северная 99-88 | 29-29-29 | 1962 |
| Иванов П. С. | Мира 111-222 | 77-88-99 | 1976 |
| Козлов Н. В. | Октябрьская 135-246 | 45-67-89 | 1970 |
| ................. |
Здесь ключом является фамилия, а все остальные элементы — полезная информация о человеке с такой фамилией. В случае, когда наша таблица становится довольно большой, найти данные о нужном нам человеке становится довольно сложно. Алгоритмы, предназначенные для поиска в таблице данных с указанным ключом, называются алгоритмами поиска. Поиск может быть удачным (если элемент с искомым ключом имеется в массиве) и неудачным (в противном случае).
При использовании языка Паскаль для работы с табличными данными довольно удобно использовать записи в качестве элементов данных. В нашем примере таблица будет состоять из элементов следующего типа:
type tItem {элемент} = record
surname: string[30]; {фамилия, ключевое поле}
address: string; {адрес}
phone: longint; {телефон}
birth: word; {год рождения}
end;
При рассмотрении алгоритмов поиска мы будем пользоваться более общей формой для записи типа элемента:
type tItem = record
key: tKey; {ключ}
data: tData; {данные}
end;
Типы tKey и tData зависят от конкретной задачи, которую нужно решать. В нашем примере tKey — строка до 30 символов длиной, а tData можно сделать записью из трёх полей (address, phone и birth).
Рассмотрим теперь некоторые способы реализации всей таблицы:
1. Массив
Это наиболее простой вариант и довольно удобный, поскольку положение элемента в таблице однозначно определяется номером элемента в массиве. Если размер таблицы меняется в ходе работы с ней (данные время от времени добавляются или удаляются), то массив оказывается не очень экономичным: поскольку точное количество элементов заранее неизвестно, приходится заводить массив из большого количества элементов, часть из которых не будет использоваться, но будет занимать место в памяти.
Для того чтобы хранить таблицу, нам потребуется запись из двух полей: сам массив и целочисленное поле, обозначающее текущий размер массива:
const maxsize = 2000; {максимальный размер таблицы}
type tTable = record
a: array[1..maxsize] of tItem; {это сам массив}
n: integer; {а это - реальное число элементов}
end;
var Table: tTable;
Предполагается, что в любой момент времени данные таблицы хранятся в первых n элементах массива, а остальные считаются пустыми.
2. Список
Этот вариант более экономичен в плане расхода памяти, так как всегда будет занято ровно столько места, сколько нужно под данные. В отличие от массива, мы не можем легко просматривать данные произвольного элемента, для перехода от одного элемента к другому нужно долго двигаться по цепочке указателей; это является недостатком списка.
Как выглядит такая таблица на Паскале нам уже известно:
type tItemPtr = ^tItem; {указатель на элемент списка}
tItem = record {элемент списка}
key: tKey;
data: tData;
next: tItemPtr;
end;
tList: tItemPtr; {задаётся указателем на первый элемент}
var Table: tList {таблица является списком}
3. Дерево
Как хранить и искать данные в двоичном дереве, мы уже знаем, а таблицу можно задать так:
type tItemPtr = ^tItem; {указатель на элемент}
tItem = record {элемент}
key: tKey;
data: tData;
left, right: tItemPtr;
end;
tTree = tItemPtr;
var Table: tTree; {таблица является деревом}
2. Алгоритмы
1. Линейный поиск в массиве
Пусть таблица представлена в виде массива. Тогда первое, что приходит в голову по поводу поиска элемента — это обход всех элементов, начиная с первого, до тех пор, пока не будет найден элемент с искомым ключом, или пока массив не кончится. Такой способ называется линейным поиском в неупорядоченном массиве. Оформим его на Паскале в виде процедуры:
procedure LinearSearch(var T:tTable; k:tKey; var index:integer);
var i: integer;
begin
i:=1; index:=0;
while (i<=T.n)and(index=0) do begin
if T.a[i].key=k then index:=i;
i:=i+1;
end;
end;
Рассмотрим подробнее части этой процедуры. Параметрами процедуры являются таблица (T), в которой нужно искать элемент, искомое значение ключа (k) и выходной параметр (index), в котором процедура должна указать номер элемента, если он найден, и 0 в противном случае. В списке параметров таблица T описана как параметр переменная, хотя процедура и не должна менять какие-либо данные из таблицы. Это нужно для того, чтобы не создавать копию таблицы в стеке при передаче параметра процедуре, поскольку таблица может иметь большой размер.
Возможен более рациональный вариант: вместо того чтобы всякий раз проверять, не закончился ли массив, можно использовать массив с фиктивным элементом номер 0, перед поиском записывать в него искомое значение ключа, и двигаться по массиву от последнего элемента к первому. Такой способ называется линейным поиском с барьером (барьер — нулевой элемент):
procedure LinearSearch2(var T:tTable; k:tKey; var index:integer);
var i: integer;
begin
T.a[0]:=k;
index:=T.n; index:=0;
while T.a[index]<>k do index:=index-1;
end;
В таком варианте становится значительно меньше сравнений, следовательно, алгоритм работает быстрее предыдущего.
2. Двоичный поиск
Следующий алгоритм также применяется для таблицы, представленной в виде массива, кроме того, массив должен быть отсортированным по значениям ключа (для определённости — по возрастанию). Тогда при поиске можно использовать следующие соображения: возьмём элемент, находящийся в середине массива, если его ключ равен искомому ключу, то мы нашли нужный элемент, если меньше — продолжаем поиск в первой половине массива, если меньше — то во второй. Под продолжением понимаем аналогичный процесс: вновь берём средний элемент из выбранной половины массива, сравниваем его ключ с искомым ключом, и т. д. Этот цикл закончится, когда часть массива, в которой производится поиск, не будет содержать ни одного элемента. Так как этот алгоритм многократно разбивает массив на две части, то он называется алгоритмом двоичного поиска. Ниже приведена соответствующая процедура на Паскале.