AA tree - Skew und Split

[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