Добавить комментарий

Delphi

Сортировка деревом

Будем вставлять элементы в двоичное дерево. Для получения результата достаточно будет обойти получившееся дерево в глубину.

Код на Delphi:

type
  TAI = array of integer;

  TNode = class
            private
              Fkey : integer; // Собственный ключ узла
              FLeft, FRight: TNode; // Правое и левое поддеревья.
            public
              property Key: integer read FKey write FKey;

              constructor Create(aKey: Integer);
              procedure Insert(aNode: TNode); // Добавление узла в дерево
              procedure Extract(var A: TAI); // Извлечение дерева обратно в массив.
              destructor Destroy;override;
          end;
...

{ TNode }

constructor TNode.Create(aKey: Integer);
begin
  FKey := akey;
end;

destructor TNode.Destroy;
begin
  FLeft.Free;
  FRight.Free;
  inherited;
end;

procedure TNode.Extract(var A: TAI);
begin
  // Сначала извлекаем левое поддерево,
  if Assigned(FLeft) then FLeft.Extract(A);
  // потом свой ключ,
  SetLength(A, Length(A) +1);
  A[Length(A)-1] := FKey;
  // и правое поддерево.
  if Assigned(FRight) then FRight.Extract(A);
end;

procedure TNode.Insert(aNode: TNode);
begin
  if aNode.Key < Key then
  begin // Меньшие ключи добавляем в левое поддерево,
    if Assigned(FLeft) then FLeft.Insert(aNode)
                       else FLeft := aNode;
  end
    else
  begin // остальные - в правое.
    if Assigned(FRight) then FRight.Insert(aNode)
                        else FRight := aNode;
  end;
end;

...

procedure BTreeSort(var A: TAI);
var
    Tree: TNode;
    i:integer;
begin
  if length(A)>1 then
  begin
    // Начинаем дерево первым элементом
    Tree := TNode.Create(A[Low(A)]);
    // и вставляем в него все остальные.
    for i := Low(A)+1 to High(A) do
    begin
      Tree.Insert(TNode.Create(A[i]));
    end;
    // Дерево сформировано. Сбрасываем массив.
    Setlength(A,0);
    // Извлекаем результат обратно в массив.
    Tree.Extract(A);
    // Освобождаем память из под дерева.
    Tree.Free;
  end;
end;

 

Сложность:

Максимальная O(N2)
Минимальная O(N(logN))
Средняя O(N(logN))

 

Filtered HTML

  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Допустимые HTML-теги: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Строки и абзацы переносятся автоматически.
  • Вы можете цитировать другие сообщения, используя тэг [quote]

Plain text

  • HTML-теги не обрабатываются и показываются как обычный текст
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и абзацы переносятся автоматически.