Digs - Персональная территория

Авторский проект Артема Глазкова
? 
        Версия для печати (цвет)  

Использование материалов
Заметка #26
15 июля 2007

Сбалансированное дерево


    Бинарным сбалансированным деревом я буду называть дерево, в котором для каждого узла количество узлов справа отличается от количества узлов слева не более чем на единицу.
    Дерево будем делать для списка строк (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


© 2005-16, Powered By Digs (Написать письмо, vk)