Avlsort, Variante 2 (Listen-Optimierung)

Hierbei handelt es sich um eine alternative Variante, die besonders für Listen geeignet ist. Diese Variante ist realisierbar, wenn von Anfang an klar ist, daß die Daten mit diesem Verfahren sortiert werden sollen.

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

Diese Variante wäre mit ein paar Änderungen in resolve parallelisierbar. Auf die asymptotische Laufzeit hätte das aber keinen Einfluß.

Variante 2.a (halbrekursiv)
Typ alternativ
Eigenschaften halbrekursiv, in-place, stabil, nicht parallelisierbar
Datenstrukturen einfachverkettete Listen
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(nlogn) Θ(nlogn) Ο(nlogn)
Vergleiche n(logn-1.1) n(logn-1.1) n(logn-0.7)
Verschiebungen 0 n n

avlsort(listele first, listele last) {
  root    := first;
  lastnext:= last.next;
  for ele:=first.next to last do {
    ele.prev:= null;
    ele.next:= null;
    root:= insert(root, ele);
  }
  lastnext.prev:= resolve(root, first.prev);
  lastnext.prev.next:= lastnext;
}

listele insert(listele current, listele element) {
  if (element < current) then {
    if (current.prev <> null) then {
      current.prev:= insert(A, current.prev, element);
      pbal        := -pbal;
    } else {
      current.prev:= element;
      pbal        := -1;
    }
  } else {
    if (current.next <> null) then {
      current.next:= insert(A, current.next, element);
    } else {
      current.next:= element;
      pbal        := +1;
    }
  }
  return balance(current, pbal);
}


listele resolve(node current, listele prev) {
  if (current <> null) then {
    prev:= resolve(current.prev, prev);
    prev.next:= current;
    current.prev:= prev;
    return resolve(current.next, current);
  } else {
    return prev;
  }
}

listele rrot(node a) {
  ...
}

listele lrot(node a) {
  ...
}

listele balance(node a, int bal) {
  ...
}


Avlsort, Variante 2