Бинарным сбалансированным деревом я буду называть дерево, в котором для каждого узла количество узлов справа отличается от количества узлов слева не более чем на единицу.
Дерево будем делать для списка строк (
TStrings), а сама сортировка будет производиться в специальном массиве, где каждый элемент будет хранить номера вершин левого и правого поддеревьев. Элемент массива с некоторым индексом будет соответствовать строке с тем же индексом. Сразу распишу все структуры, чтобы к ним потом не возвращаться.
PNode = ^TNode;
TNode = record
Left,Right : Integer;
ID : Integer;
end;
TNodes = array[0..High(integer) div SizeOf(TNode)-1] of TNode;
PNodes = ^TNodes;
По поводу
ID скажу в заключении, а на данный момент там будет храниться индекс элемента в массиве. Для хранения списка узлов делаем вот такой класс:
TNodeList = class(TList)
private
function GetNode(Index: Integer): PNode;
public
property Nodes[Index : Integer]: PNode read GetNode; default;
end;
function TNodeList.GetNode(Index: Integer): PNode;
begin
Result := PNode(inherited Items[Index]);
end;
Основная идея заключается в подсчете для каждого узла количества узлов в правом и левом поддереве. Функция составления дерева будет рекурсивной. Ей на вход будем подавать текущее множество узлов, а возвращать она будет индекс вершины построенного дерева. Следовательно, сразу создадим начальный список узлов, в который включаем все узлы.
L := TNodeList.Create;
for i:=0 to Texts.Count-1 do
begin
Nodes[i].Left := 0;
Nodes[i].Right := 0;
Nodes[i].ID := i;
L.Add(@Nodes[i]);
end;
for i:=0 to Texts.Count-1 do
for j:=i+1 to Texts.Count-1 do
if Texts[i]<Texts[j] then
begin
Inc(Nodes[i].Right);
Inc(Nodes[j].Left);
end
else
begin
Inc(Nodes[i].Left);
Inc(Nodes[j].Right);
end;
Теперь сама функция. Подсчетом узлов слева и справа мы произвели неявную сортировку. Это значит, что по значению поля
Left для двух узлов можно судить о результате сравнения соответствующих строк. Значит, найдя в текущем списке вершину дерева (
abs(node.left-node.right)<=1) мы можем смело сбросить в левое поддерево все узлы, у которых поле
Left будет содержать меньшее значение, чем у найденной вершины. Так как данное утверждение верно и для поля
Right, то чтобы вычислить для каждого узла левого поддерева новое количество узлов справа, достаточно из поля
Right вычесть значение
Right найденной вершины плюс единицу (так как найденная вершина также справа). Остается в поля
Left и
Right найденной вершины положить то, что и должно там лежать: вершины левого и правого поддерева. Ну, здесь просто рекурсия.
function Sub(List: TNodeList) : Integer;
var i,main : Integer;
L,R : TNodeList;
Begin
//если список пуст, возвращаем отсутствующий индекс
if List.Count=0 then begin Result := -1; exit end;
main := 0;
//находим индекс вершины
for i:=0 to List.Count-1 do
if abs(List[i].Left-List[i].Right)<2 then
begin
main := List[i].ID;
break;
end;
//формируем списки узлов левого и правого поддерева
L := TNodeList.Create;
R := TNodeList.Create;
try
for i:=0 to List.Count-1 do
if main<>List[i].ID then
if List[i].Left<Nodes[main].Left then
begin
L.Add(List[i]);
Dec(List[i].Right,Nodes[main].Right+1);
end
else
begin
R.Add(List[i]);
Dec(List[i].Left,Nodes[main].Left+1);
end;
//возвращаем индекс вершины
Result := main;
//создаем поддеревья
Nodes[main].Left := Sub(L);
Nodes[main].Right := Sub(R);
finally
L.Free;
R.Free;
end;
end;
Заключение Хочется сказать про поле
ID. От него можно избавиться, если передавать в функцию не список ссылок на узлы, а список их номеров. Я пошел по пути добавления этого поля, чтобы получить более наглядный код. Согласитесь, что строчка
List[i].ID
выглядит значительно лучше, чем
Nodes[List[i]].ID
)