重庆夜网Size Balanced Tree
Chen Qifeng (Farmer John)
Zhongshan Memorial Middle School, Guangdong, China
Email:
December 29, 2006
Abstract
This paper prents 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 Phras
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 prenting 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-t operations, including Search, Minimum, Maximum, Predecessor, Successor, Inrt and Delete. It ca
n be ud 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-arch-tree property:
Let x be a node in a binary arch 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 u 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 arch tree that prerves the binary-arch-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 inver operation, Right-Rotate(y).
中
华
信
息
学
竞
赛
网
w w w .
100x
i n x
i .
c o
m
1.2.1 Pudocode 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 Pudocode 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):
Inrt(t,v) Inrts a node who key is v into the SBT rooted at t.
Delete(t,v) Deletes a node who key is v from the SBT rooted at t. In the ca
that no such a node in the tree, deletes the node arched at last.
Find(t,v) Finds the node who 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 becau 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.
中
华
信
苏轼蝶恋花息
学
竞
赛
网
w w w .
100x
女性脂溢性脱发i n x
i .
c o
m
Commonly every node of a SBT contains key, left, right and extra but uful 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 inrt a node who key is v into a BST. Generally we u the following procedure to accomplish the mission.
Simple-Inrt (t,v) 1 If t=0 then
2 t ←NEW-NODE(v)
3 El
4 s[t] ←s[t]+1
5 If v<key[t] then
6 Simple-Inrt(left[t],v)
7 El
8 Simple-Inrt(right[t],v)
中
华
信
息
学
竞
赛
网
w w w .
100x
i n x
i .
c o
m
After the execution of Simple-Inrt properties (a) and (b) are probably not satisfied. In that ca we need to maintain the SBT.
The vital operation on a SBT is a unique procedure, Maintain. Maintain(t) is ud 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 ca that restriction (a) is violated in detail.
跖疣怎么引起的
Ca 1: s[left[left[t]]>s[right[t]]
In this ca that s[A]>s[R] correspond to Figure 2.1 after Inrt(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 becau 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. Becau of the possibility of violating the properties it is needful to run Maintain(L) again.
Ca 2: s[right[left[t]]>s[right[t]]
In this ca that s[B]>s[R] correspond to Figure 3.2 after Inrt(left[t],v), the maintaining is kind of complicated than that in ca 1. We can carry out the following operations for repair.
中
华
信
息
学
竞
赛
网
w w w .
100x
i n x
i .
c o
m
