AA tree - Skew und Split

[sk.Silvia]

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]

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