end
{повысить ранг правого дочернего узла, т.е. выполнить поворот родительского узла влево}
else begin
Parent^.btChild[ctRight] := aNode^.btChild[ctLeft];
if (Parent^.btChild[ctRight]<> nil) then
Parent^.btChild[ctRight]^.btParent := Parent;
aNode^.btParent := Parent^.btParent;
if (aNode^.btParent^.btChild[ctLeft] = Parent) then
aNode^.btParent^.btChild[ctLeft] := anode else
aNode^.btParent^.btChild[ctRight] := aNode;
aNode^.btChild[ctLeft] := Parent;
Parent^.btParent := aNode;
end;
{вернуть узел, ранг которого был повышен}
Result := aNode;
end;
Исходный код класса TtdRedBlackTree можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDBinTre.pas.
В этой главе мы рассмотрели бинарные деревья - важную структуру данных, которая может использоваться во многих прикладных приложениях. Мы рассмотрели стандартное бинарное дерево, а затем перешли к исследованию его сортированной разновидности - дереву бинарного поиска.
В ходе рассмотрения дерева бинарного поиска мы ознакомились с проблемой, которая может возникнуть во время вставки и удаления - проблемой вырождения дерева, - именно в это связи мы исследовали способы ее устранения. Первое решение, скошенное дерево, предоставляет хорошую возможность, несмотря на то, что при этом эффективность вставки и удаления лишь в среднем, а не всегда, описывается соотношением O(log(n)). Однако эта разновидность дерева представляет собой приемлемый компромисс между стандартным деревом бинарного поиска и таким действительно сбалансированным деревом, как красно-черное дерево.
Воспользовавшись красно-черным деревом, мы, наконец, получили полное дерево бинарного поиска, имеющее встроенные алгоритмы балансировки как для вставки, так и для удаления.
В главе 3 мы рассмотрели несколько очень простых структур данных. Одной из них была очередь. В эту структуру можно было добавлять элементы, а затем извлекать их в порядке поступления. При этом сохранение даты и времени создания записи позволяло не обращать внимания на реальную длину элемента в очереди. Вместо этого мы просто организовали элементы по порядку их поступления в связный список или массив, а затем удаляли их в порядке поступления. При этом использовались две базовые операции: "добавление элемента в очередь" (называемая еще постановкой в очередь) и "удаление самого старого элемента очереди" (или вывод из очереди).
Все это замечательно, и очередь сама по себе является важной структурой данных. Однако ей присуще ограничение, заключающееся в том, что элементы обрабатываются в порядке их поступления. Предположим, что элементы нужно обрабатывать в совершенно ином порядке. Иначе говоря, требуется очередь, для которой по-прежнему определена операция "добавления элемента", но второй операцией является не "удаление самого старого элемента", а "удаление самого большого элемента" или "удаление самого малого элемента". В этом случае упрощенный критерий упорядочения "по возрасту" желательно заменить каким-то совершенно иным критерием. Например, предположим, что элементами очереди являются задачи, которые необходимо выполнить, и требуется извлечь задачу, обладающую наивысшим приоритетом.
Фактически, упомянутый пример обусловливает название новой структуры данных, называемой очередью по приоритету. Для очереди по приоритету (priority queue) определены две базовых операции: добавление элемента (как и ранее) и извлечение элемента с наивысшим приоритетом. (Естественно, при этом предполагается, что с каждым элементом связано значение приоритета, которое легко проверить.) у читателей может возникнуть вопрос, что в данном контексте понимается под "приоритетом"? Что ж, приоритетом может быть все что угодно. В классическом понимании это численное значение, указывающее на приоритет элемента в каком-либо процессе. Примерами могут служить очереди на печать в операционных системах, очереди заданий или потоки в многопоточной среде. Если принять в качестве примера очередь печати, каждому заданию печати присваивается приоритет - значение, указывающее важность данного задания печати. Задания на печать с высоким приоритетом должны обрабатываться раньше заданий с низким приоритетом. В этом случае операционная система должна была бы завершить выполнение конкретного задания печати, обратиться к очереди печати и извлечь задание печати с наивысшим приоритетом. По мере выполнения работы в операционной системе, другие задания печати будут добавляться в очередь печати с различными приоритетами, а очередь печати обеспечит такую их организацию, чтобы при необходимости можно было определить печатное задание с наивысшим приоритетом.
Однако следует отметить, что используемое в качестве "приоритета" значение не обязательно должно быть классическим номером приоритета. Оно может иметь любой тип или значение - главное, чтобы значения были связаны отношением упорядочения, и чтобы очередь могла определить элемент с наибольшим значением. {Отношение упорядочения набора объектов - это правило, которое позволяет упорядочить объекты так, чтобы объект X был "меньше" объекта Y. Если X меньше Y, то Y не может быть меньше х. Кроме того, если X меньше Y, и Y меньше Z, то X меньше Z. Обычное упорядочение целых чисел, когда 2 меньше 3 и т.д., представляет собой пример отношения упорядочения.}
Например, значением приоритета могло бы быть имя (иначе говоря, строка), а упорядочением мог бы быть стандартный алфавитный порядок. Таким образом, вместо операции извлечения элемента с наибольшим приоритетом можно было бы использовать извлечение элемента, располагающегося раньше в алфавитном порядке (т.е. все А располагаются перед всеми В и т.д.).
Итак, очередь по приоритету должна обеспечивать (1) хранение произвольного количества элементов, (2) добавление в очередь элемента с определенным приоритетом и (3) выявление и удаление элемента с наивысшим приоритетом.
При разработке очереди по приоритету первый атрибут (возможность хранения произвольного количества элементов) наталкивает на мысль об использовании какой-либо расширяемой структуры данных типа связного списка или расширяемого массива, такого как TList. Мы будем использовать (по крайней мере, пока) TList.
Следующий атрибут (возможность добавления элемента в очередь) легко реализовать в случае применения TList: достаточно вызвать метод Add структуры TList. Мы будем исходить из предположения, что добавляемыми в очередь по приоритету элементами будут каким-то образом описанные объекты, свойством которых является их приоритет. В результате мы получаем Достаточно простой элемент, не отвлекающий наше внимание от функциональных возможностей очереди по приоритету.
Реализация третьего атрибута (возможности отыскания наивысшего приоритета и возвращения связанного с ним объекта с удалением его из обрабатываемой очереди по приоритету) несколько сложнее, но все же сравнительно проста. По существу мы выполняем итерационный просмотр элементов структуры TList, сравнивая приоритет каждого элемента с наибольшим обнаруженным приоритетом. Если приоритет данного элемента больше наибольшего обнаруженного до этого момента приоритета, мы помечаем индекс этого элемента как нового элемента с наибольшим приоритетом и переходим к следующему элементу. Этот поиск является простым последовательным поиском. После проверки всех элементов в структуре TList мы знаем, какой их них является наибольшим (его индекс был запомнен), и просто удаляем его из TList.
Пример кода простой очереди по приоритету приведен в листинге 9.1. В нем используется функция сравнения, которая передается очереди по приоритету при ее создании, и которая сравнивает приоритеты элементов. Таким образом, самой очереди по приоритету не нужно уметь сравнивать приоритеты (и, следовательно, знать, являются ли они числами, строками или чем-либо еще): очередь просто вызывает функцию сравнения, передавая ей два элемента, приоритеты которых требуется сравнить. Обратите также внимание, что очереди не нужно знать, что представляют собой элементы. Она просто хранит их. Поэтому можно просто объявить использование указателей в очереди и при необходимости выполнять приведение типов.
Листинг 9.1. Простая очередь по приоритету, построенная на основе структуры TList type
TtdSimplePriQueuel = class private
FCompare : TtdCompareFunc;
FList : TList;
protected
function pqGetCount : integer;
public
constructor Create(aCompare : TtdCompareFunc);
destructor Destroy; override;
function Dequeue : pointer;
procedure Enqueue(aItem : pointer);
property Count : integer read pqGetCount;
end;
constructor TtdSimplePriQueuel.Create(aCompare : TdCompareFunc);
begin
inherited Create;
FCompare := aCompare;
FList := TList.Create;
end;