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));
}
for i:= l to r do {
B[0][i] = i;
B[1][i] = i;
}
resolve(A, B, l, root);
}
node insert(field A, node current, node element) {
...
}
int resolve(field A, int[][] B, int index, node current) {
if (current <> null) then {
index:= resolve(A, B, index, current.left);
s:= B[0][current.index];
t:= B[1][index];
exchange(A[s], A[index]);
B[0][t]:= s;
B[1][s]:= t;
index++;
return resolve(A, B, index, current.right);
} else {
return index;
}
}
node rrot(node a) {
...
}
node lrot(node a) {
...
}
node balance(node a, int bal) {
...
}
class node {
...
}
|