Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Object-Pascal / Delphi-Language (https://www.delphipraxis.net/32-object-pascal-delphi-language/)
-   -   Delphi AA tree - Skew und Split (https://www.delphipraxis.net/81833-aa-tree-skew-und-split.html)

sk.Silvia 4. Dez 2006 17:41


AA tree - Skew und Split
 
cau, hat jemand von euch ein delphi source von Skew and Split?
konnte kein delphi source finden:(( und mein funkcionier nicht so gut...

Delphi-Quellcode:
   
    procedure TAA.Split;
    var tmp : TAA; begin
        tmp := TAA.CreateAATree(0);
        if ( not(Self = nil) and not(RightNode.isEmpty) and not(RightNode.RightNode.isEmpty)) then
            if(RightNode.RightNode.HeaderInfo.DepthLevel = HeaderInfo.DepthLevel) then begin
                tmp := RightNode;  //sem to nechce vojst
                RightNode := tmp.LeftNode;
                tmp.LeftNode := Self;
                Self := tmp;
                inc(Self.HeaderInfo.DepthLevel);
            end;
    end;

    procedure TAA.Skew;
    var tmp : TAA; begin
        tmp := TAA.CreateAATree(0);
        if ( not(Self = nil) and not(LeftNode = nil)) then
            if (LeftNode.HeaderInfo.DepthLevel = HeaderInfo.DepthLevel) then begin
                tmp := RightNode;
                LeftNode := tmp.RightNode;
                tmp.RightNode := Self;
                Self := tmp; //sem to nechce vojst
            end;
    end;
Dankeschon:)

marabu 4. Dez 2006 19:01

Re: AA tree - Skew und Split
 
Hallo Silvia,

dein Deutsch wird immer besser.

Der folgende Code ist meine Portierung des Arne Anderson Tree von Nic Roets - ausschnittsweise und ungetestet.

Delphi-Quellcode:
type
  PAATreeNode = ^TAATreeNode;
  TAATreeNode = record
    Parent, Left, Right: PAATreeNode;
    Level: Integer;
    Data: Integer;
  end;

procedure Skew(oldParent: PAATreeNode);
var
  node: PAATreeNode;
begin
  node := oldParent.Left;
  if oldParent.Parent.Left = oldParent
    then oldParent.Parent.Left := node
    else oldParent.Parent.Right := node;
  node.Parent := oldParent.Parent;
  oldParent.Parent := node;
  oldParent.Left := node.Right;
  if Assigned(oldParent.Left) then
    oldParent.Left.Parent := oldParent;
  node.Right := oldParent;
  if Assigned(oldParent.Left)
    then oldParent.Level := oldParent.Left.Level + 1
    else oldParent.Level := 1;
end;

function Split(oldParent: PAATreeNode): Boolean;
var
  node: PAATreeNode;
begin
  node := oldParent.Right;
  if Assigned(node) and Assigned(node.Right) and (node.Right.Level = oldParent.Level) then
  begin
    if oldParent.Parent.Left = oldParent
      then oldParent.Parent.Left := node
      else oldParent.Parent.Right := node;
    node.Parent := oldParent.Parent;
    oldParent.Parent := node;
    oldParent.Right := node.Left;
    if Assigned(oldParent.Right) then
      oldParent.Right.Parent := oldParent;
    node.Left := oldParent;
    node.Level := oldParent.Level + 1;
    Result := True;
  end else Result := False;
end;
Da du deine Klasse TAA nicht vorgestellt hast, musst du den Code selbst an deine Bedürfnisse anpassen.

Freundliche Grüße vom marabu


Alle Zeitangaben in WEZ +1. Es ist jetzt 20:23 Uhr.

Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz