Алгоритмы и структуры данных

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

Рассмотрим такие преобразования.

 

Пусть вершина а имеет правый потомок b. Обозначим через P левое поддерево вершины а, через Q и R - левое и правое поддеревья вершины b. Упорядоченность дерева требует, чтобы P < а < Q < b < R. Точно того же требует упорядоченность дерева с корнем b, его левым потомком а, в котором P и Q - левое и правое поддеревья а, R - правое поддерево b. Поэтому первое дерево можно преобразовать во второе, не нарушая упорядоченности. Такое преобразование называется малым правым вращением (рис. 33). Аналогично определяется симметричное ему малое левое вращение.

Рис. 33. Малое правое вращение сбалансированного дерева

Пусть b - правый потомок а, c - левый потомок b, P - левое поддерево а, Q и R - левое и правое поддеревья c, S - правое поддерево b. Тогда P < а < Q < c < R < b < S. Такой же порядок соответствует дереву с корнем c, имеющим левый потомок а и правый потомок b, для которых P и Q -поддеревья вершины а, а R и S - поддеревья вершины b. Соответствующее преобразование будем называть большим правым вращением (рис. 34). Аналогично определяется симметричное ему большое левое вращение.

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

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

type

PTree = ATTree; TTree = record

Data: TypeElement;      {поле данных}

Left, Right: PTree;    {указатели на левое и правое поддеревья}

Balance: integer;        {показатель сбалансированности} end;

В сбалансированном дереве показатели сбалансированности всех вершин лежат в пределах от -1 до 1. При операциях добавления/удаления могут появляться вершины с показателями сбалансированности -2 и 2:

procedure TreeBalance(a:  PTree; var CurBalance:  integer);

{Балансировка двоичного дерева}

procedure SmallRightRotation(a: PTree);

{малое правое вращение поддерева с корнем a}

var

b: PTree;

val a, val b: TypeElement; h P, h Q, h R: integer; begin

b := aA.Right;    {b <> null}

val a := aA.Data; val b := bA.Data;

h_Q := 0;

h R := bA.Balance;

h_P := (max(h_Q, h_R) + 1)- aA.Balance; aA.Data := val b;   bA.Data := val a; aA.Right := bA.Right;    {поддерево R} bA.Right := bA.Left;      {поддерево Q} bA.Left    := aA.Left;      {поддерево P} aA.Left := b; bA.Balance := h_Q - h_P; aA.Balance := h_R -  (max(h_P, h_Q) + 1);

end;

procedure BigRightRotation(a: PTree); {большое правое вращение поддерева с корнем a} var

b, c: PTree;

val a, val b, val c: TypeElement; h_P, h_Q, h_R, h_S: integer; begin

b := aA.Right;    c := bA.Left;    {b <> null,c <> null}

val a := aA.Data;   val b := bA.Data;   val c := cA.Data;

h_Q := 0;   h_R := cA.Balance;

h_S := (max(h_Q, h_R)  + 1) + bA.Balance;

h P := 1 + max (h S, h S-bA.Balance) - aA.Balance;

aA.Data := val c;    cA.Data := val a;

bA.Left    := cA.Right;    {поддерево R}

cA.Right := cA.Left;      {поддерево Q}

cA.Left    := aA.Left;      {поддерево P}

aA.Left := c;

bA.Balance := h_S - h_R;

cA.Balance := h_Q - h_P;

aA.Balance := max(h S, h R) - max(h P, h Q); end;

begin   {-2 <= aA.Balance <= 2} if aA.Balance = 2 then begin b := aA.Right;

if bA.Balance = -1 then begin

BigRightRotation(a);    CurBalance := -1; end else begin

if bA.Balance = 0 then begin

SmallRightRotation(a);    CurBalance := 0; end else begin   {bA.Balance = 1}

SmallRightRotation(a);    CurBalance := - 1; end; end; end else begin

if aA.Balance = -2 then begin b := aA.Left;

if bA.Balance = 1 then begin

BigLeftRotation(a);    CurBalance := -1;

end else begin

if bA.Balance = 0 then begin

SmallLeftRotation(a);    CurBalance := 0; end else begin {bA.Balance = -1}

SmallLeftRotation(a);    CurBalance := - 1; end; end;

end else begin {-2 < aA.Balance < 2, ничего делать не надо}

CurBalance := 0; end; end; end;

Схематично алгоритм добавления нового элемента в сбалансированное дерево будет состоять из следующих трех основных шагов:

1) поиск по дереву.

2) вставка элемента в место, где закончился поиск, если элемент 
отсутствует.

3) восстановление сбалансированности.

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

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

Алгоритм удаления элемента из сбалансированного дерева будет выглядеть так:

1. поиск по дереву.
2. удаление элемента из дерева.
3. восстановление сбалансированности дерева (обратный проход).

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

Третий шаг представляет собой обратный проход от места, из которого взят элемент для замены удаляемого, или от места, из которого удален элемент, если в замене не было необходимости.

Операция удаления может потребовать перебалансировки всех вершин вдоль обратного пути к корню дерева, т. е. порядка log n вершин.

Таким образом, алгоритмы поиска, добавления и удаления элементов в сбалансированном дереве имеют сложность, пропорциональную O(log n).

Г. М. Адельсон-Вельский и Е. М. Ландис доказали теорему, согласно которой высота сбалансированного дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%.

2.3.5. Поиск в тексте

Часто приходится сталкиваться со специфическим поиском, так называемым поиском слова. Его можно определить следующим образом. Пусть задан массив Txt из N элементов, называемый текстом и массив Wrd из M элементов, называемый словом, причем 0 < M < N. Описать их можно как строки.

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

2.3.5.1. Прямой поиск

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

Данный алгоритм заключается в посимвольном сравнении текста со словом. В начальный момент происходит сравнение первого символа текста с первым символом слова, второго символа текста со вторым символом слова и т. д. Если произошло совпадение всех символов, то фиксируется факт нахождения слова. В противном случае производится «сдвиг» слова на одну позицию вправо и повторяется посимвольное сравнение, т. е. сравнивается второй символ текста с первым символом слова, третий символ текста со вторым символом слова и т. д. (рис. 35). Эти «сдвиги» слова повторяются до тех пор, пока конец слова не достиг конца текста или не произошло полное совпадение символов слова с текстом (т. е. слово найдено):

function DirectTxtSearch(var Wrd:  TWrd;

var Txt: TText;

var Position: integer): boolean; {Функция поиска слова Wrd в тексте Txt,} {если слово найдено,  то возвращает значение true} {и позицию Position начала первого слова Wrd,} {иначе - false и Position не изменяется}

var

i, {Индекс начала слова в тексте}

j: integer;        {Индекс текущего символа слова} begin i := 0; repeat

j  := 1;    i := i + 1;

{Осуществляем посимвольное сравнение} while  (j <= M) and

(Txt[i+j-1] = Wrd[j])  do

j := j+1;

until  (j = M+1)  or    {Совпало все слово}

(i >= N-M+1);    {Конец слова за концом текста} {Оценка результатов поиска} if j = M+1 then begin

DirectTxtSearch := true;

Position := i; end else begin

DirectTxtSearch := false; end; end;

Рис. 35. Алгоритм прямого поиска в тексте

Этот алгоритм работает достаточно эффективно, если допустить, что несовпадение пары символов происходит после незначительного коли-

 

чества сравнений во внутреннем цикле. При достаточно большом множестве символов это довольно частый случай. Можно предполагать, что для текстов, составленных из 128 символов, несовпадение будет обнаруживаться после одной или двух проверок. Тем не менее, в худшем случае алгоритм будет малоэффективен, так как его сложность будет пропорциональна O((N - M)-M).

2.3.5.2. Алгоритм Кнута, Мориса и Пратта

Приблизительно в 1970 году Д. Кнут, Д. Морис и В. Пратт изобрели алгоритм (КМП-алгоритм), фактически требующий только O(N) сравнений даже в самом плохом случае. Новый алгоритм основывается на том соображении, что после частичного совпадения начальной части слова с соответствующими символами текста фактически известна пройденная часть текста и можно «вычислить» некоторые сведения (на основе самого слова), с помощью которых затем быстро продвинуться по тексту.

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

Если j определяет позицию в слове, содержащую первый несовпадающий символ (как в алгоритме прямого поиска), то величина сдвига Shift определяется как j - LenSuff - 1. Значение LenSuff определяется как размер самой длинной последовательности символов слова, непосредственно предшествующих позиции j (суффикс), которая полностью совпадает с началом слова. LenSuff зависит только от слова и не зависит от текста. Для каждого j будет своя величина Shift, которую обозначим Shift.

Приведенный на рис. 36 пример поиска слова ABCABD показывает принцип работы такого алгоритма. Символы, подвергшиеся сравнению, здесь подчеркнуты. Обратите внимание: при каждом несовпадении пары символов слово сдвигается на переменную величину, и меньшие сдвиги не могут привести к полному совпадению.

Так как величины Shifty зависят только от слова, то перед началом фактического поиска можно вычислить вспомогательную таблицу Shift; эти вычисления сводятся к некоторой предтрансляции слова. Соответствующие усилия будут оправданными, если размер текста значительно превышает размер слова (M<<N). Если нужно искать многие вхождения одного и того же слова, то можно пользоваться одной и той же Shift. Приведенные на рис. 37 примеры объясняют назначение Shift.

Следующая функция на языке Паскаль демонстрирует КМП-алго-ритм:

function KMPTxtSearch(var Wrd:  TWrd;

var Txt: TTxt;

var Position: integer): boolean; {Функция поиска слова Wrd в тексте Txt,} {если слово найдено, то возвращает значение true} {и позицию Position начала первого слова Wrd,}

{иначе - false и Position не изменяется} var

i, {Индекс начала слова в тексте}

j, {Индекс текущ.символа слова}

k, {Индекс текущ.символа суффикса слова}

LenSuff: integer;  {Длина суффикса}

Equal: boolean; {Признак совпадения суффикса с началом} 
Shift: array[1..M] of integer; {Массив смещений}

begin

{Заполнение массива Shift}

Shift[1]   := 1; Shift[2]   := 1;    {Для первых двух смещение 1} {Вычисляем смещение для остальных M-2 символов слова} for j  := 3 to M do begin

Shift[j]   := 1;      {Предопределенное значение} {Перебираем все возможные длины суффиксов} for LenSuff := 1 to j-2 do begin Equal:=true;

{Сравниваем посимвольно суффикс с началом слова} for k := 1 to LenSuff do begin

if Wrd[k] <>

Wrd[j-LenSuff+k-1]

then Equal:=false; end;

{Если суффикс совпал, то Shift - это смещение от начала слова до начала суффикса} if Equal then

Shift[j] := j - LenSuff - 1;

end; end;

{Поиск слова Wrd в тексте Txt, аналогичный прямому, только смещение не на 1, а на переменный шаг Shift} i := 0;    j  := 1;      {Начальные значения} repeat

{Смещение слова}

i := i + Shift[j]; j := 1;

{Посимвольное сравнение} while (j <= M) and

(Txt[i+j-1] = Wrd[j]) do

j := j+1;

until (j = M+1) or (i >= N-M+1);

{Оценка результатов поиска} if j = M+1 then begin

KMPTxtSearch := true;

Position := i; end else begin

KMPTxtSearch := false;

end; end;

Точный анализ КМП-алгоритма весьма сложен. Его изобретатели доказывают, что требуется порядка O(M + N) сравнений символов, что значительно лучше, чем O((N - M)-M) сравнений при прямом поиске.

2.3.5.3. Алгоритм Боуера и Мура

КМП-алгоритм дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае слово сдвигается более чем на единицу. К несчастью, это скорее исключение, чем правило: совпадения встречаются значительно реже, чем несовпадения. Поэтому выигрыш от использования КМП-алгоритма в большинстве случаев поиска в обычных текстах весьма незначителен. Метод же, предложенный Р. Боуером и Д. Муром в 1975 году (БМ-алго-ритм), не только улучшает обработку самого плохого случая, но дает выигрыш в промежуточных ситуациях.

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

Далее приводится функция на языке Паскаль с упрощенным БМ-алгорит-мом, построенная так же, как и предыдущая программа с КМП-алгоритмом:

function BMTxtSearch(var Wrd:  TWrd;

var Txt: TText;

var Position: integer): boolean; {Функция поиска слова Wrd в тексте Txt,} {если слово найдено, то возвращает значение true} {и позицию Position начала первого слова Wrd,} {иначе - false и Position не изменяется} var

i, {Индекс начала слова в тексте}

j: integer;       {Индекс текущего символа слова} ch: char;

Shift: arrayH \.'я'] of integer;       {Массив смещений} begin

{Заполнение массива Shift}

for ch:='  ^Л to ^Ля' do Shift[ch]  := MI;

for j:=1 to M do Shift[Wrd[j]] := M-j;

{Поиск слова Wrd в тексте Txt}

i := 1;       {Начало слова совпадает с началом текста} repeat

j := M+1;    {Сравнивать будем с последнего символа} {Посимвольное сравнение слова, начиная с правого символа} repeat