"Деревянный" TList

[mutabor]

Нужна реализация самобалансирующегося (красно-черного или АВЛ, не суть важно) дерева на Delphi. Ибо скорость стандартного поиска TList.IndexOf не устраивает никак. Что посоветуете? Желательно что-то готовое, удобное и напоминающее интерфейсом TList, чтобы просто заменить и не вникать долго.

p.s. Кстати, может есть в поставке Delphi такое чудо? В С++ и в Java есть на базе красно-черного дерева структуры данных, может и в Delphi появились?

[Баламут]

Готового класса предложить не могу, к сожалению. Но может это поможет? Там довольно подробно все расписано

[alexBlack]

Может просто TList дописать по аналогии с TStrings. Что-то вроде:

type
   TSortedList = class(TList)
   private
      FSorted : boolean;
      FCompare : TListSortCompare;
   public
      function AddSorted(AObject: TObject): Integer;
      function Find(const AObject: TObject; var Index: Integer): Boolean;
      constructor Create(aCompare: TListSortCompare);
   end;

constructor TSortedList.Create(aCompare: TListSortCompare);
begin
   inherited Create;
   FSorted := true;
   FCompare := aCompare;
end;

function TSortedList.AddSorted(AObject: TObject): Integer;
begin
  if not FSorted then
    Result := Count
  else
    if Find(AObject, Result) then {};
  Insert(Result, AObject);
end;

function TSortedList.Find(const AObject: TObject; var Index: Integer): Boolean;
var
  L, H, I, C: Integer;
begin
  Result := False;
  L := 0;
  H := Count - 1;
  while L <= H do
  begin
    I := (L + H) shr 1;
    C := FCompare(items[I], AObject);
    if C < 0 then L := I + 1 else
    begin
      H := I - 1;
      if C = 0 then
      begin
        Result := True;
        {if Duplicates <> dupAccept then L := I;}
      end;
    end;
  end;
  Index := L;
end;

Весь код из VCL практически без изменений.

function MySort(N1, N2:Pointer):integer;
begin
   if      integer(N1) = integer(N2) then result :=  0
   else if integer(N1) < integer(N2) then result := -1
   else                                   result :=  1
end;

procedure TForm6.FormCreate(Sender: TObject);
var L1:TSortedList;
    i, N:integer;
begin
   L1 := TSortedList.Create(MySort);
   for i := 0 to 1000 do L1.AddSorted(Pointer(Random(10000)));

[mutabor]

Баламут, у меня есть эта книга, но все равно спасибо, может когда нибудь сделаю реализацию TList скоростную, а пока хочется что-то готовое, времени нет на это.

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

Нашел библиотеку для Delphi где есть ассоциативные массивы на базе красно-черного дерева. Прикрутил, работает, то что надо, быстрее раз в 20 стало. Тут >>> есть описание, там и другие библиотеки упоминаются, но я сделал на той, о к-рой статья, там много чего еще в ней есть, практически реализация STL для Delphi.

Во вложении адаптированный для D2009 главный модуль библиотеки (к статье приложена версия адаптированная для D7), еще я там отключил пул, в начале юнита директива, с ним программа вываливалась с исключением. Насчет остальных модулей не знаю, мне они не понадобились, только этот и еще один (mwFixedRecSort.pas), но там без изменений.

[alexBlack]

Не-а, не полный перебор. В Find используется деление списка пополам, как в QuickSort. т.е. теоретически log2(n) операций для поиска.