Lazarus и сбалансированные деревья.

В Lazarus есть встроенные сбалансированные деревья AVL. Модуль AVL_Tree.

Я такие деревья использую в массивах справочниках, когда важна скорость поиска какого то элемента. Конечно когда в справочник 10 или 20 элементов это не так важно, можно применить и линейный поиск. Но когда элементов 100, 1000 или тем более 100000, то вещь совершенно необходимая.

Вот интересная статья на википедии.

На самом деле в Lazarus две реализации деревьев, AvgLvlTree и AVL_Tree. Я решил использовать AVL_Tree, так как они показались мне более быстрыми и низкоуровневыми.

Небольшой пример использования.

type
  TDataItem = class(TObject)
  private
    id: integer;
    content:string;
  end;

  PDataItem = ^TDataItem;
...........................................

// процедура сравнения элементов, тут можно указать любое поле. По этому полю будет сортироваться дерево
function CompareItem(a, b: Pointer): longint;
begin
  Result := PDataItem(a)^.id - PDataItem(b)^.id;
end;

procedure TForm1.Test;
var
  Data: TAVLTree;
  item: TDataItem;
  node: TAVLTreeNode;
begin

  // создание дерева
  Data := TAVLTree.Create(@CompareItem);

  // добавление элемента в дерево
  item := TDataItem.Create;
  item.id := Random(100);
  item.Content := 'тестовая строка';
  Data.Add(Addr(item));      

  // поиск нужного элемента
  item := TDataItem.Create;
  item.id := 4; // укажем тут, что ищем
  node := Data.Find(item); // это поиск
  FreeAndNil(item);

  ShowMessage(PDataItem(node.Data)^.content); // так можно получить доступ к найденному элементу

  // очистка дерева
  node := Data.findLowest;
  while node <> nil do
  begin
    FreeAndNil(PDataItem(node.Data)^);
    node := Data.FindSuccessor(node);
  end;
  FreeAndNil(Data);

end;

Главное помнить, что в дереве хранятся только ссылки на ваши объекты и их потом нужно удалять. Вместо класса можно запихнуть в дерево ссылку на запись.