# "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 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 ====

.

**Follow-Ups**:

- 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):