Учебно-методическое пособие "Методы сортировок и поиска" Редакция №1 от 28. 08. 2013 г

«Системное программное обеспечение»

для специальности 5В070200 -

«Автоматизация и управление»

Семей

В этой части книги будут обсуждаться структуры данных в основной памяти и методы их использования, предназначенные для поиска данных в соответствии со значениями их ключей. Эта задача является не менее распространенной в программировании, чем внутренняя сортировка данных.

Главным образом, распространены два подхода - поиск в динамических древовидных структурах и поиск в таблицах на основе хэширования. Рассмотрению разновидностей этих подходов и посвящены следующие два раздела.

Заметим, что мы намеренно выделили в отдельную часть структуры данных и методы поиска данных во внешней памяти. Несмотря на использование того же набора терминов (деревья и хэширование) поиск во внешней памяти и критерии оценки эффективности алгоритмов существенно отличаются от тех, которые применимы в случае расположения данных в основной памяти.

Методы поиска в основной памяти на основе деревьев

Понятия, связанные с деревьями, широко известны и интуитивно понятны. Тем не менее, для однозначного понимания содержимого этого раздела (и соответствующего раздела следующей части курса) мы приведем несколько не слишком формальных определений и примеров.

Существует несколько возможных определений дерева. Например, с точки зрения теории графов деревом часто называют неориентированный граф с выделенной вершиной (корнем), который не содержит циклов. Нас будут интересовать не произвольные графы, а только ориентированные деревья, причем с точки зрения программистов. Поэтому мы используем следующее рекурсивное определение: дерево R с базовым типом T - это либо (a) пустое дерево (не содержащее ни одной вершины), либо (b) некоторая вершина типа T (корень дерева) с конечным (возможно, нулевым) числом связанных с ней деревьев с базовым типом T (эти деревья называются поддеревьями дерева R). Из этого определения, в частности, следует, что однонаправленный список (рисунок 4.1) является деревом.


Рис.1.

Деревья можно представлять по-разному (это всего лишь однородная иерархическая структура). Например, на рисунках 4.1 и 4.2 показаны два разных способа представления одного и того же дерева, у которого базовый тип содержит множество букв латинского алфавита. Сразу заметим, что графовое представление на рисунке 4.2 больше соответствует специфике программирования.

Придерживаясь естественной для графового представления терминологии, мы будем называть связи между поддеревьями ветвями, а корень каждого поддерева - вершиной. Упорядоченным деревом называется такое, у которого ветви, исходящие из каждой вершины, упорядочены. Например, два упорядоченных дерева на рисунке 4.3 различаются.

По определению, корень дерева находится на уровне 0, а все вершины дерева, непосредственно связанные с вершиной уровня i, находятся на уровне i+1. Вершина x уровня i, непосредственно связанная с вершиной y уровня i+1, называется непосредственным предком (или родителем) вершины y. Такая вершина y соответственно называется непосредственным потомком (или сыном) вершины x. Вершина без непосредственных потомков называется листовой (или терминальной), нелистовые вершины называются внутренними. Под степенью внутренней вершины понимается число ее непосредственных потомков. Если все вершины имеют одну и ту же степень, то она полагается степенью дерева. На самом деле, всегда можно добиться того, чтобы любая вершина дерева имела одну и ту же степень путем добавления специальных вершин в тех точках, где отсутствуют поддеревья (рисунок 4.4).

Число вершин (или ветвей), которые нужно пройти от корня к вершине x, называется длиной пути к вершине x. Высотой (или глубиной) дерева будем называть максимальную длину его вершины.


Лекция № 2 Сортировка с помощью прямого включения

Для организации поиска в основной памяти особое значение имеют упорядоченные двоичные (бинарные) деревья (как, например, на рисунке 4.3). В каждом таком дереве естественно определяются левое и правое поддеревья. Двоичное дерево называется идеально сбалансированным, если число вершин в его левом и правом поддеревьях отличается не более, чем на 1 (легко видеть, что при соблюдении этого условия длины пути до любой листовой вершины дерева отличаются не больше, чем на 1). Примеры идеально сбалансированных деревьев показаны на рисунке 4.5.

Двоичные деревья обычно представляются как динамические структуры с базовым типом записи T, в число полей которого входят два указателя на переменные типа T.

При использовании в целях поиска элементов данных по значению уникального ключа применяются двоичные деревья поиска, обладающие тем свойством, что для любой вершины дерева значение ее ключа больше значения ключа любой вершины ее левого поддерева и больше значения ключа любой вершины правого поддерева (рисунок 4.6). Для поиска заданного ключа в дереве поиска достаточно пройти по одному пути от корня до (возможно, листовой) вершины (рисунок 4.7). Высота идеально сбалансированного двоичного дерева с n вершинами составляет не более, чем log n (логарифм двоичный), поэтому при применении таких деревьев в качестве деревьев поиска (рисунок 4.8) потребуется не более log n сравнений.


Рис. 6. Путь поиска ключа по значению “23”


Рис. 7. Идеально сбалансированное двоичное дерево

Применение деревьев как объектов с динамической структурой особенно полезно, если допускать выполнение не только операции поиска по значению ключа, но и операций включения новых и исключения существующих ключей. Если не принимать во внимание потенциальное желание поддерживать идеальную балансировку дерева, то процедуры включения и исключения ключей очень просты. Для включения в дерево вершины с новым ключом x по общим правилам поиска ищется листовая вершина, в которой находился бы этот ключ, если бы он входил в дерево. Возможны две ситуации: (a) такая вершина не существует; (b) вершина существует и уже занята, т.е. содержит некоторый ключ y. В первой ситуации создается недостающая вершина, и в нее заносится значение ключа x. Во второй ситуации после включения ключа x эта вершина в любом случае становится внутренней, причем если x > y, то ключ x заносится в новую листовую вершину - правого сына y, а если x


(a)


(b)


(c)


(d)


(e)
Рис. 8.

При выполнении исключения ключа из дерева также прежде всего выполняется поиск ключа. Если ключ обнаруживается, то возможны следующие случаи: (a) ключ содержится в листовой вершине, у вершины-отца которой имеются два сына; (b) ключ содержится в листовой вершине, являющей единственным сыном своего отца; (c) ключ содержится во внутренней вершине, имеющей только левого или только правого сына; (d) ключ содержится во внутренней вершине, имеющей и левого, и правого сыновей. В случае (a) соответствующая листовая вершина ликвидируется, а у ее отца остается только один сын. В случае (b) листовая вершина ликвидируется, а ее отец становится новой листовой вершиной. В случае (c) внутренняя вершина ликвидируется, и ее место занимает единственный сын (он может быть внутренней или листовой вершиной. В случае (d) внутренняя вершина ликвидируется, и заменяется на листовую или внутреннюю вершину, достигаемую по самому правому пути от левого сына внутренней вершины. Эта вершина наследует левого и правого сыновей ликвидируемой вершины. Возможные варианты иллюстрируются на рисунке 4.10.

Поддержка дерева поиска в идеально сбалансированном состоянии требует существенного усложнения (с соответствующим увеличением накладных расходов) операций включения и исключения ключей. Кроме того, как показано в книге Вирта, при равномерном распределении значений включаемых и исключаемых ключей использование идеально сбалансированных деревьев поиска дает выигрыш не более 30% (имеется в виду число сравнений, требующихся при поиске). Поэтому на практике идеально сбалансированные деревья поиска используются крайне редко.

Как видно из содержимого предыдущего подраздела, идеально сбалансированные деревья представляют, в большей степени, чисто теоретический интерес, поскольку поддержание идеальной сбалансированности требует слишком больших накладных расходов. В 1962 г. советские математики Адельсон-Вельский и Ландис предложили менее строгое определение сбалансированности деревьев, которое в достаточной степени обеспечивает возможности использования сбалансированных деревьев при существенно меньших расходах на поддержание сбалансированности. Такие деревья принято называть АВЛ-деревьями (в соответствии с именами их первооткрывателей).

По определению, двоичное дерево называется сбалансированным (или АВЛ) деревом в том и только в том случае, когда высоты двух поддеревьев каждой из вершин дерева отличаются не более, чем на единицу. При использовании деревьев, соответствующих этому определению, обеспечивается простая процедура балансировки при том, что средняя длина поиска составляет O(log n), т.е. практически не отличается от длины поиска в идеально сбалансированных деревьях. Как доказали Адельсон-Вельский и Ландис, АВЛ-дерево никогда не превышает по глубине аналогичное сбалансированное дерево больше, чем на 45%.

Чтобы понять, как устроены "самые плохие" АВЛ-деревья, попробуем построить сбалансированное дерево с высотой h, содержащее минимальное число вершин. Обозначим такое дерево через Th. Понятно, что T0 - это пустое дерево, а T1 - дерево с одной вершиной. Дерево Th строится путем добавления к корню двух поддеревьев типа T(h-1). Одно из таких поддеревьев должно иметь высоту h-1, а другое может иметь глубину h-2. Такие "плохо" сбалансированные деревья называются деревьями Фибоначчи (поскольку принцип их построения напоминает принцип построения чисел Фибоначчи) и определяются рекурсивно следующим образом:

• 
  (a) пустое дерево есть дерево Фибоначчи высоты 0;
  
• 
  (b) единственная вершина есть дерево Фибоначчи высоты 1;
  
• 
  (c) если T(h-1) и T(h-2) являются деревьями Фибоначчи высотой h-1 и h-2 соответственно, а x - новый корень дерева, то Th = есть дерево Фибоначчи высотой h;
  
• 
  (d) другие деревья Фибоначчи не существуют.
  

Число вершин в дереве Th определяется из следующего рекуррентного соотношения:

N0 = 0; N1 = 1; Nh = N(h-1) +1 + N(h-2)

Эти числа определяют число вершин в АВЛ-дереве в худшем случае и называются "числами Леонарда". Заметим, что из этого соотношения следует, что длина пути от корня любого листа в АВЛ-дереве может отличаться не более, чем на единицу.

• 
  (a) если hl = hr, то после добавления вершины L и R станут разной высоты, но свойство сбалансированности сохранится;
  
• 
  (b) если hl
• 
  (c) если hl > hr, то после включения ключа критерий сбалансированности нарушится, и потребуется перестройка дерева.
  

Как кажется, в данном случае рисунки лучше проясняют суть явления, чем текст и тем более компьютерная программа. Действия, которые требуются для балансировки, авторы механизма назвали "поворотами". Действительно, если внимательно посмотреть на то, что происходит с деревом, это действительно напоминает его повороты относительно выбранной вершины.

При исключении вершин из АВЛ-дерева также возможна его не слишком сложная балансировка. Мы не будем приводить описание требующихся процедур, а проиллюстрируем их на нескольких последовательных примерах (рисунок 4.14).


(a)


(b)


(c)


(d)


(e)


(f)


(g)
Рис. 13.

Известно, что оценкой стоимости поиска в АВЛ-дереве, а также выполнения операций включения и исключения ключей является O(log n), т.е. эти деревья при поиске ведут себя почти так же хорошо, как и идеально сбалансированные деревья, а поддержка балансировки при включениях и исключениях обходится гораздо дешевле.

Лекция № 4 Сортировка с помощью прямого обмена (метод пузырька)

Пусть дерево поиска содержит n вершин, и обозначим через pi вероятность обращения к i-той вершине, содержащей ключ ki. Сумма всех pi, естественно, равна 1. Постараемся теперь организовать дерево поиска таким образом, чтобы обеспечить минимальность общего числа шагов поиска, подсчитанного для достаточно большого количества обращений. Будем считать, что корень дерева имеет высоту 1 (а не 0, как раньше), и определим взвешенную длину пути дерева как сумму pi*hi (1

В качестве примера рассмотрим возможности построения дерева поиска для трех ключей 1, 2, 3 с вероятностями обращения к ним 1/7, 2/7 и 4/7 соответственно (рисунок 4.15).

Посчитаем взвешенную длину пути для каждого случая. В случае (a) взвешенная длина пути P(a) = 1*4/7 + 2*2/7 + 3*1/7 = 11/7. Аналогичные подсчеты дают результаты P(b)=12/7; P(c)=12/7; P(d)=15/7; P(e)=17/7. Следовательно, оптимальным в интересующем нас смысле оказалось не идеально сбалансированное дерево (c), а вырожденное дерево (a).

На практике приходится решать несколько более общую задачу, а именно, при построении дерева учитывать вероятности неудачного поиска, т.е. поиска ключа, не включенного в дерево. В частности, при реализации сканера желательно уметь эффективно распознавать идентификаторы, которые не являются ключевыми словами. Можно считать, что поиск по ключу, отсутствующему в дереве, приводит к обращению к "специальной" вершине, включенной между реальными вершинами с меньшим и большим значениями ключа соответственно. Если известна вероятность qj обращения к специальной j-той вершине, то к общей средней взвешенной длине пути дерева необходимо добавить сумму qj*ej для всех специальных вершин, где ej - высота j-той специальной вершины.


(a)


(b)


(c)


(d)


(e)
Рис. 14.

При построении дерева оптимального поиска вместо значений pi и qj обычно используют полученные статистически значения числа обращений к соответствующим вершинам. Процедура построения дерева оптимального поиска достаточно сложна и опирается на тот факт, что любое поддерево дерева оптимального поиска также обладает свойством оптимальности. Поэтому известный алгоритм строит дерево "снизу-вверх", т.е. от листьев к корню. Сложность этого алгоритма и расходы по памяти составляют O(n2). Имеется эвристический алгоритм, дающий дерево, близкое к оптимальному, со сложностью O(n*log n) и расходами памяти - O(n).

Деревья цифрового поиска

Методы цифрового поиска достаточно громоздки и плохо иллюстрируются. Поэтому мы кратко остановимся на наиболее простом механизме - бинарном дереве цифрового поиска. Как и в деревьях, обсуждавшихся в предыдущих разделах, в каждой вершине такого дерева хранится полный ключ, но переход по левой или правой ветви происходит не путем сравнения ключа-аргумента со значением ключа, хранящегося в вершине, а на основе значения очередного бита аргумента.

Поиск начинается от корня дерева. Если содержащийся в корневой вершине ключ не совпадает с аргументом поиска, то анализируется самый левый бит аргумента. Если он равен 0, происходит переход по левой ветви, если 1 - по правой. Если не обнаруживается совпадение ключа с аргументом поиска, то анализируется следующий бит аргумента и т.д., пока либо не будут проверены все биты аргумента, или мы не наткнемся на вершину с отсутствующей левой или правой ссылкой.

На рисунке 4.16 показан пример дерева цифрового поиска для некоторых заглавных букв латинского алфавита. Считается, что буквы кодируются в соответствии с кодовым набором ASCII, а для их представления и поиска используются 5 младших бит кода. Например, код буквы A равен 41(16), а представляться A будет как последовательность бит 00001.