"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


==== PLAIN TEXT VERSION OF THE THESIS PDF ====
Size Balanced Tree
Chen Qifeng (Farmer John)
Zhongshan Memorial Middle School, Guangdong, China
Email:344368722@xxxxxx
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.
  For 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]=0.
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←left[t]

2 left[t] ←right[k]

3 right[k] ←t

4 s[k] ←s[t]

5 s[t] ←s[left[t]]+s[right[t]]+1

6 t←k

1.2.2 Pseudocode Of Left-Rotate
The Left-Rotate assumes that the right child exists.
Left-Rotate (t)

1 k←right[t]

2 right[t] ←left[k]

3 left[k] ←t

4 s[k] ←s[t]

5 s[t] ←s[left[t]]+s[right[t]]+1

6 t←k

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):
  Insert(t,v)
  Inserts a node whose key is v into the
SBT rooted at t.
  Delete(t,v)
  Deletes 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.
  Find(t,v)
  Finds the node whose key is v and
returns it.
  Rank(t,v)
  Returns 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.
  Select(t,k)
  Returns 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])
  Pred(t,v)
  Returns the node with maximum key
which is less than v.
  Succ(t,v)
  Returns the node with minimum key
which is larger than v.

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

==== PASCAL SOURCE CODE ====
{$inline on}
program CQF_SBT;
const maxn=2000000;
var key,s,left,right,a,b:array[0..maxn] of longint;
tt,q:longint;
procedure init;
begin
readln(q);
for q:=1 to q do
readln(a[q],b[q]);
end;
procedure work;
var t,k:longint;
procedure right_rotate(var t:longint);inline;
begin
k:=left[t];
left[t]:=right[k];
right[k]:=t;
s[k]:=s[t];
s[t]:=s[left[t]]+s[right[t]]+1;
t:=k;
end;
procedure left_rotate(var t:longint);inline;
begin
k:=right[t];
right[t]:=left[k];
left[k]:=t;
s[k]:=s[t];
s[t]:=s[left[t]]+s[right[t]]+1;
t:=k;
end;
procedure maintain(var t:longint;flag:boolean);inline;
begin
if flag=false 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=0 then begin
inc(tt);
t:=tt;
key[t]:=v;
s[t]:=1;
left[t]:=0;
right[t]:=0;
end
else begin
inc(s[t]);
if v<key[t] then
insert(left[t],v)
else
insert(right[t],v);
maintain(t,v>=key[t]);
end;
end;
function delete(var t:longint;v:longint):longint;inline;
begin
dec(s[t]);
if (v=key[t])or(v<key[t])and(left[t]=0)or(v>key[t])and(right[t]=0)
then begin
delete:=key[t];
if (left[t]=0)or(right[t]=0) then
t:=left[t]+right[t]
else
key[t]:=delete(left[t],key[t]+1);
end
else
if v<key[t] then
delete:=delete(left[t],v)
else
delete:=delete(right[t],v);
end;
function find(var t,v:longint):boolean;inline;
begin
if t=0 then
exit(false);
if v<key[t] then
find:=find(left[t],v)
else
find:=(key[t]=v)or find(right[t],v);
end;
function rank(var t,v:longint):longint;inline;
begin
if t=0 then
exit(1);
if v<=key[t] then
rank:=rank(left[t],v)
else
rank:=s[left[t]]+1+rank(right[t],v);
end;
function select(var t:longint;k:longint):longint;inline;
begin
if k=s[left[t]]+1 then
exit(key[t]);
if k<=s[left[t]] then
select:=select(left[t],k)
else
select:=select(right[t],k-1-s[left[t]]);
end;
function pred(var t,v:longint):longint;inline;
begin
if t=0 then
exit(v);
if v<=key[t] then
pred:=pred(left[t],v)
else begin
pred:=pred(right[t],v);
if pred=v then
pred:=key[t];
end;
end;
function succ(var t,v:longint):longint;inline;
begin
if t=0 then
exit(v);
if key[t]<=v then
succ:=succ(right[t],v)
else begin
succ:=succ(left[t],v);
if succ=v then
succ:=key[t];
end;
end;
begin
tt:=0;
t:=0;
s[0]:=0;
for q:=1 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.
==== END OF PASCAL SOURCE CODE ====

.



Relevant Pages