Re: "Size Balanced Tree" - more efficient than any known algorithm?
- From: "Booted Cat" <yaoziyuan@xxxxxxxxx>
- Date: 5 Jan 2007 02:56:39 -0800
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...@xxxxxx> 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...@xxxxxxxxx> 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...@xxxxxxxxx> 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/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:344368...@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)...
read more »
.
- Follow-Ups:
- References:
- "Size Balanced Tree" - more efficient than any known algorithm?
- From: Booted Cat
- Re: "Size Balanced Tree" - more efficient than any known algorithm?
- From: Booted Cat
- "Size Balanced Tree" - more efficient than any known algorithm?
- Prev by Date: Re: what is the complexity of Hamiltonian problem on 2-regular digraph
- Next by Date: Re: "Size Balanced Tree" - more efficient than any known algorithm?
- Previous by thread: Re: "Size Balanced Tree" - more efficient than any known algorithm?
- Next by thread: Re: "Size Balanced Tree" - more efficient than any known algorithm?
- Index(es):
Relevant Pages
|
|
