Re: "Size Balanced Tree" - more efficient than any known algorithm?



PtoC (source code and binaries for Windows):
http://www.garret.ru/~knizhnik/pascal.html

It generates a C file which includes a "ptoc.h" that encapsulates
translations of Pascal system functions. The C file is as follows:

#include "ptoc.h"

/*$inline on*/

const integer maxn = 2000000;
array<0,maxn,longint> key,s,left,right,a,b;
longint tt,q;
void init()
{
input >> q >> NL;
for( q=1; q <= q; q ++)
input >> a[q] >> b[q] >> NL;
}
void work();

static void right_rotate(longint& t, longint& k)
{
k=left[t];
left[t]=right[k];
right[k]=t;
s[k]=s[t];
s[t]=s[left[t]]+s[right[t]]+longint(1);
t=k;
}


static void left_rotate(longint& t, longint& k)
{
k=right[t];
right[t]=left[k];
left[k]=t;
s[k]=s[t];
s[t]=s[left[t]]+s[right[t]]+longint(1);
t=k;
}


static void maintain(longint& t,boolean flag, longint& k)
{
if (flag==false)
if (s[left[left[t]]]>s[right[t]])
right_rotate(t, k);
else
if (s[right[left[t]]]>s[right[t]]) {
left_rotate(left[t], k);
right_rotate(t, k);
}
else
return;
else
if (s[right[right[t]]]>s[left[t]])
left_rotate(t, k);
else
if (s[left[right[t]]]>s[left[t]]) {
right_rotate(right[t], k);
left_rotate(t, k);
}
else
return;
maintain(left[t],false, k);
maintain(right[t],true, k);
maintain(t,true, k);
maintain(t,false, k);
}


static void insert1(longint& t,longint& v, longint& k)
{
if (t==0) {
tt += 1;
t=tt;
key[t]=v;
s[t]=1;
left[t]=0;
right[t]=0;
}
else {
s[t] += 1;
if (v<key[t])
insert1(left[t],v, k);
else
insert1(right[t],v, k);
maintain(t,v>=key[t], k);
}
}


static longint delete_(longint& t,longint v)
{
longint delete__result;
s[t] -= 1;
if
((v==key[t])||((v<key[t])&&(left[t]==0))||((v>key[t])&&(right[t]==0)))
{
delete__result=key[t];
if ((left[t]==0)||(right[t]==0))
t=left[t]+right[t];
else
key[t]=delete_(left[t],key[t]+longint(1));
}
else
if (v<key[t])
delete__result=delete_(left[t],v);
else
delete__result=delete_(right[t],v);
return delete__result;
}


static boolean find(longint& t,longint& v)
{
boolean find_result;
if (t==0)
exit(false);
if (v<key[t])
find_result=find(left[t],v);
else
find_result=(key[t]==v)|| find(right[t],v);
return find_result;
}


static longint rank(longint& t,longint& v)
{
longint rank_result;
if (t==0)
exit(1);
if (v<=key[t])
rank_result=rank(left[t],v);
else
rank_result=s[left[t]]+longint(1)+rank(right[t],v);
return rank_result;
}


static longint select(longint& t,longint k)
{
longint select_result;
if (k==s[left[t]]+longint(1))
exit(key[t]);
if (k<=s[left[t]])
select_result=select(left[t],k);
else
select_result=select(right[t],k-longint(1)-s[left[t]]);
return select_result;
}


static longint pred_(longint& t,longint& v)
{
longint pred__result;
if (t==0)
exit(v);
if (v<=key[t])
pred__result=pred(longint,left[t],v);
else {
pred__result=pred(longint,right[t],v);
if (pred_()==v)
pred__result=key[t];
}
return pred__result;
}


static longint succ_(longint& t,longint& v)
{
longint succ__result;
if (t==0)
exit(v);
if (key[t]<=v)
succ__result=succ(longint,right[t],v);
else {
succ__result=succ(longint,left[t],v);
if (succ_()==v)
succ__result=key[t];
}
return succ__result;
}

void work()
{
longint t,k;

tt=0;
t=0;
s[0]=0;
for( q=1; q <= q; q ++)
switch (a[q]) {
case 1:insert1(t,b[q], k); break;
case 2:delete_(t,b[q]); break;
case 3:output << btos(find(t,b[q])) << NL; break;
case 4:output << rank(t,b[q]) << NL; break;
case 5:output << select(t,b[q]) << NL; break;
case 6:output << pred(longint,t,b[q]) << NL; break;
case 7:output << succ(longint,t,b[q]) << NL; break;
}
}
int main(int argc, const char* argv[])
{
pio_initialize(argc, argv);
assign(input,"bst.in");
assign(output,"bst.out");
reset(input);
rewrite(output);
init();
work();
close(input);
close(output);
return EXIT_SUCCESS;
}



On Jan 2, 4:58 am, "Booted Cat" <yaoziy...@xxxxxxxxx> wrote:
On Jan 2, 4:52 am, sillyban...@xxxxxxxxx wrote:

Booted Cat <yaoziy...@xxxxxxxxx> wrote:
According to Chen, his algorithm is an amortized one and has much
faster speed than Adams' original algorithm. That would be a great
achievement if no prior art exists.What do you mean by this? An *algorithm* isn't amortized - the
analysis can be amortized. Or you can say that it has good amortized
performance. But it doesn't make sense to say an algorithm is
amortized.

The first guess at an interpretation is that it's an algorithm that
gives good amortized performance for arbitrary request sequences (like
Splay trees). However, that's not the case with this new data
structure, since the balance condition is a worst-case condition. If
your balance condition is worst-case, then you won't get good
amortized performance on highly skewed request sequences...Never mind. I just mean his paper refers to the word "amortized"
several times...



I took a brief look at his paper and his code. The paper looks
reasonable clear, so I'll try to look at it more carefully. On the
other hand the code is pretty horrible (and in Pascal!?), so I'm not
sure I'm going to try to slog through that...Pascal is never a problem. There are Pascal->C code converters.



--

Steve Stringer
sillyban...@xxxxxxxxx

.