f



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

A member ("Chen Qifeng") of an online forum about teenagers'
programming contests claims to have found a new binary search tree
algorithm that outperforms all existing well-known algorithms of its
kind, and other members of that forum who have replied all confirmed
his finding. So I think it's time to forward this result to comp.theory
for a wider-scope evaluation.

The thesis in PDF format and an accompanying Pascal source code file
are in a zip file available at:
http://yaoziyuan.googlepages.com/SizeBalancedTree.zip

Also below is the plain text version of that PDF and the source code
for the Usenet's records.

Regards,
Yao Ziyuan


=3D=3D=3D=3D PLAIN TEXT VERSION OF THE THESIS PDF =3D=3D=3D=3D
Size Balanced Tree
Chen Qifeng (Farmer John)
Zhongshan Memorial Middle School, Guangdong, China
Email:344368722@QQ.com
December 29, 2006
Abstract
This paper presents a unique strategy for maintaining balance in
dynamically
changing Binary Search Trees that has optimal expected behavior at
worst. Size
Balanced Tree is, as the name suggests, a Binary Search Tree (abbr.
BST) kept
balanced by size. It is simple, efficient and versatile in every
aspect. It is very easy to
implement and has a straightforward description and a surprisingly
simple proof of
correctness and runtime. Its runtime matches that of the fastest BST
known so far.
Furthermore, it works much faster than many other famous BSTs due to
the
tendency of a perfect BST in practice. It not only supports typical
primary
operations but also Select and Rank.
Key Words And Phrases
Size Balanced Tree
SBT
Maintain
This paper is dedicated to the memory of Heavens.
1 Introduction
Before presenting Size Balanced Trees it is necessary to explicate
Binary Search Trees
and rotations on BSTs, Left-Rotate and Right-Rotate.
1=2E1 Binary Search Tree
Binary Search Tree is a significant kind of advanced data structures.
It supports many
dynamic-set operations, including Search, Minimum, Maximum,
Predecessor, Successor,
Insert and Delete. It can be used both as a dictionary and as a
priority queue.
A BST is an organized binary tree. Every node in a BST contains two
children at most.
The keys for compare in a BST are always stored in such a way as to
satisfy the
binary-search-tree property:
Let x be a node in a binary search tree. Then the key of x is not less
than that in left
subtree and not larger than that in right subtree.
=E3=80=80=E3=80=80For every node t we use the fields of left[t] and right[t=
] to
store two pointers to its
children. And we define key[t] to mean the value of the node t for
compare. In addition
we add s[t], the size of subtree rooted at t, to keep the number of the
nodes in that tree.
Particularly we call 0 the pointer to an empty tree and s[0]=3D0.
1=2E2 Rotations
In order to keep a BST balanced (not degenerated to be a chain) we
usually change the
pointer structure through rotations to change the configuration, which
is a local operation
in a search tree that preserves the binary-search-tree property.
Figure1.1: The operation Left-Rotate(x) transforms the configuration of
the two
nodes on the right into the configuration on the left by changing a
constant number
of pointers. The configuration on the left can be transformed into the
configuration
on the right by the inverse operation, Right-Rotate(y).
1=2E2.1 Pseudocode Of Right-Rotate
The Right-Rotate assumes that the left child exists.
Right-Rotate (t)

1 k=E2=86=90left[t]

2 left[t] =E2=86=90right[k]

3 right[k] =E2=86=90t

4 s[k] =E2=86=90s[t]

5 s[t] =E2=86=90s[left[t]]+s[right[t]]+1

6 t=E2=86=90k

1=2E2.2 Pseudocode Of Left-Rotate
The Left-Rotate assumes that the right child exists.
Left-Rotate (t)

1 k=E2=86=90right[t]

2 right[t] =E2=86=90left[k]

3 left[k] =E2=86=90t

4 s[k] =E2=86=90s[t]

5 s[t] =E2=86=90s[left[t]]+s[right[t]]+1

6 t=E2=86=90k

2 Size Balanced Tree
Size Balanced Tree (abbr. SBT) is a kind of Binary Search Trees kept
balanced by size. It
supports many dynamic primary operations in the runtime of O(logn):
=E3=80=80=E3=80=80Insert(t,v)
=E3=80=80=E3=80=80Inserts a node whose key is v into the
SBT rooted at t.
=E3=80=80=E3=80=80Delete(t,v)
=E3=80=80=E3=80=80Deletes a node whose key is v from
the SBT rooted at t. In the case that no
such a node in the tree, deletes the node
searched at last.
=E3=80=80=E3=80=80Find(t,v)
=E3=80=80=E3=80=80Finds the node whose key is v and
returns it.
=E3=80=80=E3=80=80Rank(t,v)
=E3=80=80=E3=80=80Returns the rank of v in the tree
rooted at t. In another word, it is one plus
the number of the keys which are less
than v in that tree.
=E3=80=80=E3=80=80Select(t,k)
=E3=80=80=E3=80=80Returns the node which is ranked at
the kth position. Apparently it includes
operations of Get-max and Get-min
because Get-min is equivalent to
Select(t,1) and Get-max is equivalent to
Select(t,s[t])
=E3=80=80=E3=80=80Pred(t,v)
=E3=80=80=E3=80=80Returns the node with maximum key
which is less than v.
=E3=80=80=E3=80=80Succ(t,v)
=E3=80=80=E3=80=80Returns the node with minimum key
which is larger than v.

=3D=3D=3D=3D END OF PLAIN TEXT VERSION OF THE THESIS PDF =3D=3D=3D=3D

=3D=3D=3D=3D PASCAL SOURCE CODE =3D=3D=3D=3D
{$inline on}
program CQF_SBT;
const maxn=3D2000000;
var key,s,left,right,a,b:array[0..maxn] of longint;
    tt,q:longint;
procedure init;
begin
   readln(q);
   for q:=3D1 to q do
      readln(a[q],b[q]);
end;
procedure work;
var t,k:longint;
procedure right_rotate(var t:longint);inline;
begin
   k:=3Dleft[t];
   left[t]:=3Dright[k];
   right[k]:=3Dt;
   s[k]:=3Ds[t];
   s[t]:=3Ds[left[t]]+s[right[t]]+1;
   t:=3Dk;
end;
procedure left_rotate(var t:longint);inline;
begin
   k:=3Dright[t];
   right[t]:=3Dleft[k];
   left[k]:=3Dt;
   s[k]:=3Ds[t];
   s[t]:=3Ds[left[t]]+s[right[t]]+1;
   t:=3Dk;
end;
procedure maintain(var t:longint;flag:boolean);inline;
begin
   if flag=3Dfalse then
      if s[left[left[t]]]>s[right[t]] then
         right_rotate(t)
      else
         if s[right[left[t]]]>s[right[t]] then begin
            left_rotate(left[t]);
            right_rotate(t);
         end
         else
            exit
   else
      if s[right[right[t]]]>s[left[t]] then
         left_rotate(t)
      else
         if s[left[right[t]]]>s[left[t]] then begin
            right_rotate(right[t]);
            left_rotate(t);
         end
         else
            exit;
   maintain(left[t],false);
   maintain(right[t],true);
   maintain(t,true);
   maintain(t,false);
end;
procedure insert(var t,v:longint);inline;
begin
   if t=3D0 then begin
      inc(tt);
      t:=3Dtt;
      key[t]:=3Dv;
      s[t]:=3D1;
      left[t]:=3D0;
      right[t]:=3D0;
   end
   else begin
      inc(s[t]);
      if v<key[t] then
         insert(left[t],v)
      else
         insert(right[t],v);
      maintain(t,v>=3Dkey[t]);
   end;
end;
function delete(var t:longint;v:longint):longint;inline;
begin
   dec(s[t]);
   if (v=3Dkey[t])or(v<key[t])and(left[t]=3D0)or(v>key[t])and(right[t]=3D0)
then begin
      delete:=3Dkey[t];
      if (left[t]=3D0)or(right[t]=3D0) then
         t:=3Dleft[t]+right[t]
      else
         key[t]:=3Ddelete(left[t],key[t]+1);
   end
   else
      if v<key[t] then
         delete:=3Ddelete(left[t],v)
      else
         delete:=3Ddelete(right[t],v);
end;
function find(var t,v:longint):boolean;inline;
begin
   if t=3D0 then
      exit(false);
   if v<key[t] then
      find:=3Dfind(left[t],v)
   else
      find:=3D(key[t]=3Dv)or find(right[t],v);
end;
function rank(var t,v:longint):longint;inline;
begin
   if t=3D0 then
      exit(1);
   if v<=3Dkey[t] then
      rank:=3Drank(left[t],v)
   else
      rank:=3Ds[left[t]]+1+rank(right[t],v);
end;
function select(var t:longint;k:longint):longint;inline;
begin
   if k=3Ds[left[t]]+1 then
      exit(key[t]);
   if k<=3Ds[left[t]] then
      select:=3Dselect(left[t],k)
   else
      select:=3Dselect(right[t],k-1-s[left[t]]);
end;
function pred(var t,v:longint):longint;inline;
begin
   if t=3D0 then
      exit(v);
   if v<=3Dkey[t] then
      pred:=3Dpred(left[t],v)
   else begin
      pred:=3Dpred(right[t],v);
      if pred=3Dv then
         pred:=3Dkey[t];
   end;
end;
function succ(var t,v:longint):longint;inline;
begin
   if t=3D0 then
      exit(v);
   if key[t]<=3Dv then
      succ:=3Dsucc(right[t],v)
   else begin
      succ:=3Dsucc(left[t],v);
      if succ=3Dv then
         succ:=3Dkey[t];
   end;
end;
begin
   tt:=3D0;
   t:=3D0;
   s[0]:=3D0;
   for q:=3D1 to q do
      case a[q] of
         1:insert(t,b[q]);
         2:delete(t,b[q]);
         3:writeln(find(t,b[q]));
         4:writeln(rank(t,b[q]));
         5:writeln(select(t,b[q]));
         6:writeln(pred(t,b[q]));
         7:writeln(succ(t,b[q]));
      end;
end;
begin
   assign(input,'bst.in');
   assign(output,'bst.out');
   reset(input);
   rewrite(output);
   init;
   work;
   close(input);
   close(output);
end.
=3D=3D=3D=3D END OF PASCAL SOURCE CODE =3D=3D=3D=3D

0
yaoziyuan (186)
12/31/2006 9:02:55 PM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

36 Replies
1878 Views

Similar Articles

[PageSpeed] 39

On 31 Dec 2006 13:02:55 -0800, "Booted Cat" <yaoziyuan@gmail.com>
wrote:

>A member ("Chen Qifeng") of an online forum about teenagers'
>programming contests claims to have found a new binary search tree
>algorithm that outperforms all existing well-known algorithms of its
>kind, and other members of that forum who have replied all confirmed
>his finding. So I think it's time to forward this result to comp.theory
>for a wider-scope evaluation.
             

And what about discovering the light bulb?...

A.L.
0
alewando1 (106)
12/31/2006 9:19:30 PM
I don't endorse this work; I'm just the forwarder.


On Jan 1, 5:19 am, A.L. <alewa...@fala2005.com> wrote:
> On 31 Dec 2006 13:02:55 -0800, "Booted Cat" <yaoziy...@gmail.com>
> wrote:
>
> >A member ("Chen Qifeng") of an online forum about teenagers'
> >programming contests claims to have found a new binary search tree
> >algorithm that outperforms all existing well-known algorithms of its
> >kind, and other members of that forum who have replied all confirmed
> >his finding. So I think it's time to forward this result to comp.theory
> >for a wider-scope evaluation.And what about discovering the light bulb?...
> 
> A.L.

0
yaoziyuan (186)
12/31/2006 9:30:02 PM
Seems this concept (size-balanced binary search tree) is no new. See:

Stephen Adams, "Efficient sets: a balancing act", Journal of Functional
Programming 3(4):553-562, October 1993,
http://www.swiss.ai.mit.edu/~adams/BB.

J. Nievergelt and E.M. Reingold, "Binary search trees of bounded
balance", SIAM journal of computing 2(1), March 1973.

0
yaoziyuan (186)
12/31/2006 10:12:54 PM
I am Chen Qifeng, the author of that paper.
First I have to say "I never say that this concept, "Size Balanced" ,
is created by myself and that it is faster than all existing BSTs".
I think the new in my paper is the unique way to keep balanced:
(a)s[right[t]]>=s[left[left[t]]],s[right[left[t]]]
(b)s[left[t]]>=s[right[right[t]]],s[left[right[t]]]
And under such properties a BST works quite well. It is the reason I
wrote this paper.

I am a student in a middle school in China. It is hard for me to read
many foreign theses although they are famous. I am afflicted by the
lack of papers. Could you tell me how to get famous theses about
algorithms and data structures.

0
344368722 (5)
1/1/2007 2:07:54 AM
I didn't read your paper and was influenced by the hurrays on that
forum so I misreported something...

Famous, seminal papers are discovered by following references by random
papers you hunt with a keyword-based search engine.


On Jan 1, 10:07 am, "Chen Qifeng" <344368...@qq.com> wrote:
> I am Chen Qifeng, the author of that paper.
> First I have to say "I never say that this concept, "Size Balanced" ,
> is created by myself and that it is faster than all existing BSTs".
> I think the new in my paper is the unique way to keep balanced:
> (a)s[right[t]]>=s[left[left[t]]],s[right[left[t]]]
> (b)s[left[t]]>=s[right[right[t]]],s[left[right[t]]]
> And under such properties a BST works quite well. It is the reason I
> wrote this paper.
>
> I am a student in a middle school in China. It is hard for me to read
> many foreign theses although they are famous. I am afflicted by the
> lack of papers. Could you tell me how to get famous theses about
> algorithms and data structures.

0
yaoziyuan (186)
1/1/2007 3:02:59 AM
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.

On Jan 1, 11:02 am, "Booted Cat" <yaoziy...@gmail.com> wrote:
> I didn't read your paper and was influenced by the hurrays on that
> forum so I misreported something...
>
> Famous, seminal papers are discovered by following references by random
> papers you hunt with a keyword-based search engine.
>
> On Jan 1, 10:07 am, "Chen Qifeng" <344368...@qq.com> wrote:
>
> > I am Chen Qifeng, the author of that paper.
> > First I have to say "I never say that this concept, "Size Balanced" ,
> > is created by myself and that it is faster than all existing BSTs".
> > I think the new in my paper is the unique way to keep balanced:
> > (a)s[right[t]]>=s[left[left[t]]],s[right[left[t]]]
> > (b)s[left[t]]>=s[right[right[t]]],s[left[right[t]]]
> > And under such properties a BST works quite well. It is the reason I
> > wrote this paper.
>
> > I am a student in a middle school in China. It is hard for me to read
> > many foreign theses although they are famous. I am afflicted by the
> > lack of papers. Could you tell me how to get famous theses about
> > algorithms and data structures.

0
yaoziyuan (186)
1/1/2007 4:25:09 AM
Chen Qifeng <344368722@qq.com> wrote:
> I am Chen Qifeng, the author of that paper.
> First I have to say "I never say that this concept, "Size Balanced" ,
> is created by myself and that it is faster than all existing BSTs".
> I think the new in my paper is the unique way to keep balanced:
> (a)s[right[t]]>=s[left[left[t]]],s[right[left[t]]]
> (b)s[left[t]]>=s[right[right[t]]],s[left[right[t]]]
> And under such properties a BST works quite well. It is the reason I
> wrote this paper.
> 
> I am a student in a middle school in China. It is hard for me to read
> many foreign theses although they are famous. I am afflicted by the
> lack of papers. Could you tell me how to get famous theses about
> algorithms and data structures.

On first glance, I don't see anything obviuosly flakey in this (sorry
if that seems harsh, but things posted here talking of some new
discovery are mostly bogus).  I'll look at it a little more if I have
time over the next few days or so.

I can say that you should have compared it to some more efficient
balanced BST implementations.  For example, how does it compare to
red-black trees?  2-3 trees?   AVL trees are historically significant
and a good example of a balanced binary tree, but hardly anyone uses
them since there are more efficient methods in practice.  Since your
new tree seems to barely beat AVL trees, I'm somewhat suspicious that
it would lose when compared with some of these other BSTs...  or what
about comparing to non-tree-based data structures for the same ADT,
like skip lists?

-- 

Steve Stringer
sillybanter@gmail.com

0
1/1/2007 8:30:35 PM
On 31 Dec 2006 20:25:09 -0800, "Booted Cat" <yaoziyuan@gmail.com>
wrote:

>According to Chen, his algorithm is an amortized one and has much
>faster speed 

What this means "faster speed"?... 

A.L.
0
alewando1 (106)
1/1/2007 8:37:21 PM
Booted Cat <yaoziyuan@gmail.com> 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...

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...

-- 

Steve Stringer
sillybanter@gmail.com

0
1/1/2007 8:52:17 PM

On Jan 2, 4:52 am, sillyban...@gmail.com wrote:
> Booted Cat <yaoziy...@gmail.com> 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...@gmail.com

0
yaoziyuan (186)
1/1/2007 8:58:06 PM
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...@gmail.com> wrote:
> On Jan 2, 4:52 am, sillyban...@gmail.com wrote:
>
> > Booted Cat <yaoziy...@gmail.com> 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...@gmail.com

0
yaoziyuan (186)
1/1/2007 9:12:16 PM
Sorry, this is a C++ output.

On Jan 2, 5:12 am, "Booted Cat" <yaoziy...@gmail.com> wrote:
> 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...@gmail.com> wrote:
>
> > On Jan 2, 4:52 am, sillyban...@gmail.com wrote:
>
> > > Booted Cat <yaoziy...@gmail.com> 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...@gmail.com

0
yaoziyuan (186)
1/1/2007 9:15:53 PM
Booted Cat <yaoziyuan@gmail.com> wrote:
> PtoC (source code and binaries for Windows):
> http://www.garret.ru/~knizhnik/pascal.html

Yes, I've got ptoc...  still horrendous code, no matter what
programming language....

-- 

Steve Stringer
sillybanter@gmail.com

0
1/2/2007 4:37:59 AM
Yeah, because some programming contestants like to use single-letter
variable names.


On Jan 2, 12:37 pm, sillyban...@gmail.com wrote:
> Booted Cat <yaoziy...@gmail.com> wrote:
> > PtoC (source code and binaries for Windows):
> >http://www.garret.ru/~knizhnik/pascal.htmlYes, I've got ptoc...  still horrendous code, no matter what
> programming language....
> 
> --
> 
> Steve Stringer
> sillyban...@gmail.com

0
yaoziyuan (186)
1/2/2007 4:47:40 AM
I am sorry for the vagueness about "amortized".
I means that at worst the amortized runtime of Maintain is still O(1).
It is similar with Splay. Maybe the runtime for some Maintain is more
than O(1).

0
344368722 (5)
1/2/2007 6:35:40 AM
>>>>> "CQ" == Chen Qifeng <344368722@qq.com> writes:

See the top of page 476 in vol. 3 of Knuth, 2nd ed.

-- 

Professor Edward M. Reingold                Email: reingold@iit.edu
Department of Computer Science              Voice: (312) 567-3309
Illinois Institute of Technology            Assistant: (312) 567-5152
Stuart Building                             Fax:   (312) 567-5067
10 West 31st Street, Suite 236
Chicago, IL  60616-3729  U.S.A.
0
reingold (129)
1/2/2007 1:48:24 PM
Sorry. I don't have that book. What is it about?
On Jan 2, 9:48 pm, reing...@emr.cs.iit.edu (Edward M. Reingold) wrote:
> >>>>> "CQ" == Chen Qifeng <344368...@qq.com> writes:See the top of page 476 in vol. 3 of Knuth, 2nd ed.
>
> --
>
> Professor Edward M. Reingold                Email: reing...@iit.edu
> Department of Computer Science              Voice: (312) 567-3309
> Illinois Institute of Technology            Assistant: (312) 567-5152
> Stuart Building                             Fax:   (312) 567-5067
> 10 West 31st Street, Suite 236
> Chicago, IL  60616-3729  U.S.A.

0
344368722 (5)
1/3/2007 8:17:26 AM
>>>>> "CQ" == Chen Qifeng <344368722@qq.com> writes:

    CQ> Sorry. I don't have that book. What is it about?
    CQ> On Jan 2, 9:48 pm, reing...@emr.cs.iit.edu (Edward M. Reingold) wrote:
    >> >>>>> "CQ" == Chen Qifeng <344368...@qq.com> writes:See the top of page
    >> 476 in vol. 3 of Knuth, 2nd ed.

It is THE standard for this type of data structure result; it is in most
science/engineering libraries around the world.

-- 

Professor Edward M. Reingold                Email: reingold@iit.edu
Department of Computer Science              Voice: (312) 567-3309
Illinois Institute of Technology            Assistant: (312) 567-5152
Stuart Building                             Fax:   (312) 567-5067
10 West 31st Street, Suite 236
Chicago, IL  60616-3729  U.S.A.
0
reingold (129)
1/3/2007 2:44:24 PM
The background motive behind things like this is China's poor computer
science undergraduate programs which stifle the young geniuses who won
top places in national programming competitions and even international
olympiads in informatics (IOI's) during their junior middle school and
high school time: they want to find better academic (especially
research) opportunities and communities. Since long ago a gold medal of
IOI no longer serves as a significant admission advantage for applying
to an american computer science undergrad program, so some of them
begin trying to present some research results to lure american
professors. For example, a previous attempt is:
http://groups.google.com/group/sci.math/browse_frm/thread/50586a0beb4ec1d/e=
c5b6e9e39f6a592?lnk=3Dst&q=3Dsci.math+zhu+zeyuan&rnum=3D2#ec5b6e9e39f6a592

Undergraduate students with their own research initiatives and projects
have to drop out, as i did from Fudan University. So I very much
understand these current programming contestants. I told them maybe for
fundamental and heavily attacked things like the binary search tree it
is nearly impossible to get something new and significant; maybe they
should look into the theoretical part of promising fields such as
computational biology, or anything of their own interest. But as Anders
Kaseorg (MIT undergrad who won quite a number of IOI's and IMO's in
high school) suggested, there is too little a turnround for someone
having just completed all his programming competition seasons in high
school to make a seriously good research result in fields like
computational biology and immediately present it to american professors
for admission to an american university.

Or maybe I should write an open letter, get some famous american cs
professors sign it, and maybe also the ACM President, calling for a
wholesale of China's top 30 contestants in every year's national
olympiad in informatics to american universities...

Yao Ziyuan


On Jan 1, 5:02 am, "Booted Cat" <yaoziy...@gmail.com> wrote:
> A member ("Chen Qifeng") of an online forum about teenagers'
> programming contests claims to have found a new binary search tree
> algorithm that outperforms all existing well-known algorithms of its
> kind, and other members of that forum who have replied all confirmed
> his finding. So I think it's time to forward this result to comp.theory
> for a wider-scope evaluation.
>
> The thesis in PDF format and an accompanying Pascal source code file
> are in a zip file available at:http://yaoziyuan.googlepages.com/SizeBalan=
cedTree.zip
>
> Also below is the plain text version of that PDF and the source code
> for the Usenet's records.
>
> Regards,
> Yao Ziyuan
>
> =3D=3D=3D=3D PLAIN TEXT VERSION OF THE THESIS PDF =3D=3D=3D=3D
> Size Balanced Tree
> Chen Qifeng (Farmer John)
> Zhongshan Memorial Middle School, Guangdong, China
> Email:344368...@QQ.com
> December 29, 2006
> Abstract
> This paper presents a unique strategy for maintaining balance in
> dynamically
> changing Binary Search Trees that has optimal expected behavior at
> worst. Size
> Balanced Tree is, as the name suggests, a Binary Search Tree (abbr.
> BST) kept
> balanced by size. It is simple, efficient and versatile in every
> aspect. It is very easy to
> implement and has a straightforward description and a surprisingly
> simple proof of
> correctness and runtime. Its runtime matches that of the fastest BST
> known so far.
> Furthermore, it works much faster than many other famous BSTs due to
> the
> tendency of a perfect BST in practice. It not only supports typical
> primary
> operations but also Select and Rank.
> Key Words And Phrases
> Size Balanced Tree
> SBT
> Maintain
> This paper is dedicated to the memory of Heavens.
> 1 Introduction
> Before presenting Size Balanced Trees it is necessary to explicate
> Binary Search Trees
> and rotations on BSTs, Left-Rotate and Right-Rotate.
> 1.1 Binary Search Tree
> Binary Search Tree is a significant kind of advanced data structures.
> It supports many
> dynamic-set operations, including Search, Minimum, Maximum,
> Predecessor, Successor,
> Insert and Delete. It can be used both as a dictionary and as a
> priority queue.
> A BST is an organized binary tree. Every node in a BST contains two
> children at most.
> The keys for compare in a BST are always stored in such a way as to
> satisfy the
> binary-search-tree property:
> Let x be a node in a binary search tree. Then the key of x is not less
> than that in left
> subtree and not larger than that in right subtree.
> =E3=80=80=E3=80=80For every node t we use the fields of left[t] and right=
[t] to
> store two pointers to its
> children. And we define key[t] to mean the value of the node t for
> compare. In addition
> we add s[t], the size of subtree rooted at t, to keep the number of the
> nodes in that tree.
> Particularly we call 0 the pointer to an empty tree and s[0]=3D0.
> 1.2 Rotations
> In order to keep a BST balanced (not degenerated to be a chain) we
> usually change the
> pointer structure through rotations to change the configuration, which
> is a local operation
> in a search tree that preserves the binary-search-tree property.
> Figure1.1: The operation Left-Rotate(x) transforms the configuration of
> the two
> nodes on the right into the configuration on the left by changing a
> constant number
> of pointers. The configuration on the left can be transformed into the
> configuration
> on the right by the inverse operation, Right-Rotate(y).
> 1.2.1 Pseudocode Of Right-Rotate
> The Right-Rotate assumes that the left child exists.
> Right-Rotate (t)
>
> 1 k=E2=86=90left[t]
>
> 2 left[t] =E2=86=90right[k]
>
> 3 right[k] =E2=86=90t
>
> 4 s[k] =E2=86=90s[t]
>
> 5 s[t] =E2=86=90s[left[t]]+s[right[t]]+1
>
> 6 t=E2=86=90k
>
> 1.2.2 Pseudocode Of Left-Rotate
> The Left-Rotate assumes that the right child exists.
> Left-Rotate (t)
>
> 1 k=E2=86=90right[t]
>
> 2 right[t] =E2=86=90left[k]
>
> 3 left[k] =E2=86=90t
>
> 4 s[k] =E2=86=90s[t]
>
> 5 s[t] =E2=86=90s[left[t]]+s[right[t]]+1
>
> 6 t=E2=86=90k
>
> 2 Size Balanced Tree
> Size Balanced Tree (abbr. SBT) is a kind of Binary Search Trees kept
> balanced by size. It
> supports many dynamic primary operations in the runtime of O(logn):
> =E3=80=80=E3=80=80Insert(t,v)
> =E3=80=80=E3=80=80Inserts a node whose key is v into the
> SBT rooted at t.
> =E3=80=80=E3=80=80Delete(t,v)
> =E3=80=80=E3=80=80Deletes a node whose key is v from
> the SBT rooted at t. In the case that no
> such a node in the tree, deletes the node
> searched at last.
> =E3=80=80=E3=80=80Find(t,v)
> =E3=80=80=E3=80=80Finds the node whose key is v and
> returns it.
> =E3=80=80=E3=80=80Rank(t,v)
> =E3=80=80=E3=80=80Returns the rank of v in the tree
> rooted at t. In another word, it is one plus
> the number of the keys which are less
> than v in that tree.
> =E3=80=80=E3=80=80Select(t,k)
> =E3=80=80=E3=80=80Returns the node which is ranked at
> the kth position. Apparently it includes
> operations of Get-max and Get-min
> because Get-min is equivalent to
> Select(t,1) and Get-max is equivalent to
> Select(t,s[t])
> =E3=80=80=E3=80=80Pred(t,v)
> =E3=80=80=E3=80=80Returns the node with maximum key
> which is less than v.
> =E3=80=80=E3=80=80Succ(t,v)
> =E3=80=80=E3=80=80Returns the node with minimum key
> which is larger than v.
>
> =3D=3D=3D=3D END OF PLAIN TEXT VERSION OF THE THESIS PDF =3D=3D=3D=3D
>
> =3D=3D=3D=3D PASCAL SOURCE CODE =3D=3D=3D=3D
> {$inline on}
> program CQF_SBT;
> const maxn=3D2000000;
> var key,s,left,right,a,b:array[0..maxn] of longint;
>     tt,q:longint;
> procedure init;
> begin
>    readln(q);
>    for q:=3D1 to q do
>       readln(a[q],b[q]);
> end;
> procedure work;
> var t,k:longint;
> procedure right_rotate(var t:longint);inline;
> begin
>    k:=3Dleft[t];
>    left[t]:=3Dright[k];
>    right[k]:=3Dt;
>    s[k]:=3Ds[t];
>    s[t]:=3Ds[left[t]]+s[right[t]]+1;
>    t:=3Dk;
> end;
> procedure left_rotate(var t:longint);inline;
> begin
>    k:=3Dright[t];
>    right[t]:=3Dleft[k];
>    left[k]:=3Dt;
>    s[k]:=3Ds[t];
>    s[t]:=3Ds[left[t]]+s[right[t]]+1;
>    t:=3Dk;
> end;
> procedure maintain(var t:longint;flag:boolean);inline;
> begin
>    if flag=3Dfalse then
>       if s[left[left[t]]]>s[right[t]] then
>          right_rotate(t)
>       else
>          if s[right[left[t]]]>s[right[t]] then begin
>             left_rotate(left[t]);
>             right_rotate(t);
>          end
>          else
>             exit
>    else
>       if s[right[right[t]]]>s[left[t]] then
>          left_rotate(t)
>       else
>          if s[left[right[t]]]>s[left[t]] then begin
>             right_rotate(right[t]);
>             left_rotate(t);
>          end
>          else
>             exit;
>    maintain(left[t],false);
>    maintain(right[t],true);
>    maintain(t,true);
>    maintain(t,false);
> end;
> procedure insert(var t,v:longint);inline;
> begin
>    if t=3D0 then begin
>       inc(tt);
>       t:=3Dtt;
>       key[t]:=3Dv;
>       s[t]:=3D1;
>       left[t]:=3D0;
>       right[t]:=3D0;
>    end
>    else begin
>       inc(s[t]);
>       if v<key[t] then
>          insert(left[t],v)
>       else
>          insert(right[t],v);
>       maintain(t,v>=3Dkey[t]);
>    end;
> end;
> function delete(var t:longint;v:longint):longint;inline;
> begin
>    dec(s[t]);
>    if (v=3Dkey[t])or(v<key[t])and(left[t]=3D0)or(v>key[t])and(right[t]=3D=
0)
> then begin
>       delete:=3Dkey[t];
>       if (left[t]=3D0)or(right[t]=3D0) then
>          t:=3Dleft[t]+right[t]
>       else
>          key[t]:=3Ddelete(left[t],key[t]+1);
>    end
>    else
>       if v<key[t] then
>          delete:=3Ddelete(left[t],v)
>       else
>          delete:=3Ddelete(right[t],v);
> end;
> function find(var t,v:longint):boolean;inline;
> begin
>    if t=3D0 then
>       exit(false);
>    if v<key[t] then
>       find:=3Dfind(left[t],v)
>    else
>       find:=3D(key[t]=3Dv)or find(right[t],v);
> end;
> function rank(var t,v:longint):longint;inline;
> begin
>    if t=3D0 then
>       exit(1);
>    if v<=3Dkey[t] then
>       rank:=3Drank(left[t],v)
>    else
>       rank:=3Ds[left[t]]+1+rank(right[t],v);
> end;
> function select(var t:longint;k:longint):longint;inline;
> begin
>    if k=3Ds[left[t]]+1 then
>       exit(key[t]);
>    if k<=3Ds[left[t]] then
>       select:=3Dselect(left[t],k)
>    else
>       select:=3Dselect(right[t],k-1-s[left[t]]);
> end;
> function pred(var t,v:longint):longint;inline;
> begin
>    if t=3D0 then
>       exit(v);
>    if v<=3Dkey[t] then
>       pred:=3Dpred(left[t],v)
>    else begin
>       pred:=3Dpred(right[t],v);
>       if pred=3Dv then
>          pred:=3Dkey[t];
>    end;
> end;
> function succ(var t,v:longint):longint;inline;
> begin
>    if t=3D0 then
>       exit(v);
>    if key[t]<=3Dv then
>       succ:=3Dsucc(right[t],v)
>    else begin
>       succ:=3Dsucc(left[t],v);
>       if succ=3Dv then
>          succ:=3Dkey[t];
>    end;
> end;
> begin
>    tt:=3D0;
>    t:=3D0;
>    s[0]:=3D0;
>    for q:=3D1 to q do
>       case a[q] of
>          1:insert(t,b[q]);
>          2:delete(t,b[q]);
>          3:writeln(find(t,b[q]));
>          4:writeln(rank(t,b[q]));
>          5:writeln(select(t,b[q]));
>          6:writeln(pred(t,b[q]));
>          7:writeln(succ(t,b[q]));
>       end;
> end;
> begin
>    assign(input,'bst.in');
>    assign(output,'bst.out');
>    reset(input);
>    rewrite(output);
>    init;
>    work;
>    close(input);
>    close(output);
> end.
> =3D=3D=3D=3D END OF PASCAL SOURCE CODE =3D=3D=3D=3D

0
yaoziyuan (186)
1/5/2007 12:38:35 AM
Is it about weight-balanced tree(page 476 in vol. 3 of Knuth)? It quite
differs from SBT. Weight-balanced tree guarantees that
1/w<size[left]/size[right]<w . Sometimes w here is sqrt(2). Due to the
slow division it works unefficiently. On the contrary there are only
compares and additions in SBT.
On Jan 5, 8:38=C2=A0am, "Booted Cat" <yaoziy...@gmail.com> wrote:
> The background motive behind things like this is China's poor computer
> science undergraduate programs which stifle the young geniuses who won
> top places in national programming competitions and even international
> olympiads in informatics (IOI's) during their junior middle school and
> high school time: they want to find better academic (especially
> research) opportunities and communities. Since long ago a gold medal of
> IOI no longer serves as a significant admission advantage for applying
> to an american computer science undergrad program, so some of them
> begin trying to present some research results to lure american
> professors. For example, a previous attempt is:http://groups.google.com/g=
roup/sci.math/browse_frm/thread/50586a0beb4...
>
> Undergraduate students with their own research initiatives and projects
> have to drop out, as i did from Fudan University. So I very much
> understand these current programming contestants. I told them maybe for
> fundamental and heavily attacked things like the binary search tree it
> is nearly impossible to get something new and significant; maybe they
> should look into the theoretical part of promising fields such as
> computational biology, or anything of their own interest. But as Anders
> Kaseorg (MIT undergrad who won quite a number of IOI's and IMO's in
> high school) suggested, there is too little a turnround for someone
> having just completed all his programming competition seasons in high
> school to make a seriously good research result in fields like
> computational biology and immediately present it to american professors
> for admission to an american university.
>
> Or maybe I should write an open letter, get some famous american cs
> professors sign it, and maybe also the ACM President, calling for a
> wholesale of China's top 30 contestants in every year's national
> olympiad in informatics to american universities...
>
> Yao Ziyuan
>
> On Jan 1, 5:02 am, "Booted Cat" <yaoziy...@gmail.com> wrote:
>
>
>
> > A member ("Chen Qifeng") of an online forum about teenagers'
> > programming contests claims to have found a new binary search tree
> > algorithm that outperforms all existing well-known algorithms of its
> > kind, and other members of that forum who have replied all confirmed
> > his finding. So I think it's time to forward this result to comp.theory
> > for a wider-scope evaluation.
>
> > The thesis in PDF format and an accompanying Pascal source code file
> > are in a zip file available at:http://yaoziyuan.googlepages.com/SizeBal=
ancedTree.zip
>
> > Also below is the plain text version of that PDF and the source code
> > for the Usenet's records.
>
> > Regards,
> > Yao Ziyuan
>
> > =3D=3D=3D=3D PLAIN TEXT VERSION OF THE THESIS PDF =3D=3D=3D=3D
> > Size Balanced Tree
> > Chen Qifeng (Farmer John)
> > Zhongshan Memorial Middle School, Guangdong, China
> > Email:344368...@QQ.com
> > December 29, 2006
> > Abstract
> > This paper presents a unique strategy for maintaining balance in
> > dynamically
> > changing Binary Search Trees that has optimal expected behavior at
> > worst. Size
> > Balanced Tree is, as the name suggests, a Binary Search Tree (abbr.
> > BST) kept
> > balanced by size. It is simple, efficient and versatile in every
> > aspect. It is very easy to
> > implement and has a straightforward description and a surprisingly
> > simple proof of
> > correctness and runtime. Its runtime matches that of the fastest BST
> > known so far.
> > Furthermore, it works much faster than many other famous BSTs due to
> > the
> > tendency of a perfect BST in practice. It not only supports typical
> > primary
> > operations but also Select and Rank.
> > Key Words And Phrases
> > Size Balanced Tree
> > SBT
> > Maintain
> > This paper is dedicated to the memory of Heavens.
> > 1 Introduction
> > Before presenting Size Balanced Trees it is necessary to explicate
> > Binary Search Trees
> > and rotations on BSTs, Left-Rotate and Right-Rotate.
> > 1.1 Binary Search Tree
> > Binary Search Tree is a significant kind of advanced data structures.
> > It supports many
> > dynamic-set operations, including Search, Minimum, Maximum,
> > Predecessor, Successor,
> > Insert and Delete. It can be used both as a dictionary and as a
> > priority queue.
> > A BST is an organized binary tree. Every node in a BST contains two
> > children at most.
> > The keys for compare in a BST are always stored in such a way as to
> > satisfy the
> > binary-search-tree property:
> > Let x be a node in a binary search tree. Then the key of x is not less
> > than that in left
> > subtree and not larger than that in right subtree.
> > =E3=80=80=E3=80=80For every node t we use the fields of left[t] and rig=
ht[t] to
> > store two pointers to its
> > children. And we define key[t] to mean the value of the node t for
> > compare. In addition
> > we add s[t], the size of subtree rooted at t, to keep the number of the
> > nodes in that tree.
> > Particularly we call 0 the pointer to an empty tree and s[0]=3D0.
> > 1.2 Rotations
> > In order to keep a BST balanced (not degenerated to be a chain) we
> > usually change the
> > pointer structure through rotations to change the configuration, which
> > is a local operation
> > in a search tree that preserves the binary-search-tree property.
> > Figure1.1: The operation Left-Rotate(x) transforms the configuration of
> > the two
> > nodes on the right into the configuration on the left by changing a
> > constant number
> > of pointers. The configuration on the left can be transformed into the
> > configuration
> > on the right by the inverse operation, Right-Rotate(y).
> > 1.2.1 Pseudocode Of Right-Rotate
> > The Right-Rotate assumes that the left child exists.
> > Right-Rotate (t)
>
> > 1 k=E2=86=90left[t]
>
> > 2 left[t] =E2=86=90right[k]
>
> > 3 right[k] =E2=86=90t
>
> > 4 s[k] =E2=86=90s[t]
>
> > 5 s[t] =E2=86=90s[left[t]]+s[right[t]]+1
>
> > 6 t=E2=86=90k
>
> > 1.2.2 Pseudocode Of Left-Rotate
> > The Left-Rotate assumes that the right child exists.
> > Left-Rotate (t)
>
> > 1 k=E2=86=90right[t]
>
> > 2 right[t] =E2=86=90left[k]
>
> > 3 left[k] =E2=86=90t
>
> > 4 s[k] =E2=86=90s[t]
>
> > 5 s[t] =E2=86=90s[left[t]]+s[right[t]]+1
>
> > 6 t=E2=86=90k
>
> > 2 Size Balanced Tree
> > Size Balanced Tree (abbr. SBT) is a kind of Binary Search Trees kept
> > balanced by size. It
> > supports many dynamic primary operations in the runtime of O(logn):
> > =E3=80=80=E3=80=80Insert(t,v)
> > =E3=80=80=E3=80=80Inserts a node whose key is v into the
> > SBT rooted at t.
> > =E3=80=80=E3=80=80Delete(t,v)
> > =E3=80=80=E3=80=80Deletes a node whose key is v from
> > the SBT rooted at t. In the case that no
> > such a node in the tree, deletes the node
> > searched at last.
> > =E3=80=80=E3=80=80Find(t,v)
> > =E3=80=80=E3=80=80Finds the node whose key is v and
> > returns it.
> > =E3=80=80=E3=80=80Rank(t,v)
> > =E3=80=80=E3=80=80Returns the rank of v in the tree
> > rooted at t. In another word, it is one plus
> > the number of the keys which are less
> > than v in that tree.
> > =E3=80=80=E3=80=80Select(t,k)
> > =E3=80=80=E3=80=80Returns the node which is ranked at
> > the kth position. Apparently it includes
> > operations of Get-max and Get-min
> > because Get-min is equivalent to
> > Select(t,1) and Get-max is equivalent to
> > Select(t,s[t])
> > =E3=80=80=E3=80=80Pred(t,v)
> > =E3=80=80=E3=80=80Returns the node with maximum key
> > which is less than v.
> > =E3=80=80=E3=80=80Succ(t,v)
> > =E3=80=80=E3=80=80Returns the node with minimum key
> > which is larger than v.
>
> > =3D=3D=3D=3D END OF PLAIN TEXT VERSION OF THE THESIS PDF =3D=3D=3D=3D
>
> > =3D=3D=3D=3D PASCAL SOURCE CODE =3D=3D=3D=3D
> > {$inline on}
> > program CQF_SBT;
> > const maxn=3D2000000;
> > var key,s,left,right,a,b:array[0..maxn] of longint;
> > =C2=A0 =C2=A0 tt,q:longint;
> > procedure init;
> > begin
> > =C2=A0 =C2=A0readln(q);
> > =C2=A0 =C2=A0for q:=3D1 to q do
> > =C2=A0 =C2=A0 =C2=A0 readln(a[q],b[q]);
> > end;
> > procedure work;
> > var t,k:longint;
> > procedure right_rotate(var t:longint);inline;
> > begin
> > =C2=A0 =C2=A0k:=3Dleft[t];
> > =C2=A0 =C2=A0left[t]:=3Dright[k];
> > =C2=A0 =C2=A0right[k]:=3Dt;
> > =C2=A0 =C2=A0s[k]:=3Ds[t];
> > =C2=A0 =C2=A0s[t]:=3Ds[left[t]]+s[right[t]]+1;
> > =C2=A0 =C2=A0t:=3Dk;
> > end;
> > procedure left_rotate(var t:longint);inline;
> > begin
> > =C2=A0 =C2=A0k:=3Dright[t];
> > =C2=A0 =C2=A0right[t]:=3Dleft[k];
> > =C2=A0 =C2=A0left[k]:=3Dt;
> > =C2=A0 =C2=A0s[k]:=3Ds[t];
> > =C2=A0 =C2=A0s[t]:=3Ds[left[t]]+s[right[t]]+1;
> > =C2=A0 =C2=A0t:=3Dk;
> > end;
> > procedure maintain(var t:longint;flag:boolean);inline;
> > begin
> > =C2=A0 =C2=A0if flag=3Dfalse then
> > =C2=A0 =C2=A0 =C2=A0 if s[left[left[t]]]>s[right[t]] then
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0right_rotate(t)
> > =C2=A0 =C2=A0 =C2=A0 else
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if s[right[left[t]]]>s[right[t]] then=
 begin
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 left_rotate(left[t]);
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 right_rotate(t);
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0end
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0else
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 exit
> > =C2=A0 =C2=A0else
> > =C2=A0 =C2=A0 =C2=A0 if s[right[right[t]]]>s[left[t]] then
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0left_rotate(t)
> > =C2=A0 =C2=A0 =C2=A0 else
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if s[left[right[t]]]>s[left[t]] then =
begin
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 right_rotate(right[t]);
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 left_rotate(t);
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0end
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0else
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 exit;
> > =C2=A0 =C2=A0maintain(left[t],false);
> > =C2=A0 =C2=A0maintain(right[t],true);
> > =C2=A0 =C2=A0maintain(t,true);
> > =C2=A0 =C2=A0maintain(t,false);
> > end;
> > procedure insert(var t,v:longint);inline;
> > begin
> > =C2=A0 =C2=A0if t=3D0 then begin
> > =C2=A0 =C2=A0 =C2=A0 inc(tt);
> > =C2=A0 =C2=A0 =C2=A0 t:=3Dtt;
> > =C2=A0 =C2=A0 =C2=A0 key[t]:=3Dv;
> > =C2=A0 =C2=A0 =C2=A0 s[t]:=3D1;
> > =C2=A0 =C2=A0 =C2=A0 left[t]:=3D0;
> > =C2=A0 =C2=A0 =C2=A0 right[t]:=3D0;
> > =C2=A0 =C2=A0end
> > =C2=A0 =C2=A0else begin
> > =C2=A0 =C2=A0 =C2=A0 inc(s[t]);
> > =C2=A0 =C2=A0 =C2=A0 if v<key[t] then
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0insert(left[t],v)
> > =C2=A0 =C2=A0 =C2=A0 else
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0insert(right[t],v);
> > =C2=A0 =C2=A0 =C2=A0 maintain(t,v>=3Dkey[t]);
> > =C2=A0 =C2=A0end;
> > end;
> > function delete(var t:longint;v:longint):longint;inline;
> > begin
> > =C2=A0 =C2=A0dec(s[t]);
> > =C2=A0 =C2=A0if (v=3Dkey[t])or(v<key[t])and(left[t]=3D0)or(v>key[t])and=
(right[t]=3D0)
> > then begin
> > =C2=A0 =C2=A0 =C2=A0 delete:=3Dkey[t];
> > =C2=A0 =C2=A0 =C2=A0 if (left[t]=3D0)or(right[t]=3D0) then
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0t:=3Dleft[t]+right[t]
> > =C2=A0 =C2=A0 =C2=A0 else
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0key[t]:=3Ddelete(left[t],key[t]+1);
> > =C2=A0 =C2=A0end
> > =C2=A0 =C2=A0else
> > =C2=A0 =C2=A0 =C2=A0 if v<key[t] then
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0delete:=3Ddelete(left[t],v)
> > =C2=A0 =C2=A0 =C2=A0 else
> > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0delete:=3Ddelete(right[t],v);
> > end;
> > function find(var t,v:longint):boolean;inline;
> > begin
> > =C2=A0 =C2=A0if t=3D0 then
> > =C2=A0 =C2=A0 =C2=A0 exit(false);
> > =C2=A0 =C2=A0if v<key[t] then
> > =C2=A0 =C2=A0 =C2=A0 find:=3Dfind(left[t],v)
> > =C2=A0 =C2=A0else
> > =C2=A0 =C2=A0 =C2=A0 find:=3D(key[t]=3Dv)or find(right[t],v);
> > end;
> > function rank(var t,v:longint):longint;inline;
> > begin
> > =C2=A0 =C2=A0if t=3D0 then
> > =C2=A0 =C2=A0 =C2=A0 exit(1);
> > =C2=A0 =C2=A0if v<=3Dkey[t] then
> > =C2=A0 =C2=A0 =C2=A0 rank:=3Drank(left[t],v)
> > =C2=A0 =C2=A0else
> > =C2=A0 =C2=A0 =C2=A0 rank:=3Ds[left[t]]+1+rank(right[t],v);
> > end;
> > function select(var t:longint;k:longint):longint;inline;
> > begin
> > =C2=A0 =C2=A0if k=3Ds[left[t]]+1 then
> > =C2=A0 =C2=A0 =C2=A0 exit(key[t]);
> > =C2=A0 =C2=A0if k<=3Ds[left[t]] then
> > =C2=A0 =C2=A0 =C2=A0 select:=3Dselect(left[t],k)
> > =C2=A0 =C2=A0else
> > =C2=A0 =C2=A0 =C2=A0 select:=3Dselect(right[t],k-1-s[left[t]]);
> > end;...
>=20
> read more =C2=BB- Hide quoted text -- Show quoted text -

0
344368722 (5)
1/5/2007 7:02:09 AM
Good to see you speak so confidently... Find some test data and give us
performance comparison...

On Jan 5, 3:02 pm, "Chen Qifeng" <344368...@qq.com> wrote:
> Is it about weight-balanced tree(page 476 in vol. 3 of Knuth)? It quite
> differs from SBT. Weight-balanced tree guarantees that
> 1/w<size[left]/size[right]<w . Sometimes w here is sqrt(2). Due to the
> slow division it works unefficiently. On the contrary there are only
> compares and additions in SBT.
> On Jan 5, 8:38 am, "Booted Cat" <yaoziy...@gmail.com> wrote:
>
> > The background motive behind things like this is China's poor computer
> > science undergraduate programs which stifle the young geniuses who won
> > top places in national programming competitions and even international
> > olympiads in informatics (IOI's) during their junior middle school and
> > high school time: they want to find better academic (especially
> > research) opportunities and communities. Since long ago a gold medal of
> > IOI no longer serves as a significant admission advantage for applying
> > to an american computer science undergrad program, so some of them
> > begin trying to present some research results to lure american
> > professors. For example, a previous attempt is:http://groups.google.com=
/group/sci.math/browse_frm/thread/50586a0beb4...
>
> > Undergraduate students with their own research initiatives and projects
> > have to drop out, as i did from Fudan University. So I very much
> > understand these current programming contestants. I told them maybe for
> > fundamental and heavily attacked things like the binary search tree it
> > is nearly impossible to get something new and significant; maybe they
> > should look into the theoretical part of promising fields such as
> > computational biology, or anything of their own interest. But as Anders
> > Kaseorg (MIT undergrad who won quite a number of IOI's and IMO's in
> > high school) suggested, there is too little a turnround for someone
> > having just completed all his programming competition seasons in high
> > school to make a seriously good research result in fields like
> > computational biology and immediately present it to american professors
> > for admission to an american university.
>
> > Or maybe I should write an open letter, get some famous american cs
> > professors sign it, and maybe also the ACM President, calling for a
> > wholesale of China's top 30 contestants in every year's national
> > olympiad in informatics to american universities...
>
> > Yao Ziyuan
>
> > On Jan 1, 5:02 am, "Booted Cat" <yaoziy...@gmail.com> wrote:
>
> > > A member ("Chen Qifeng") of an online forum about teenagers'
> > > programming contests claims to have found a new binary search tree
> > > algorithm that outperforms all existing well-known algorithms of its
> > > kind, and other members of that forum who have replied all confirmed
> > > his finding. So I think it's time to forward this result to comp.theo=
ry
> > > for a wider-scope evaluation.
>
> > > The thesis in PDF format and an accompanying Pascal source code file
> > > are in a zip file available at:http://yaoziyuan.googlepages.com/SizeB=
alancedTree.zip
>
> > > Also below is the plain text version of that PDF and the source code
> > > for the Usenet's records.
>
> > > Regards,
> > > Yao Ziyuan
>
> > > =3D=3D=3D=3D PLAIN TEXT VERSION OF THE THESIS PDF =3D=3D=3D=3D
> > > Size Balanced Tree
> > > Chen Qifeng (Farmer John)
> > > Zhongshan Memorial Middle School, Guangdong, China
> > > Email:344368...@QQ.com
> > > December 29, 2006
> > > Abstract
> > > This paper presents a unique strategy for maintaining balance in
> > > dynamically
> > > changing Binary Search Trees that has optimal expected behavior at
> > > worst. Size
> > > Balanced Tree is, as the name suggests, a Binary Search Tree (abbr.
> > > BST) kept
> > > balanced by size. It is simple, efficient and versatile in every
> > > aspect. It is very easy to
> > > implement and has a straightforward description and a surprisingly
> > > simple proof of
> > > correctness and runtime. Its runtime matches that of the fastest BST
> > > known so far.
> > > Furthermore, it works much faster than many other famous BSTs due to
> > > the
> > > tendency of a perfect BST in practice. It not only supports typical
> > > primary
> > > operations but also Select and Rank.
> > > Key Words And Phrases
> > > Size Balanced Tree
> > > SBT
> > > Maintain
> > > This paper is dedicated to the memory of Heavens.
> > > 1 Introduction
> > > Before presenting Size Balanced Trees it is necessary to explicate
> > > Binary Search Trees
> > > and rotations on BSTs, Left-Rotate and Right-Rotate.
> > > 1.1 Binary Search Tree
> > > Binary Search Tree is a significant kind of advanced data structures.
> > > It supports many
> > > dynamic-set operations, including Search, Minimum, Maximum,
> > > Predecessor, Successor,
> > > Insert and Delete. It can be used both as a dictionary and as a
> > > priority queue.
> > > A BST is an organized binary tree. Every node in a BST contains two
> > > children at most.
> > > The keys for compare in a BST are always stored in such a way as to
> > > satisfy the
> > > binary-search-tree property:
> > > Let x be a node in a binary search tree. Then the key of x is not less
> > > than that in left
> > > subtree and not larger than that in right subtree.
> > > =E3=80=80=E3=80=80For every node t we use the fields of left[t] and r=
ight[t] to
> > > store two pointers to its
> > > children. And we define key[t] to mean the value of the node t for
> > > compare. In addition
> > > we add s[t], the size of subtree rooted at t, to keep the number of t=
he
> > > nodes in that tree.
> > > Particularly we call 0 the pointer to an empty tree and s[0]=3D0.
> > > 1.2 Rotations
> > > In order to keep a BST balanced (not degenerated to be a chain) we
> > > usually change the
> > > pointer structure through rotations to change the configuration, which
> > > is a local operation
> > > in a search tree that preserves the binary-search-tree property.
> > > Figure1.1: The operation Left-Rotate(x) transforms the configuration =
of
> > > the two
> > > nodes on the right into the configuration on the left by changing a
> > > constant number
> > > of pointers. The configuration on the left can be transformed into the
> > > configuration
> > > on the right by the inverse operation, Right-Rotate(y).
> > > 1.2.1 Pseudocode Of Right-Rotate
> > > The Right-Rotate assumes that the left child exists.
> > > Right-Rotate (t)
>
> > > 1 k=E2=86=90left[t]
>
> > > 2 left[t] =E2=86=90right[k]
>
> > > 3 right[k] =E2=86=90t
>
> > > 4 s[k] =E2=86=90s[t]
>
> > > 5 s[t] =E2=86=90s[left[t]]+s[right[t]]+1
>
> > > 6 t=E2=86=90k
>
> > > 1.2.2 Pseudocode Of Left-Rotate
> > > The Left-Rotate assumes that the right child exists.
> > > Left-Rotate (t)
>
> > > 1 k=E2=86=90right[t]
>
> > > 2 right[t] =E2=86=90left[k]
>
> > > 3 left[k] =E2=86=90t
>
> > > 4 s[k] =E2=86=90s[t]
>
> > > 5 s[t] =E2=86=90s[left[t]]+s[right[t]]+1
>
> > > 6 t=E2=86=90k
>
> > > 2 Size Balanced Tree
> > > Size Balanced Tree (abbr. SBT) is a kind of Binary Search Trees kept
> > > balanced by size. It
> > > supports many dynamic primary operations in the runtime of O(logn):
> > > =E3=80=80=E3=80=80Insert(t,v)
> > > =E3=80=80=E3=80=80Inserts a node whose key is v into the
> > > SBT rooted at t.
> > > =E3=80=80=E3=80=80Delete(t,v)
> > > =E3=80=80=E3=80=80Deletes a node whose key is v from
> > > the SBT rooted at t. In the case that no
> > > such a node in the tree, deletes the node
> > > searched at last.
> > > =E3=80=80=E3=80=80Find(t,v)
> > > =E3=80=80=E3=80=80Finds the node whose key is v and
> > > returns it.
> > > =E3=80=80=E3=80=80Rank(t,v)
> > > =E3=80=80=E3=80=80Returns the rank of v in the tree
> > > rooted at t. In another word, it is one plus
> > > the number of the keys which are less
> > > than v in that tree.
> > > =E3=80=80=E3=80=80Select(t,k)
> > > =E3=80=80=E3=80=80Returns the node which is ranked at
> > > the kth position. Apparently it includes
> > > operations of Get-max and Get-min
> > > because Get-min is equivalent to
> > > Select(t,1) and Get-max is equivalent to
> > > Select(t,s[t])
> > > =E3=80=80=E3=80=80Pred(t,v)
> > > =E3=80=80=E3=80=80Returns the node with maximum key
> > > which is less than v.
> > > =E3=80=80=E3=80=80Succ(t,v)
> > > =E3=80=80=E3=80=80Returns the node with minimum key
> > > which is larger than v.
>
> > > =3D=3D=3D=3D END OF PLAIN TEXT VERSION OF THE THESIS PDF =3D=3D=3D=3D
>
> > > =3D=3D=3D=3D PASCAL SOURCE CODE =3D=3D=3D=3D
> > > {$inline on}
> > > program CQF_SBT;
> > > const maxn=3D2000000;
> > > var key,s,left,right,a,b:array[0..maxn] of longint;
> > >     tt,q:longint;
> > > procedure init;
> > > begin
> > >    readln(q);
> > >    for q:=3D1 to q do
> > >       readln(a[q],b[q]);
> > > end;
> > > procedure work;
> > > var t,k:longint;
> > > procedure right_rotate(var t:longint);inline;
> > > begin
> > >    k:=3Dleft[t];
> > >    left[t]:=3Dright[k];
> > >    right[k]:=3Dt;
> > >    s[k]:=3Ds[t];
> > >    s[t]:=3Ds[left[t]]+s[right[t]]+1;
> > >    t:=3Dk;
> > > end;
> > > procedure left_rotate(var t:longint);inline;
> > > begin
> > >    k:=3Dright[t];
> > >    right[t]:=3Dleft[k];
> > >    left[k]:=3Dt;
> > >    s[k]:=3Ds[t];
> > >    s[t]:=3Ds[left[t]]+s[right[t]]+1;
> > >    t:=3Dk;
> > > end;
> > > procedure maintain(var t:longint;flag:boolean);inline;
> > > begin
> > >    if flag=3Dfalse then
> > >       if s[left[left[t]]]>s[right[t]] then
> > >          right_rotate(t)
> > >       else
> > >          if s[right[left[t]]]>s[right[t]] then begin
> > >             left_rotate(left[t]);
> > >             right_rotate(t);
> > >          end
> > >          else
> > >             exit
> > >    else
> > >       if s[right[right[t]]]>s[left[t]] then
> > >          left_rotate(t)
> > >       else
> > >          if s[left[right[t]]]>s[left[t]] then begin
> > >             right_rotate(right[t]);
> > >             left_rotate(t);
> > >          end
> > >          else
> > >             exit;
> > >    maintain(left[t],false);
> > >    maintain(right[t],true);
> > >    maintain(t,true);
> > >    maintain(t,false);
> > > end;
> > > procedure insert(var t,v:longint);inline;
> > > begin
> > >    if t=3D0 then begin
> > >       inc(tt);
> > >       t:=3Dtt;
> > >       key[t]:=3Dv;
> > >       s[t]:=3D1;
> > >       left[t]:=3D0;
> > >       right[t]:=3D0;
> > >    end
> > >    else begin
> > >       inc(s[t]);
> > >       if v<key[t] then
> > >          insert(left[t],v)
> > >       else
> > >          insert(right[t],v);
> > >       maintain(t,v>=3Dkey[t]);
> > >    end;
> > > end;
> > > function delete(var t:longint;v:longint):longint;inline;
> > > begin
> > >    dec(s[t]);
> > >    if (v=3Dkey[t])or(v<key[t])and(left[t]=3D0)or(v>key[t])and(right[t=
]=3D0)...
>=20
> read more =C2=BB

0
yaoziyuan (186)
1/5/2007 10:56:39 AM
On 4 Jan 2007 16:38:35 -0800, "Booted Cat" <yaoziyuan@gmail.com>
wrote:

>The background motive behind things like this is China's poor computer
>science undergraduate programs which stifle the young geniuses who won
>top places in national programming competitions and even international
>olympiads in informatics (IOI's) during their junior middle school and
>high school time: they want to find better academic (especially
>research) opportunities and communities. Since long ago a gold medal of
>IOI no longer serves as a significant admission advantage for applying
>to an american computer science undergrad program, so some of them
>begin trying to present some research results to lure american
[....]
>Or maybe I should write an open letter, get some famous american cs
>professors sign it, and maybe also the ACM President, calling for a
>wholesale of China's top 30 contestants in every year's national
>olympiad in informatics to american universities...
                
I don't know what is "wholesale of top contestants" But providing
resources to Chinese students is the problem of China government,
and not the responsibility (and duy) of the rest of the world. 

A.L.
0
alewando1 (106)
1/5/2007 1:38:16 PM
On 5 Jan 2007 02:56:39 -0800, "Booted Cat" <yaoziyuan@gmail.com>
wrote:

>Good to see you speak so confidently... Find some test data and give us
>performance comparison...
>
>On Jan 5, 3:02 pm, "Chen Qifeng" <344368...@qq.com> wrote:
>> Is it about weight-balanced tree(page 476 in vol. 3 of Knuth)? It quite
    

Do you know that thara are following habits

a. You rospond AFTER the message bot BEFORE
b. You don't quote 3 pages of trash to add your single sentence.

A.L.
0
alewando1 (106)
1/5/2007 1:40:11 PM
Geniuses don't need resources. They only need FREEDOM TO PURSUE THEIR
INTERESTS. Dropping out does give maximal freedom (plus I have a
shareware business developed since high school hence a good automated
income source for living in China), but some geniuses do care about A
UNIVERSITY DEGREE. In China you can't get them both. I heard that in
the free world (e.g. the US, Hong Kong) a genius can have MORE (BUT
STILL LIMITED) FREEDOM while attending college (a counterexample is
<http://groups.google.com/group/comp.theory/browse_frm/thread/c37b7f0585f8d823/c7c343e8a07028b3?lnk=st&q=k-ary+tree+yao+ziyuan&rnum=1#c7c343e8a07028b3>,
which reveals american faculty members are quite tough), so I think
going to a US or HK university could be a good compromise for degree
wanters. Recently I read an article claiming "geniuses are not
cultivated, but tempered by harsh environment" and citing Einstein
trying twice before passing his qualification exam in physics, Farad
starting as an apprentice and nearly stifled by authorities when
becoming a budding star, Shannon's seminal paper making a devious way
to see sunlight. The article says they are never greenhouse plants;
they are "weeds", "infidels", "victims", "underdogs", but they finally
make their way out. Modern examples include BitTorrent inventor Bram
Cohen, a college dropout from SUNY Buffalo who lived on credit card
debts during the year of creating BitTorrent, and Perelman, who spent 8
lonely years attacking Poincare Conjecture and lived on savings from
past professorship in America and his mother's pension.

Chinese contestants take back all gold medals every year in IOI's and
IMO's but Chinese researchers contribute so little innovation to the
world. Why is that? Because clever students are too many and brave ones
too few.

Yao Ziyuan


On Jan 5, 9:38 pm, A.L. <alewa...@fala2005.com> wrote:
> On 4 Jan 2007 16:38:35 -0800, "Booted Cat" <yaoziy...@gmail.com>
> wrote:
>
>
>
> >The background motive behind things like this is China's poor computer
> >science undergraduate programs which stifle the young geniuses who won
> >top places in national programming competitions and even international
> >olympiads in informatics (IOI's) during their junior middle school and
> >high school time: they want to find better academic (especially
> >research) opportunities and communities. Since long ago a gold medal of
> >IOI no longer serves as a significant admission advantage for applying
> >to an american computer science undergrad program, so some of them
> >begin trying to present some research results to lure american
> [....]
> >Or maybe I should write an open letter, get some famous american cs
> >professors sign it, and maybe also the ACM President, calling for a
> >wholesale of China's top 30 contestants in every year's national
> >olympiad in informatics to american universities...I don't know what is "wholesale of top contestants" But providing
> resources to Chinese students is the problem of China government,
> and not the responsibility (and duy) of the rest of the world.
> 
> A.L.

0
yaoziyuan (186)
1/5/2007 4:02:05 PM
On 5 Jan 2007 08:02:05 -0800, "Booted Cat" <yaoziyuan@gmail.com>
wrote:

>Geniuses don't need resources. They only need FREEDOM TO PURSUE THEIR
>INTERESTS. Dropping out does give maximal freedom (plus I have a
>shareware business developed since high school hence a good automated
>income source for living in China), but some geniuses do care about A
>UNIVERSITY DEGREE. In China you can't get them both. 

Freedom... Freedom... What about freedom in China?...

>Chinese contestants take back all gold medals every year in IOI's and
>IMO's but Chinese researchers contribute so little innovation to the
>world. Why is that? Because clever students are too many and brave ones
>too few.
>

This is not the world's problem. This is problem of citizens of
China.

A.L.
0
alewando1 (106)
1/5/2007 4:10:22 PM

On Jan 6, 12:10 am, A.L. <alewa...@fala2005.com> wrote:
> On 5 Jan 2007 08:02:05 -0800, "Booted Cat" <yaoziy...@gmail.com>
> wrote:
>
> >Geniuses don't need resources. They only need FREEDOM TO PURSUE THEIR
> >INTERESTS. Dropping out does give maximal freedom (plus I have a
> >shareware business developed since high school hence a good automated
> >income source for living in China), but some geniuses do care about A
> >UNIVERSITY DEGREE. In China you can't get them both.Freedom... Freedom... What about freedom in China?...

Freedom in China is up to the Pentagon and me.

>
> >Chinese contestants take back all gold medals every year in IOI's and
> >IMO's but Chinese researchers contribute so little innovation to the
> >world. Why is that? Because clever students are too many and brave ones
> >too few.This is not the world's problem. This is problem of citizens of
> China.
> 
> A.L.

0
yaoziyuan (186)
1/5/2007 4:18:38 PM
On 5 Jan 2007 08:18:38 -0800, "Booted Cat" <yaoziyuan@gmail.com>
wrote:

>
>
>On Jan 6, 12:10 am, A.L. <alewa...@fala2005.com> wrote:
>> On 5 Jan 2007 08:02:05 -0800, "Booted Cat" <yaoziy...@gmail.com>
>> wrote:
>>
>> >Geniuses don't need resources. They only need FREEDOM TO PURSUE THEIR
>> >INTERESTS. Dropping out does give maximal freedom (plus I have a
>> >shareware business developed since high school hence a good automated
>> >income source for living in China), but some geniuses do care about A
>> >UNIVERSITY DEGREE. In China you can't get them both.Freedom... Freedom... What about freedom in China?...
>
>Freedom in China is up to the Pentagon and me.

Pentagon has nothing with freedom in China.

A.L.
0
alewando1 (106)
1/5/2007 5:25:57 PM

On Jan 6, 1:25 am, A.L. <alewa...@fala2005.com> wrote:
> On 5 Jan 2007 08:18:38 -0800, "Booted Cat" <yaoziy...@gmail.com>
> wrote:
>
>
>
> >On Jan 6, 12:10 am, A.L. <alewa...@fala2005.com> wrote:
> >> On 5 Jan 2007 08:02:05 -0800, "Booted Cat" <yaoziy...@gmail.com>
> >> wrote:
>
> >> >Geniuses don't need resources. They only need FREEDOM TO PURSUE THEIR
> >> >INTERESTS. Dropping out does give maximal freedom (plus I have a
> >> >shareware business developed since high school hence a good automated
> >> >income source for living in China), but some geniuses do care about A
> >> >UNIVERSITY DEGREE. In China you can't get them both.Freedom... Freedom... What about freedom in China?...
>
> >Freedom in China is up to the Pentagon and me.Pentagon has nothing with freedom in China.
>
> A.L.

True. The Pentagon launched no new war last year. Seems it's solely up
to me.

0
yaoziyuan (186)
1/6/2007 1:15:29 AM
Freedom in China is a very interesting operations research problem to
ponder at.

On Jan 6, 12:10 am, A.L. <alewa...@fala2005.com> wrote:
> On 5 Jan 2007 08:02:05 -0800, "Booted Cat" <yaoziy...@gmail.com>
> wrote:
>
> >Geniuses don't need resources. They only need FREEDOM TO PURSUE THEIR
> >INTERESTS. Dropping out does give maximal freedom (plus I have a
> >shareware business developed since high school hence a good automated
> >income source for living in China), but some geniuses do care about A
> >UNIVERSITY DEGREE. In China you can't get them both.Freedom... Freedom... What about freedom in China?...
>
> >Chinese contestants take back all gold medals every year in IOI's and
> >IMO's but Chinese researchers contribute so little innovation to the
> >world. Why is that? Because clever students are too many and brave ones
> >too few.This is not the world's problem. This is problem of citizens of
> China.
> 
> A.L.

0
yaoziyuan (186)
1/10/2007 4:27:14 PM
     In any case, it is clear that if the original author (Chen)
really is a student in middle school (I assume this means
"zhong/1 xue/2" = "highschool" in North American parlance), then
he or she is a very good student with an excellent command of
English and a good grasp of concepts that many 3rd-year computer
science students in North America struggle with.

     I hope that Chen is able to find a good university that
allows all students to flourish and live up to their potential.
Unfortunately, I don't know of any scholarship programs from
Western countries that would award scholarships to Chinese
nationals studying at the undergraduate level.  Maybe at some of
the best universities in the US there are such programs.

--Jamie.                 (efil4dreN)
  andrews    .uwo      } Merge these two lines to obtain my e-mail address.
         @csd    .ca   } (Unsolicited "bulk" e-mail costs everyone.)
0
me4 (19624)
1/18/2007 7:57:43 PM
Surely, SBT is faster than normal BSTs

0
sqybilly (2)
2/24/2007 3:31:06 PM
"sqybi" <sqybilly@gmail.com> writes:

> Surely, SBT is faster than normal BSTs

In what context?  If your data arrive in random order, I doubt
any kind of balanced tree will be faster than an unbalanced tree,
because you spend unneeded time doing balancing.  See
        http://benpfaff.org/papers/libavl.pdf
-- 
Ben Pfaff 
blp@cs.stanford.edu
http://benpfaff.org
0
blp (3955)
2/24/2007 5:50:58 PM
On Feb 25, 1:50 am, Ben Pfaff <b...@cs.stanford.edu> wrote:
> "sqybi" <sqybi...@gmail.com> writes:
> > Surely, SBT is faster than normal BSTs
>
> In what context?  If your data arrive in random order, I doubt
> any kind of balanced tree will be faster than an unbalanced tree,
> because you spend unneeded time doing balancing.  See
>        http://benpfaff.org/papers/libavl.pdf
> --
> Ben Pfaff
> b...@cs.stanford.eduhttp://benpfaff.org

I agree with Ben Pfaff. In my comprehension what sqybi said was that
SBT is faster than many ordinary balanced BSTs such as treap, AVL,
Splay in his practice. But I don't think there is a balanced BST which
is faster than a simple unbalanced tree while data are random. I know
SBT does not always beat another BST under all possible cases. But I
do think SBT is the best one in some aspects.

0
344368722 (5)
2/27/2007 2:03:38 PM
On 2=D4=C227=C8=D5, =CF=C2=CE=E710=CA=B103=B7=D6, "Chen Qifeng" <344368...@=
qq.com> wrote:
> On Feb 25, 1:50 am, Ben Pfaff <b...@cs.stanford.edu> wrote:
>
> > "sqybi" <sqybi...@gmail.com> writes:
> > > Surely, SBT is faster than normal BSTs
>
> > In what context?  If your data arrive in random order, I doubt
> > any kind of balanced tree will be faster than an unbalanced tree,
> > because you spend unneeded time doing balancing.  See
> >        http://benpfaff.org/papers/libavl.pdf
> > --
> > Ben Pfaff
> > b...@cs.stanford.eduhttp://benpfaff.org
>
> I agree with Ben Pfaff. In my comprehension what sqybi said was that
> SBT is faster than many ordinary balanced BSTs such as treap, AVL,
> Splay in his practice. But I don't think there is a balanced BST which
> is faster than a simple unbalanced tree while data are random. I know
> SBT does not always beat another BST under all possible cases. But I
> do think SBT is the best one in some aspects.

Sorry...I meant that SBT is faster than other balanced BSTs...
My poor English...

0
sqybilly (2)
4/7/2007 3:02:03 AM
Undeniable SBT is quite fast , but proving "faster than other balanced
BSTs" needs more tests.

0
godric_forever
4/8/2007 10:12:57 AM
G'day all.

On Feb 25, 3:50 am, Ben Pfaff <b...@cs.stanford.edu> wrote:

> In what context?  If your data arrive in random order, I doubt
> any kind of balanced tree will be faster than an unbalanced tree,
> because you spend unneeded time doing balancing.

Here's the real secret of balancing binary search trees:  To a first
approximation, it doesn't matter what algorithm you use.

The purpose of balancing your binary search trees is to avoid
pathological behaviour.  That's all.  All of the reasonable algorithms
that you know have the same asymptotic complexity.  Their constant
factors are invariably so close that they don't matter in practice.
Given that, it usually makes no sense to choose an algorithm based
on "speed", whatever that means.

Red-black trees, for example, have an advantage that they only
require an extra bit of storage in each node.

AVL trees have the advantage that they minimise the number of
rotation operations per insertion.

The Adams bounded balance algorithm has the advantage that
it stores the number of elements in each subtree in the node,
and some nonstandard operations (e.g. tree merging) can take
advantage of that.

Other algorithms (e.g. in-memory B-trees with relaxed balance)
are easier to make concurrent than others.

Cheers,
Andrew Bromage

0
deguerre (3)
4/8/2007 12:01:44 PM
Reply: