Size Balanced Tree
Chen Qifeng (Farmer John)
Zhongshan Memorial Middle School, Guangdong, China
Email:344368722@QQ
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 supports not only 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 .
中
华
信
息
学
竞
赛
网
w w w .
100x
i n x
i .
c o
m
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 b
e 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).
中
华
信
息
学
竞
赛
网
w w w .
100x
i n x
i .
c o
m
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 mi
nimum key which is larger than v.
中
华
信
息
学
竞
赛
网
w w w .
100x
i n x
i .
delete inc o
m
Commonly every node of a SBT contains key, left, right  and extra but useful updated field: its size , which has been defined in the former introduction. The kernel of a SBT is divided into two restrictions on size:
For every node pointed by t in a SBT, we guarantee that Property(a):
]]][[[]]],[[[]][[t left right s t left left s t right s ≥
Property(b):
]]][[[]]],[[[]][[t right left s t right right s t left s ≥
Figure 2.1:The nodes L and R are left and right children of the
node T. The Subtrees A and B, C and D are left and right subtrees of the nodes L and R respectively.
Correspond to properties (a) and (b), ][][],[&][][],[L s D s C s R s B s A s ≤≤
3 Maintain
Assume that we need to insert a node whose key is v into a BST. Generally we use the following procedure to accomplish the mission.
Simple-Insert (t,v) 1 If  t=0 then
2    t ←NEW-NODE(v)
3 Else
4    s[t] ←s[t]+1
5    If  v<key[t] then
6      Simple-Insert(left[t],v)
7    Else
8      Simple-Insert(right[t],v)
中
华
信
息
学
竞
赛
网
w w w .
100x
i n x
i .
c o
m
After the execution of Simple-Insert properties (a) and (b) are probably not satisfied. In that case we need to maintain the SBT.
The vital operation on a SBT is a unique procedure, Maintain. Maintain(t) is used to maintain the SBT rooted at t. The hypothesis that the subtrees of t are SBT is applied before the performance.
Since properties (a) and (b) are symmetrical we only discuss the case that restriction (a) is violated in detail.
Case 1: s[left[left[t]]>s[right[t]]
In this case that s[A]>s[R] correspond to Figure 2.1 after Insert(left[t],v), we can execute the following instructions to repair the SBT:
(1) First perform Right-Rotate(T). This operation transforms Figure 2.1 into Figure
3.1;
Figure 3.1: All the nodes are defined the same as in Figure 2.1.
(2) And then sometimes it occurs that the tree is still not a SBT because s[C]>s[B] or s[D]>s[B] by any possibility. So it is necessary to implement Maintain(T). (3) In succession the configuration of the right subtree of the node L might be changed. Because of the possibility of violating the properties it is needful to run Maintain(L) again.
Case 2: s[right[left[t]]>s[right[t]]
In this case that s[B]>s[R] correspond to Figure 3.2 after Insert(left[t],v), the maintaining is kind of complicated than that in case 1. We can carry out the following operations for repair.
中
华
信
息
学
竞
赛
网
w w w .
100x
i n x
i .
c o
m

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。