"Size Balanced Tree"  more efficient than any known algorithm?
 From: "Booted Cat" <yaoziyuan@xxxxxxxxx>
 Date: 31 Dec 2006 13:02:55 0800
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 wellknown 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 widerscope 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, LeftRotate and RightRotate.
1.1 Binary Search Tree
Binary Search Tree is a significant kind of advanced data structures.
It supports many
dynamicset 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
binarysearchtree 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 binarysearchtree property.
Figure1.1: The operation LeftRotate(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, RightRotate(y).
1.2.1 Pseudocode Of RightRotate
The RightRotate assumes that the left child exists.
RightRotate (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 LeftRotate
The LeftRotate assumes that the right child exists.
LeftRotate (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 Getmax and Getmin
because Getmin is equivalent to
Select(t,1) and Getmax 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],k1s[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 ====
.
 FollowUps:
 Prev by Date: Re: A DTM to reverse a bit string
 Next by Date: Re: "Size Balanced Tree"  more efficient than any known algorithm?
 Previous by thread: Re: Probabilities in Complexity of Sequential Search Question
 Next by thread: Re: "Size Balanced Tree"  more efficient than any known algorithm?
 Index(es):
Relevant Pages
