Avlsort, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

Eine rekursive Realisierung (Variante 1.b) ist möglich.

Dieser Algorithmus besitzt im average und im worst case die optimalste Laufzeit und schlägt damit die Spitzenreiter Quicksort, Mergesort und Heapsort. Allerdings nicht ganz so stark, wie es aufgrund der Laufzeitabschätzung der Fall sein müßte. Das liegt daran, daß der Aufwand in "balance" überhaupt nicht berücksichtigt wurde. Ob das Verfahren für Sie am günstigsten ist, hängt davon ab, ob genügend Speicherplatz zur Verfügung steht und wie schnell mit den Knoten-Elementen hantiert werden kann (balance).

Bei kleineren Datenmengen ist der Aufwand gegenüber z.B. Quicksort sicherlich nicht gerechtfertigt, da der Gewinn minimal ausfällt. Bei sehr großen Datenmengen, wo das Vergleichen und Verschieben/Vertauschen/Kopieren sehr teuer ist, ist dieses Verfahren zu favorisieren. Das gilt auch, wenn nicht vorhergesagt werden kann, wie unsortiert die Elemente vorliegen (da Quicksorts worst-case nicht gerade besonders gut ist).

Variante 1.a (halbrekursiv)
Typ standard
Eigenschaften halbrekursiv, out-of-place, stabil, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(nlogn)
Vergleiche n(logn-1.1) n(logn-1.1) n(logn-0.7)
Kopierungen 2n 2n 2n

avlsort(field A, int l, int r) {
  root:= new node(l);
  for i:=l+1 to r do {
    root:= insert(A, root, new node(i));
  }
  resolve(A, B, l, root);
  for i:= l to r do {
    A[i]:= B[i];
  }
}

int pbal;

node insert(ifield A, node current, node element) {
  if (A[element.index] < A[current.index]) then {
    if (current.left <> null) then {
      current.left:= insert(A, current.left, element);
      pbal        := -pbal;
    } else {
      current.left:= element;
      pbal        := -1;
    }
  } else {
    if (current.right <> null) then {
      current.right:= insert(A, current.right, element);
    } else {
      current.right:= element;
      pbal         := +1;
    }
  }
  return balance(current, pbal);
}

int resolve(field A, field B, int index, node current) {
  if (current <> null) then {
    index:= resolve(A, B, index, current.left);
    B[index]:= A[current.index];
    index++;
    return resolve(A, B, index, current.right);
  } else {
    return index;
  }
}

node rrot(node a) {
  node b := a.left;
  node c := b.right;
  b.right:= a;
  a.left := c;
  pbal   += a.balance+1;
  if (b.balance <= 0) then {
    a.balance -= b.balance-1;
    b.balance += a.balance+1;
  } else {
    a.balance := 0;
    b.balance := 2;
  }
  return b;
}

node lrot(node a) {
  node b := a.right;
  node c := b.left;
  b.left := a;
  a.right:= c;
  pbal   -= a.balance-1;
  if (b.balance >= 0) then {
    a.balance -= b.balance+1;
    b.balance += a.balance-1;
  } else {
    a.balance :=  0;
    b.balance := -2;
  }
  return b;
}

node balance(node a, int bal) {
  pbal:= 0;
  if (bal <> 0) then {
    a.balance += bal;
    if (a.balance = -2) then {
      if (a.left.balance = -1) then {
        pbal++;
        return rrot(a);
      } else {
        a.left    := lrot(a.left);
        a.balance -= pbal;
        pbal++;
        return rrot(a);
      }
    } else if (a.balance = +2) then {
      if (a.right.balance = +1) then {
        pbal++;
        return lrot(a);
      } else {
        a.right   := rrot(a.right);
        a.balance += pbal;
        pbal++;
        return lrot(a);
      }
    } else if (a.balance <> 0) then {
      pbal++;
      return a;
    }
  }
  return a;
}

class node {               // Ein einzelner Knoten
  public int  index;       // des binären Suchbaums
  public node left;
  public node right;
  public int  balance;

  public node(int index) { // Konstruktor
    this.index  := index;
    this.left   := null;
    this.right  := null;
    this.balance:= 0;
  }
}


Avlsort, Variante 1